lines 9-236 of file: include/cppad/core/sparse_hes.hpp

{xrst_begin sparse_hes}
{xrst_spell
   nr
}

Computing Sparse Hessians
#########################

Syntax
******

| *n_sweep* = *f* . ``sparse_hes`` (
| |tab| *x* , *w* , *subset* , *pattern* , *coloring* , *work*
| )

Purpose
*******
We use :math:`F : \B{R}^n \rightarrow \B{R}^m` to denote the
function corresponding to *f* .
Here *n* is the :ref:`fun_property@Domain` size,
and *m* is the :ref:`fun_property@Range` size, or *f* .
The syntax above takes advantage of sparsity when computing the Hessian

.. math::

   H(x) = \dpow{2}{x} \sum_{i=0}^{m-1} w_i F_i (x)

In the sparse case, this should be faster and take less memory than
:ref:`Hessian-name` .
The matrix element :math:`H_{i,j} (x)` is the second partial of
:math:`w^\R{T} F (x)` with respect to :math:`x_i` and :math:`x_j`.

SizeVector
**********
The type *SizeVector* is a :ref:`SimpleVector-name` class with
:ref:`elements of type<SimpleVector@Elements of Specified Type>`
``size_t`` .

BaseVector
**********
The type *BaseVector* is a :ref:`SimpleVector-name` class with
:ref:`elements of type<SimpleVector@Elements of Specified 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
:ref:`sparse_hes@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
:math:`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 :math:`F(x)`;
i.e. :math:`w_i` is the weight for :math:`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 :ref:`sparse_hes@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 :math:`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 :ref:`sparse_hes@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 :math:`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
:ref:`sweeps<sparse_hes@n_sweep>` .

cppad.general
=============
This is the same as the sparse Jacobian
:ref:`sparse_jac@coloring@cppad` method
which does not take advantage of symmetry.

colpack.symmetric
=================
If :ref:`colpack_prefix-name` was specified on the
:ref:`cmake@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 :ref:`colpack_prefix-name` was specified on the
:ref:`cmake@CMake Command` line,
you can set *coloring* to ``colpack.general`` .
This is the same as the sparse Jacobian
:ref:`sparse_jac@coloring@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 :ref:`Forward-name` ,
the object *f* contains the corresponding
:ref:`Taylor coefficients<glossary@Taylor Coefficient>` .
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
*******
{xrst_toc_hidden
   example/sparse/sparse_hes.cpp
}
The files :ref:`sparse_hes.cpp-name`
is an example and test of ``sparse_hes`` .
It returns ``true`` , if it succeeds, and ``false`` otherwise.

Subset Hessian
**************
The routine
:ref:`sparse_sub_hes.cpp-name`
is an example and test that compute a subset of a sparse Hessian.
It returns ``true`` , for success, and ``false`` otherwise.

{xrst_end sparse_hes}
