hess_color.h

Go to the documentation of this file.

// Hessian coloring algorithms -*- C++ -*-

// Copyright (C) 2008 Mihaly Csaba Markot
//
// This file is a COCONUT inference engine.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef __HESS_COLOR_H_
#define __HESS_COLOR_H_

#include <sparsity.h>
#include <linalg.h>
#include <print_seq.h>

namespace coco {

// This value can be used to determine whether the Hessian is sparse enough
// to invoke Hessian-coloring and thus the evaluations of binary vectors for
// the Hessian-vector products. For dense problems the unit vectors are adviced
// to be used.
#define HESS_VEC_THRESHOLD 0.9

// This is algorithm StarColoringAlg1 of A.H. Gebremedhin, F. Manne, A. Pothen:
// "What Color Is Your Jacobian? Graph Coloring For Computing Derivatives.",
// SIAM Review 47(4), pp. 629-705.
//
// Input: n, the size of the Hessian (number of variables)
//        H, the sparsity structure of the Hessian (e.g. as a 0-1 matrix, of
//           size nxn
// Output: parts: the partitioning of the columns of H.
//         provides: provides has parts.size() rows and n columns, and each
//                   nonzero element of it, (say provides[i][j] = k), indicates
//                   that the jth element of the product of the Hessian and the
//                   ith binary vector provides the Hessian element
//                   H(j,k-1) = H(k-1,j).
//
// Meaning: By setting the binary n-vector d_i to d_i[j]=1 if j \in parts[i],
// d_i[j]=0 otherwise, and computing Hess*d_i (i=1,...,parts.size()), it is
// guaranteed that all different element of the Hessian appears as some element
// of the resulting product, as given by "provides".
//
void hess_star_color1(const unsigned int n,
                      const linalg::matrix<int>& H,
                      std::vector<std::vector<unsigned int> >& parts,
                      std::vector<linalg::sparse_vector<unsigned int> >& provides);

} // namespace coco

#endif /* __HESS_COLOR_H_ */

---