Prev | Next |

@(@\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}} }@)@

*f*.subgraph_sparsity(

*select_domain*, *select_range*, *transpose*, *pattern_out*

)

We use @(@ F : \B{R}^n \rightarrow \B{R}^m @)@ to denote the AD function corresponding to the operation sequence stored in

*f*

.
This routine uses a subgraph technique. To be specific, for each dependent variable, it a subgraph of the operation sequence to determine which independent variables affect it. This avoids to overhead of performing set operations that is inherent in other methods for computing sparsity patterns.

The sparsity calculation for atomic functions in the

*f*

operation sequence
are not efficient. To be specific, each atomic function is treated as if
all of its outputs depend on all of its inputs.
This may be improved upon in the future; see the
subgraph atomic functions
wish list item.
The type

*BoolVector*

is a SimpleVector
class with
elements of type
`bool`

.
The type

*SizeVector*

is a SimpleVector
class with
elements of type
`size_t`

.
The object

*f*

has prototype

ADFun<*Base*> *f*

The argument

*select_domain*

has prototype

const *BoolVector*& *select_domain*

It has size @(@
n
@)@ and specifies which independent variables
to include in the calculation.
If not all the independent variables are included in the calculation,
a forward pass on the operation sequence is used to determine which
nodes may be in the subgraphs.
The argument

*select_range*

has prototype

const *BoolVector*& *select_range*

It has size @(@
m
@)@ and specifies which components of the range
to include in the calculation.
A subgraph is built for each dependent variable
and the selected set of independent variables.
This argument has prototype

bool *transpose*

If
*transpose*

it is false (true),
upon return
*pattern_out*

is a sparsity pattern for
@(@
J(x)
@)@ (@(@
J(x)^\R{T}
@)@) defined below.
This argument has prototype

sparse_rc<*SizeVector*>& *pattern_out*

This input value of
*pattern_out*

does not matter.
Upon return
*pattern_out*

is a
dependency pattern
for @(@
F(x)
@)@.
The pattern has @(@
m
@)@ rows, @(@
n
@)@ columns.
If
*select_domain*[*j*]

is true,
*select_range*[*i*]

is true, and
@(@
F_i (x)
@)@ depends on @(@
x_j
@)@,
then the pair @(@
(i, j)
@)@ is in
*pattern_out*

.
Not that this is also a sparsity pattern for the Jacobian
@[@
J(x) = R F^{(1)} (x) D
@]@
where @(@
D
@)@ (@(@
R
@)@) is the diagonal matrix corresponding
to
*select_domain*

(
*select_range*

).
The file subgraph_sparsity.cpp contains an example and test of this operation. It returns true if it succeeds and false otherwise.

Input File: cppad/core/subgraph_sparsity.hpp