CppAD: A C++ Algorithmic Differentiation Package  20171217
subgraph_reverse.hpp
Go to the documentation of this file.
3 /* --------------------------------------------------------------------------
5
7 the terms of the
8  Eclipse Public License Version 1.0.
9
10 A copy of this license is included in the COPYING file of this distribution.
12 -------------------------------------------------------------------------- */
13 /*
14 $begin subgraph_reverse$$15 spell 16 resize 17 subgraph 18 Subgraphs 19 dw 20 Taylor 21 Bool 22 const 23$$ 24 25$section Reverse Mode Using Subgraphs$$26 27 head Syntax$$
28 $icode%f%.subgraph_reverse(%select_domain%) 29 %$$30 icode%f%.subgraph_reverse(%q%, %ell%, %col%, %dw%) 31 %$$ 32 33$head Purpose$$34 We use latex F : B^n \rightarrow B^m$$ to denote the
35 $cref/AD function/glossary/AD Function/$$corresponding to icode f$$. 36 Reverse mode computes the derivative of the$cref Forward$$mode 37 cref/Taylor coefficients/glossary/Taylor Coefficient/$$
38 with respect to the domain variable $latex x$$. 39 40 head Notation$$ 41 We use the reverse mode 42$cref/notation/reverse_any/Notation/$$with the following change: 43 the vector 44 cref/w^(k)/reverse_any/Notation/w^(k)/$$ is defined
45 $latex $46 w_i^{(k)} = \left\{ \begin{array}{ll} 47 1 & {\rm if} \; k = q-1 \; \R{and} \; i = \ell 48 \\ 49 0 & {\rm otherwise} 50 \end{array} \right. 51$ $$52 53 head BaseVector$$ 54 The type$icode BaseVector$$must be a cref SimpleVector$$ class with
55 $cref/elements of type/SimpleVector/Elements of Specified Type/$$56 icode Base$$. 57 The routine$cref CheckSimpleVector$$will generate an error message 58 if this is not the case. 59 60 head BoolVector$$
61 The type $icode BoolVector$$is a cref SimpleVector$$ class with 62$cref/elements of type/SimpleVector/Elements of Specified Type/$$63 code bool$$.
64
65 $head SizeVector$$66 The type icode SizeVector$$ is a$cref SimpleVector$$class with 67 cref/elements of type/SimpleVector/Elements of Specified Type/$$
68 $code size_t$$. 69 70 head select_domain$$ 71 The argument$icode select_domain$$has prototype 72 codei% 73 const %BoolVector%& %select_domain% 74 %$$
75 It has size $latex n$$and specifies which independent variables 76 to include in the calculation. 77 If icode%select_domain%[%j%]%$$ is false, 78 it is assumed that$latex u^{(k)}_j = 0$$for latex k > 0$$; i.e.,
79 the $th j$$component of the Taylor coefficient for latex x$$, 80 with order greater that zero, are zero; see 81$cref/u^(k)/reverse_any/Notation/u^(k)/$$. 82 83 head q$$
84 The argument $icode q$$has prototype 85 codei% 86 size_t %q% 87 %$$ 88 and specifies the number of Taylor coefficient orders to be differentiated. 89 90$head ell$$91 The argument icode ell$$ has prototype
92 $codei% 93 size_t %ell% 94 %$$95 and specifies the dependent variable index that we are computing 96 the derivatives for; i.e. latex \ell$$. 97 This index can only be used once per, and after, a call that selects 98 the independent variables using$icode select_domain$$. 99 100 head col$$
101 This argument $icode col$$has prototype 102 codei% 103 %SizeVector% %col% 104 %$$ 105 The input size and value of its elements do not matter. 106 The$icode%col%.resize%$$member function is used to change its size 107 to the number the number of possible non-zero derivative components. 108 For each icode c$$,
109 $codei% 110 %select_domain%[ %col%[%c%] ] == true 111 %col%[%c%+1] >= %col%[%c%] 112 %$$113 and the derivative with respect to the th j$$ independent 114 variable is possibly non-zero where 115$icode%j% = %col%[%c%]%$$. 116 117 head dw$$
118 The argument $icode dw$$has prototype 119 codei% 120 %Vector% %dw% 121 %$$ 122 Its input size and value does not matter. 123 Upon return, 124 it is a vector with size$latex n \times q$$. 125 For latex c = 0 , \ldots , %col%.size()-1$$,
126 and $latex k = 0, \ldots , q-1$$, 127 latex $128 dw[ j * q + k ] = W^{(1)} ( x )_{j,k} 129$$$ 130 is the derivative of the specified Taylor coefficients w.r.t the$th j$$131 independent variable where icode%j% = %col%[%c%]%$$.
132 Note that this corresponds to the $cref reverse_any$$convention when 133 cref/w/reverse_any/w/$$ has size$icode%m% * %q%$$. 134 135 head Example$$
136 $children% 137 example/sparse/subgraph_reverse.cpp 138 %$$139 The file 140 cref subgraph_reverse.cpp$$ 141 contains an example and test of this operation. 142 It returns true if it succeeds and false otherwise. 143 144$end
145 */
147 /*!
148 \file subgraph_reverse.hpp
149 Compute derivatvies using reverse mode and subgraphs.
150 */
151
152 /*!
153 Initialize reverse mode derivative computation on subgraphs.
154
155 \param select_domain
156 is a vector with size equal to the dimension of the domain for this function.
157 Only derivatives w.r.t. the components that are true will be computed.
158
159 \par subgraph_info_.map_user_op()
160 If the input size of this vector is zero,
161 its value for this player (play_) is computed.
162
163 \par subgraph_info.in_subgraph_
164 This vector is initialized for a reverse mode computation on subgraphs.
165
166 \par subgraph_info.select_domain()
167 This vector is set equal to the select_domain argument.
168
169 \par subgraph_info.process_range()
170 This vector is initialized to have size Range() and its elements are false.
171 */
172
173 template <typename Base>
174 template <typename VectorBool>
175 void ADFun<Base>::subgraph_reverse( const VectorBool& select_domain )
176 { using local::pod_vector;
177
180  );
182  size_t( select_domain.size() ) == subgraph_info_.n_ind()
183  );
184
185  // map_user_op
186  if( subgraph_info_.map_user_op().size() == 0 )
187  subgraph_info_.set_map_user_op(&play_);
188  else
190  }
192  subgraph_info_.map_user_op().size() == play_.num_op_rec()
193  );
194
195  // initialize for reverse mode subgraph computations
196  subgraph_info_.init_rev(&play_, select_domain);
198  subgraph_info_.in_subgraph().size() == play_.num_op_rec()
199  );
200
201  return;
202 }
203
204
205 /*!
206 Use reverse mode to compute derivative of Taylor coefficients on a subgraph.
207
208 The function
209 \f$X : {\bf R} \times {\bf R}^{n \times q} \rightarrow {\bf R} \f$
210 is defined by
211 \f[
212 X(t , u) = \sum_{k=0}^{q-1} u^{(k)} t^k
213 \f]
214 The function
215 \f$Y : {\bf R} \times {\bf R}^{n \times q} \rightarrow {\bf R} \f$
216 is defined by
217 \f[
218 Y(t , u) = F[ X(t, u) ]
219 \f]
220 The function
221 \f$W : {\bf R}^{n \times q} \rightarrow {\bf R} \f$ is defined by
222 \f[
223 W(u) = \sum_{k=0}^{q-1} ( w^{(k)} )^{\rm T}
224 \frac{1}{k !} \frac{ \partial^k } { t^k } Y(0, u)
225 \f]
226
227 \param q
228 is the number of Taylor coefficient we are differentiating.
229
230 \param ell
231 is the component of the range that is selected for differentiation.
232
233 \param col
234 is the set of indices j = col[c] where the return value is defined.
235 If an index j is not in col, then either its derivative is zero,
236 or it is not in select_domain.
237
238 \param dw
239 Is a vector \f$dw \f$ such that
240 for j = col[c],
241 \f$k = 0 , \ldots , q-1 \f$
242 \f[
243  dw[ j * q + k ] = W^{(1)} ( x )_{j,k}
244 \f]
245 where the matrix \f$x \f$ is the value for \f$u \f$
246 that corresponding to the forward mode Taylor coefficients
247 for the independent variables as specified by previous calls to Forward.
248
249 \par subgraph_info.process_range()
250 The element process_range[ell] is set to true by this operation.
251
252 \par subgraph_info.in_subgraph_
253 some of the elements of this vector are set to have value ell
254 (so it can not longer be used to determine the subgraph corresponding to
255 the ell-th dependent variable).
256 */
257 template <typename Base>
258 template <typename VectorBase, typename SizeVector>
260  size_t q ,
261  size_t ell ,
262  SizeVector& col ,
263  VectorBase& dw )
264 { using local::pod_vector;
265
266  // check VectorBase is Simple Vector class with Base type elements
267  CheckSimpleVector<Base, VectorBase>();
269  q > 0,
270  "The second argument to Reverse must be greater than zero."
271  );
273  num_order_taylor_ >= q,
274  "Less than q Taylor coefficients are currently stored"
275  " in this ADFun object."
276  );
278  num_direction_taylor_ == 1,
279  "reverse mode for Forward(q, r, xq) with more than one direction"
280  "\n(r > 1) is not yet supported."
281  );
284  "dependent variable index in to large for this function"
285  );
287  subgraph_info_.process_range()[ell] == false,
288  "This dependent variable index has already been processed\n"
289  "after the previous subgraph_reverse(select_domain)."
290  );
291
292  // subgraph of operators connected to dependent variable ell
294  subgraph_info_.get_rev(
296  );
297
298  // Add all the atomic function call operators
299  // for calls that have first operator in the subgraph
300  local::subgraph::entire_call(&play_, subgraph);
301
302  // sort the subgraph
303  std::sort( subgraph.data(), subgraph.data() + subgraph.size() );
304
305  /*
306  // Use this printout for debugging
307  std::cout << "{ ";
308  for(size_t k = 0; k < subgraph.size(); k++)
309  { if( k > 0 )
310  std::cout << ", ";
311  std::cout << subgraph[k];
312  }
313  std::cout << "}\n";
314  */
315
316  // initialize subgraph_partial_ matrix to zero on subgraph
317  Base zero(0);
318  subgraph_partial_.resize(num_var_tape_ * q);
319  for(size_t k = 0; k < subgraph.size(); ++k)
320  {
321  size_t i_op = size_t( subgraph[k] );
322  local::OpCode op;
324  size_t i_var;
325  play_.get_op_info(i_op, op, arg, i_var);
326  if( NumRes(op) == 0 )
328  op == local::UserOp ||
329  op == local::UsrapOp ||
330  op == local::UsravOp ||
331  op == local::UsrrpOp
332  );
333  }
334  else
335  { CPPAD_ASSERT_UNKNOWN( i_var >= NumRes(op) );
336  size_t j_var = i_var + 1 - NumRes(op);
337  for(size_t i = j_var; i <= i_var; ++i)
338  { for(size_t j = 0; j < q; ++j)
339  subgraph_partial_[i * q + j] = zero;
340  }
341  }
342  }
343
344  // set partial to one for component we are differentiating
345  subgraph_partial_[ dep_taddr_[ell] * q + q - 1] = Base(1);
346
347  // evaluate the derivatives
348  CPPAD_ASSERT_UNKNOWN( cskip_op_.size() == play_.num_op_rec() );
350  size_t n = Domain();
352  q - 1,
353  n,
354  num_var_tape_,
355  &play_,
356  cap_order_taylor_,
357  taylor_.data(),
358  q,
359  subgraph_partial_.data(),
360  cskip_op_.data(),
362  subgraph
363  );
364
365  // number of non-zero in return value
366  size_t col_size = 0;
367  size_t subgraph_index = 0;
368  while( subgraph_index < subgraph.size() )
369  { // check for InvOp
370  if( subgraph[subgraph_index] > addr_t(n) )
371  subgraph_index = subgraph.size();
372  else
373  { ++col_size;
374  ++subgraph_index;
375  }
376  }
377  col.resize(col_size);
378
379  // return the derivative values
380  dw.resize(n * q);
381  for(size_t c = 0; c < col_size; ++c)
382  { size_t i_op = subgraph[c];
383  CPPAD_ASSERT_UNKNOWN( play_.GetOp(i_op) == local::InvOp );
384  //
385  size_t j = i_op - 1;
387  //
388  // return paritial for this independent variable
389  col[c] = j;
390  for(size_t k = 0; k < q; k++)
391  dw[j * q + k ] = subgraph_partial_[ind_taddr_[j] * q + k];
392  }
393  //
394  CPPAD_ASSERT_KNOWN( ! ( hasnan(dw) && check_for_nan_ ) ,
395  "f.subgraph_reverse(dw, q, ell): dw has a nan,\n"
396  "but none of f's Taylor coefficents are nan."
397  );
398  //
399  return;
400 }
401
403 # endif
Check that exp is true, if not print msg and terminate execution.
A vector class with Type element that does not use element constructors or destructors when Type is P...
Definition: pod_vector.hpp:34
size_t NumRes(OpCode op)
Number of variables resulting from the specified operation.
Definition: op_code.hpp:281
void entire_call(const player< Base > *play, pod_vector< addr_t > &subgraph)
Convert from just firt UserOp to entire atomic function call in a subgraph.
Definition: entire_call.hpp:39
OpCode
Type used to distinguish different AD&lt; Base &gt; atomic operations.
Definition: op_code.hpp:49
bool hasnan(const Vector &v)
Definition: nan.hpp:174