\(\newcommand{\W}[1]{ \; #1 \; }\) \(\newcommand{\R}[1]{ {\rm #1} }\) \(\newcommand{\B}[1]{ {\bf #1} }\) \(\newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} }\) \(\newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} }\) \(\newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} }\) \(\newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }\)
sparse_hes¶
View page sourceComputing Sparse Hessians¶
Syntax¶
sparse_hes
(Purpose¶
We use \(F : \B{R}^n \rightarrow \B{R}^m\) to denote the function corresponding to f . Here n is the Domain size, and m is the Range size, or f . The syntax above takes advantage of sparsity when computing the Hessian
In the sparse case, this should be faster and take less memory than Hessian . The matrix element \(H_{i,j} (x)\) is the second partial of \(w^\R{T} F (x)\) with respect to \(x_i\) and \(x_j\).
SizeVector¶
The type SizeVector is a SimpleVector class with
elements of type
size_t
.
BaseVector¶
The type BaseVector is a SimpleVector class with
elements of type
size_t
.
f¶
This object has prototype
ADFun
< Base > f
Note that the Taylor coefficients stored in f are affected by this operation; see Uses Forward below.
x¶
This argument has prototype
const
BaseVector & x
and its size is n . It specifies the point at which to evaluate the Hessian \(H(x)\).
w¶
This argument has prototype
const
BaseVector & w
and its size is m . It specifies the weight for each of the components of \(F(x)\); i.e. \(w_i\) is the weight for \(F_i (x)\).
subset¶
This argument has prototype
sparse_rcv
< SizeVector , BaseVector >& subset
Its row size and column size is n ; i.e.,
subset . nr
() == n and subset . nc
() == n .
It specifies which elements of the Hessian are computed.
The input value of its value vector subset .
val
() does not matter. Upon return it contains the value of the corresponding elements of the Hessian.All of the row, column pairs in subset must also appear in pattern ; i.e., they must be possibly non-zero.
The Hessian is symmetric, so one has a choice as to which off diagonal elements to put in subset . It will probably be more efficient if one makes this choice so that the there are more entries in each non-zero column of subset ; see n_sweep below.
pattern¶
This argument has prototype
const sparse_rc
< SizeVector >& pattern
Its row size and column size is n ; i.e.,
pattern . nr
() == n and pattern . nc
() == n .
It is a sparsity pattern for the Hessian \(H(x)\).
If the i-th row (j-th column) does not appear in subset ,
the i-th row (j-th column) of pattern does not matter
and need not be computed.
This argument is not used (and need not satisfy any conditions),
when work is non-empty.
subset¶
If the i-th row and i-th column do not appear in subset , the i-th row and column of pattern do not matter. In this case the i-th-th row and column may have no entries in pattern even though they are possibly non-zero in \(H(x)\). (This can be used to reduce the amount of computation required to find pattern .)
coloring¶
The coloring algorithm determines which rows and columns can be computed during the same sweep. This field has prototype
const std::string&
coloring
This value only matters when work is empty; i.e.,
after the work constructor or work . clear
() .
cppad.symmetric¶
This coloring takes advantage of the fact that the Hessian matrix is symmetric when find a coloring that requires fewer sweeps .
cppad.general¶
This is the same as the sparse Jacobian cppad method which does not take advantage of symmetry.
colpack.symmetric¶
If colpack_prefix was specified on the
CMake Command line,
you can set coloring to colpack.symmetric
.
This also takes advantage of the fact that the Hessian matrix is symmetric.
colpack.general¶
If colpack_prefix was specified on the
CMake Command line,
you can set coloring to colpack.general
.
This is the same as the sparse Jacobian
colpack method
which does not take advantage of symmetry.
colpack.star Deprecated 2017-06-01¶
The colpack.star
method is deprecated.
It is the same as the colpack.symmetric
method
which should be used instead.
work¶
This argument has prototype
sparse_hes_work&
work
We refer to its initial value,
and its value after work . clear
() , as empty.
If it is empty, information is stored in work .
This can be used to reduce computation when
a future call is for the same object f ,
and the same subset of the Hessian.
In fact, it can be used with a different f
and a different subset provided that Hessian sparsity pattern
for f and the sparsity pattern in subset are the same.
If either of these values change, use work . clear
() to
empty this structure.
n_sweep¶
The return value n_sweep has prototype
size_t
n_sweep
It is the number of first order forward sweeps used to compute the requested Hessian values. Each first forward sweep is followed by a second order reverse sweep so it is also the number of reverse sweeps. It is also the number of colors determined by the coloring method mentioned above. This is proportional to the total computational work, not counting the zero order forward sweep, or combining multiple columns and rows into a single sweep.
Uses Forward¶
After each call to Forward ,
the object f contains the corresponding
Taylor coefficients .
After a call to sparse_hes
the zero order coefficients correspond to
f .
Forward
(0, x )
All the other forward mode coefficients are unspecified.
Example¶
The files sparse_hes.cpp
is an example and test of sparse_hes
.
It returns true
, if it succeeds, and false
otherwise.
Subset Hessian¶
The routine
sparse_sub_hes.cpp
is an example and test that compute a subset of a sparse Hessian.
It returns true
, for success, and false
otherwise.