lines 14-270 of file: include/cppad/core/sparse_jacobian.hpp

{xrst_begin sparse_jacobian}
{xrst_spell
   recomputed
   valarray
}

Sparse Jacobian
###############

Syntax
******

| *jac* = *f* . ``SparseJacobian`` ( *x* )
| *jac* = *f* . ``SparseJacobian`` ( *x* , *p* )
| *n_sweep* = *f* . ``SparseJacobianForward`` ( *x* , *p* , *row* , *col* , *jac* , *work* )
| *n_sweep* = *f* . ``SparseJacobianReverse`` ( *x* , *p* , *row* , *col* , *jac* , *work* )

Purpose
*******
We use :math:`n` for the :ref:`fun_property@Domain` size,
and :math:`m` for the :ref:`fun_property@Range` size of *f* .
We use :math:`F : \B{R}^n \rightarrow \B{R}^m` do denote the
:ref:`glossary@AD Function`
corresponding to *f* .
The syntax above sets *jac* to the Jacobian

.. math::

   jac = F^{(1)} (x)

This routine takes advantage of the sparsity of the Jacobian
in order to reduce the amount of computation necessary.
If *row* and *col* are present, it also takes
advantage of the reduced set of elements of the Jacobian that
need to be computed.
One can use speed tests (e.g. :ref:`speed_test-name` )
to verify that results are computed faster
than when using the routine :ref:`Jacobian-name` .

f
*
The object *f* has prototype

   ``ADFun`` < *Base* > *f*

Note that the :ref:`ADFun-name` object *f* is not ``const``
(see :ref:`sparse_jacobian@Uses Forward` below).

x
*
The argument *x* has prototype

   ``const`` *BaseVector* & *x*

(see :ref:`sparse_jacobian@BaseVector` below)
and its size
must be equal to *n* , the dimension of the
:ref:`fun_property@Domain` space for *f* .
It specifies
that point at which to evaluate the Jacobian.

p
*
The argument *p* is optional and has prototype

   ``const`` *SetVector* & *p*

(see :ref:`sparse_jacobian@SetVector` below).
If it has elements of type ``bool`` ,
its size is :math:`m * n`.
If it has elements of type ``std::set<size_t>`` ,
its size is :math:`m` and all its set elements are between
zero and :math:`n - 1`.
It specifies a
:ref:`glossary@Sparsity Pattern`
for the Jacobian :math:`F^{(1)} (x)`.

If this sparsity pattern does not change between calls to
``SparseJacobian`` , it should be faster to calculate *p* once
(using :ref:`ForSparseJac-name` or :ref:`RevSparseJac-name` )
and then pass *p* to ``SparseJacobian`` .
Furthermore, if you specify *work* in the calling sequence,
it is not necessary to keep the sparsity pattern; see the heading
:ref:`sparse_jacobian@work@p` under the *work* description.

In addition,
if you specify *p* , CppAD will use the same
type of sparsity representation
(vectors of ``bool`` or vectors of ``std::set<size_t>`` )
for its internal calculations.
Otherwise, the representation
for the internal calculations is unspecified.

row, col
********
The arguments *row* and *col* are optional and have prototype

| |tab| ``const`` *SizeVector* & *row*
| |tab| ``const`` *SizeVector* & *col*

(see :ref:`sparse_jacobian@SizeVector` below).
They specify which rows and columns of :math:`F^{(1)} (x)` are
computes and in what order.
Not all the non-zero entries in :math:`F^{(1)} (x)` need be computed,
but all the entries specified by *row* and *col*
must be possibly non-zero in the sparsity pattern.
We use :math:`K` to denote the value *jac* . ``size`` ()
which must also equal the size of *row* and *col* .
Furthermore,
for :math:`k = 0 , \ldots , K-1`, it must hold that
:math:`row[k] < m` and :math:`col[k] < n`.

jac
***
The result *jac* has prototype

   *BaseVector* & *jac*

In the case where the arguments *row* and *col* are not present,
the size of *jac* is :math:`m * n` and
for :math:`i = 0 , \ldots , m-1`,
:math:`j = 0 , \ldots , n-1`,

.. math::

   jac [ i * n + j ] = \D{ F_i }{ x_j } (x)

In the case where the arguments *row* and *col* are present,
we use :math:`K` to denote the size of *jac* .
The input value of its elements does not matter.
Upon return, for :math:`k = 0 , \ldots , K - 1`,

.. math::

   jac [ k ] = \D{ F_i }{ x_j } (x)
   \; , \;
   \; {\rm where} \;
   i = row[k]
   \; {\rm and } \;
   j = col[k]

work
****
If this argument is present, it has prototype

   ``sparse_jacobian_work&`` *work*

This object can only be used with the routines
``SparseJacobianForward`` and ``SparseJacobianReverse`` .
During its the first use, information is stored in *work* .
This is used to reduce the work done by future calls to the same mode
(forward or reverse),
the same *f* , *p* , *row* , and *col* .
If a future call is for a different mode,
or any of these values have changed,
you must first call *work* . ``clear`` ()
to inform CppAD that this information needs to be recomputed.

color_method
============
The coloring algorithm determines which columns (forward mode)
or rows (reverse mode) can be computed during the same sweep.
This field has prototype

   ``std::string`` *work* . ``color_method``

and its default value (after a constructor or ``clear()`` )
is ``"cppad"`` .
If :ref:`colpack_prefix-name` is specified on the
:ref:`cmake@CMake Command` line,
you can set this method to ``"colpack"`` .
This value only matters on the first call to ``sparse_jacobian``
that follows the *work* constructor or a call to
*work* . ``clear`` () .

p
=
If *work* is present, and it is not the first call after
its construction or a clear,
the sparsity pattern *p* is not used.
This enables one to free the sparsity pattern
and still compute corresponding sparse Jacobians.

n_sweep
*******
The return value *n_sweep* has prototype

   ``size_t`` *n_sweep*

If ``SparseJacobianForward`` (``SparseJacobianReverse`` ) is used,
*n_sweep* is the number of first order forward (reverse) sweeps
used to compute the requested Jacobian values.
(This is also the number of colors determined by the coloring method
mentioned above).
This is proportional to the total work that ``SparseJacobian`` does,
not counting the zero order forward sweep,
or the work to combine multiple columns (rows) into a single sweep.

BaseVector
**********
The type *BaseVector* must be a :ref:`SimpleVector-name` class with
:ref:`elements of type<SimpleVector@Elements of Specified Type>`
*Base* .
The routine :ref:`CheckSimpleVector-name` will generate an error message
if this is not the case.

SetVector
*********
The type *SetVector* must be a :ref:`SimpleVector-name` class with
:ref:`elements of type<SimpleVector@Elements of Specified Type>`
``bool`` or ``std::set<size_t>`` ;
see :ref:`glossary@Sparsity Pattern` for a discussion
of the difference.
The routine :ref:`CheckSimpleVector-name` will generate an error message
if this is not the case.

Restrictions
============
If *SetVector* has elements of ``std::set<size_t>`` ,
then *p* [ *i* ] must return a reference (not a copy) to the
corresponding set.
According to section 26.3.2.3 of the 1998 C++ standard,
``std::valarray< std::set<size_t> >`` does not satisfy
this condition.

SizeVector
**********
The type *SizeVector* must be a :ref:`SimpleVector-name` class with
:ref:`elements of type<SimpleVector@Elements of Specified Type>`
``size_t`` .
The routine :ref:`CheckSimpleVector-name` will generate an error message
if this is not the case.

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 any of the sparse Jacobian routines,
the zero order Taylor coefficients correspond to
*f* . ``Forward`` (0, *x* )
and the other coefficients are unspecified.

After ``SparseJacobian`` ,
the previous calls to :ref:`Forward-name` are undefined.

Example
*******
{xrst_toc_hidden
   example/sparse/sparse_jacobian.cpp
}
The routine
:ref:`sparse_jacobian.cpp-name`
is examples and tests of ``sparse_jacobian`` .
It return ``true`` , if it succeeds and ``false`` otherwise.

{xrst_end sparse_jacobian}
