CppAD: A C++ Algorithmic Differentiation Package  20171217
rev_hes_sparsity.hpp
Go to the documentation of this file.
1 # ifndef CPPAD_CORE_REV_HES_SPARSITY_HPP
2 # define CPPAD_CORE_REV_HES_SPARSITY_HPP
3
4 /* --------------------------------------------------------------------------
5 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell
6
8 the terms of the
9  Eclipse Public License Version 1.0.
10
11 A copy of this license is included in the COPYING file of this distribution.
13 -------------------------------------------------------------------------- */
14 /*
15 $begin rev_hes_sparsity$$16 spell 17 Jacobian 18 Hessian 19 jac 20 hes 21 bool 22 const 23 rc 24 cpp 25$$ 26 27$section Reverse Mode Hessian Sparsity Patterns$$28 29 head Syntax$$
30 $icode%f%.rev_hes_sparsity( 31 %select_range%, %transpose%, %internal_bool%, %pattern_out% 32 )%$$33 34 head Purpose$$ 35 We use$latex F : \B{R}^n \rightarrow \B{R}^m$$to denote the 36 cref/AD function/glossary/AD Function/$$ corresponding to
37 the operation sequence stored in $icode f$$. 38 Fix latex R \in \B{R}^{n \times \ell}$$,$latex s \in \B{R}^m$$39 and define the function 40 latex $41 H(x) = ( s^\R{T} F )^{(2)} ( x ) R 42$$$
43 Given a $cref/sparsity pattern/glossary/Sparsity Pattern/$$for latex R$$ 44 and for the vector$latex s$$, 45 code rev_hes_sparsity$$ computes a sparsity pattern for $latex H(x)$$. 46 47 head x$$ 48 Note that the sparsity pattern$latex H(x)$$corresponds to the 49 operation sequence stored in icode f$$ and does not depend on
50 the argument $icode x$$. 51 52 head BoolVector$$ 53 The type$icode BoolVector$$is a cref SimpleVector$$ class with
54 $cref/elements of type/SimpleVector/Elements of Specified Type/$$55 code bool$$. 56 57$head SizeVector$$58 The type icode SizeVector$$ is a $cref SimpleVector$$class with 59 cref/elements of type/SimpleVector/Elements of Specified Type/$$ 60$code size_t$$. 61 62 head f$$
63 The object $icode f$$has prototype 64 codei% 65 ADFun<%Base%> %f% 66 %$$ 67 68$head R$$69 The sparsity pattern for the matrix latex R$$ is specified by
70 $cref/pattern_in/for_jac_sparsity/pattern_in/$$in the previous call 71 codei% 72 %f%.for_jac_sparsity( 73 %pattern_in%, %transpose%, %dependency%, %internal_bool%, %pattern_out% 74 )%$$ 75 76$head select_range$$77 The argument icode select_range$$ has prototype
78 $codei% 79 const %BoolVector%& %select_range% 80 %$$81 It has size latex m$$ and specifies which components of the vector 82$latex s$$are non-zero; i.e., icode%select_range%[%i%]%$$ is true
83 if and only if $latex s_i$$is possibly non-zero. 84 85 head transpose$$ 86 This argument has prototype 87$codei%
88  bool %transpose%
89 %$$90 See cref/pattern_out/rev_hes_sparsity/pattern_out/$$ below.
91
92 $head internal_bool$$93 If this is true, calculations are done with sets represented by a vector 94 of boolean values. Otherwise, a vector of sets of integers is used. 95 This must be the same as in the previous call to 96 icode%f%.for_jac_sparsity%$$. 97 98$head pattern_out$$99 This argument has prototype 100 codei% 101 sparse_rc<%SizeVector%>& %pattern_out% 102 %$$
103 This input value of $icode pattern_out$$does not matter. 104 If icode transpose$$ it is false (true), 105 upon return$icode pattern_out$$is a sparsity pattern for 106 latex H(x)$$ ($latex H(x)^\R{T}$$). 107 108 head Sparsity for Entire Hessian$$ 109 Suppose that$latex R$$is the latex n \times n$$ identity matrix.
110 In this case, $icode pattern_out$$is a sparsity pattern for 111 latex (s^\R{T} F) F^{(2)} ( x )$$. 112 113$head Example$$114 children% 115 example/sparse/rev_hes_sparsity.cpp 116 %$$
117 The file
118 $cref rev_hes_sparsity.cpp$$119 contains an example and test of this operation. 120 It returns true if it succeeds and false otherwise. 121 122$end
123 -----------------------------------------------------------------------------
124 */
127
129
130 /*!
131 Reverse Hessian sparsity patterns.
132
133 \tparam Base
134 is the base type for this recording.
135
136 \tparam BoolVector
137 is the simple vector with elements of type bool that is used for
138 sparsity for the vector s.
139
140 \tparam SizeVector
141 is the simple vector with elements of type size_t that is used for
142 row, column index sparsity patterns.
143
144 \param select_range
145 is a sparsity pattern for for s.
146
147 \param transpose
148 Is the returned sparsity pattern transposed.
149
150 \param internal_bool
151 If this is true, calculations are done with sets represented by a vector
152 of boolean values. Otherwise, a vector of standard sets is used.
153
154 \param pattern_out
155 The value of transpose is false (true),
156 the return value is a sparsity pattern for H(x) ( H(x)^T ) where
157 \f[
158  H(x) = R * F^{(1)} (x)
159 \f]
160 Here F is the function corresponding to the operation sequence
161 and x is any argument value.
162 */
163 template <class Base>
164 template <class BoolVector, class SizeVector>
166  const BoolVector& select_range ,
167  bool transpose ,
168  bool internal_bool ,
169  sparse_rc<SizeVector>& pattern_out )
170 { size_t n = Domain();
171  size_t m = Range();
172  //
174  size_t( select_range.size() ) == m,
175  "rev_hes_sparsity: size of select_range is not equal to "
176  "number of dependent variables"
177  );
178  //
179  // vector that holds reverse Jacobian sparsity flag
180  local::pod_vector<bool> rev_jac_pattern(num_var_tape_);
181  for(size_t i = 0; i < num_var_tape_; i++)
182  rev_jac_pattern[i] = false;
183  //
184  // initialize rev_jac_pattern for dependent variables
185  for(size_t i = 0; i < m; i++)
186  rev_jac_pattern[ dep_taddr_[i] ] = select_range[i];
187  //
188  //
189  if( internal_bool )
191  for_jac_sparse_pack_.n_set() > 0,
192  "rev_hes_sparsity: previous call to for_jac_sparsity did not "
193  "use bool for interanl sparsity patterns."
194  );
195  // column dimension of internal sparstiy pattern
196  size_t ell = for_jac_sparse_pack_.end();
197  //
198  // allocate memory for bool sparsity calculation
199  // (sparsity pattern is emtpy after a resize)
200  local::sparse_pack internal_hes;
201  internal_hes.resize(num_var_tape_, ell);
202  //
203  // compute the Hessian sparsity pattern
205  &play_,
206  n,
207  num_var_tape_,
208  for_jac_sparse_pack_,
209  rev_jac_pattern.data(),
210  internal_hes
211
212  );
213  // get sparstiy pattern for independent variables
215  transpose, ind_taddr_, internal_hes, pattern_out
216  );
217  }
218  else
220  for_jac_sparse_set_.n_set() > 0,
221  "rev_hes_sparsity: previous call to for_jac_sparsity did not "
222  "use bool for interanl sparsity patterns."
223  );
224  // column dimension of internal sparstiy pattern
225  size_t ell = for_jac_sparse_set_.end();
226  //
227  // allocate memory for bool sparsity calculation
228  // (sparsity pattern is emtpy after a resize)
229  local::sparse_list internal_hes;
230  internal_hes.resize(num_var_tape_, ell);
231  //
232  // compute the Hessian sparsity pattern
234  &play_,
235  n,
236  num_var_tape_,
237  for_jac_sparse_set_,
238  rev_jac_pattern.data(),
239  internal_hes
240
241  );
242  // get sparstiy pattern for independent variables
244  transpose, ind_taddr_, internal_hes, pattern_out
245  );
246  }
247  return;
248 }
249 } // END_CPPAD_NAMESPACE
250 # endif
void rev_hes_sparsity(const BoolVector &select_range, bool transpose, bool internal_bool, sparse_rc< SizeVector > &pattern_out)
Reverse Hessian sparsity patterns.
Check that exp is true, if not print msg and terminate execution.
Vector of sets of positive integers, each set stored as a singly linked list.
Definition: sparse_list.hpp:35
void get_internal_sparsity(bool transpose, const vector< size_t > &internal_index, const InternalSparsity &internal_pattern, sparse_rc< SizeVector > &pattern_out)
Get sparsity pattern for a sub-set of variables.
void rev_hes_sweep(const local::player< Base > *play, size_t n, size_t numvar, const Vector_set &for_jac_sparse, bool *RevJac, Vector_set &rev_hes_sparse)
Given the forward Jacobian sparsity pattern for all the variables, and the reverse Jacobian sparsity ...
Vector of sets of postivie integers, each set stored as a packed boolean array.
Definition: sparse_pack.hpp:33
sparsity pattern for a matrix with indices of type size_t
Definition: sparse_rc.hpp:212
Type * data(void)
current data pointer is no longer valid after any of the following: extend, erase, operator=, and ~pod_vector. Take extreem care when using this function.
Definition: pod_vector.hpp:89
void resize(size_t n_set, size_t end)
Start a new vector of sets.
File used to define the ADFun&lt;Base&gt; class.
Routines that enable code to be independent of which internal spasity pattern is used.
void resize(size_t n_set, size_t end)
Change number of sets, set end, and initialize all sets as empty.