\(\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_sparsity¶
View page sourceSubgraph Dependency Sparsity Patterns¶
Syntax¶
subgraph_sparsity
(See Also¶
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 creates a subgraph of the operation sequence containing the variables that affect the dependent variable. This avoids the 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 sparsity 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
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.