Prev Next Index-> contents reference index search external Up-> CppAD ADFun sparsity_pattern subgraph_sparsity CppAD-> Install Introduction AD ADFun preprocessor multi_thread utility ipopt_solve Example speed Appendix ADFun-> record_adfun drivers Forward Reverse sparsity_pattern sparse_derivative optimize abs_normal FunCheck check_for_nan sparsity_pattern-> for_jac_sparsity ForSparseJac rev_jac_sparsity RevSparseJac rev_hes_sparsity RevSparseHes for_hes_sparsity ForSparseHes dependency.cpp rc_sparsity.cpp subgraph_sparsity subgraph_sparsity-> subgraph_sparsity.cpp Headings-> Syntax Notation Method Atomic Function BoolVector SizeVector f select_domain select_range transpose pattern_out Example

$\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}} }$
Subgraph Dependency Sparsity Patterns

Syntax
f.subgraph_sparsity(      select_domain, select_range, transpose, pattern_out )

Notation
We use $F : \B{R}^n \rightarrow \B{R}^m$ to denote the AD function corresponding to the operation sequence stored in f .

Method
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.

Atomic Function
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.

BoolVector
The type BoolVector is a SimpleVector class with elements of type bool.

SizeVector
The type SizeVector is a SimpleVector class with elements of type size_t.

f
The object f has prototype       ADFun<Base> f 
select_domain
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.

select_range
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.

transpose
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.

pattern_out
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 ).

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