CppAD: A C++ Algorithmic Differentiation Package  20171217
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
optimize.hpp
Go to the documentation of this file.
1 # ifndef CPPAD_CORE_OPTIMIZE_HPP
2 # define CPPAD_CORE_OPTIMIZE_HPP
3 
4 /* --------------------------------------------------------------------------
5 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell
6 
7 CppAD is distributed under multiple licenses. This distribution is under
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.
12 Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
13 -------------------------------------------------------------------------- */
14 
15 /*
16 $begin optimize$$
17 $spell
18  enum
19  jac
20  bool
21  Taylor
22  CppAD
23  cppad
24  std
25  const
26  onetape
27  op
28 $$
29 
30 $section Optimize an ADFun Object Tape$$
31 $mindex sequence operations speed memory NDEBUG$$
32 
33 
34 $head Syntax$$
35 $icode%f%.optimize()
36 %$$
37 $icode%f%.optimize(%options%)
38 %$$
39 
40 $head Purpose$$
41 The operation sequence corresponding to an $cref ADFun$$ object can
42 be very large and involve many operations; see the
43 size functions in $cref seq_property$$.
44 The $icode%f%.optimize%$$ procedure reduces the number of operations,
45 and thereby the time and the memory, required to
46 compute function and derivative values.
47 
48 $head f$$
49 The object $icode f$$ has prototype
50 $codei%
51  ADFun<%Base%> %f%
52 %$$
53 
54 $head options$$
55 This argument has prototype
56 $codei%
57  const std::string& %options%
58 %$$
59 The default for $icode options$$ is the empty string.
60 If it is present, it must consist of one or more of the options below
61 separated by a single space character.
62 
63 $subhead no_conditional_skip$$
64 The $code optimize$$ function can create conditional skip operators
65 to improve the speed of conditional expressions; see
66 $cref/optimize/CondExp/Optimize/$$.
67 If the sub-string $code no_conditional_skip$$ appears in $icode options$$,
68 conditional skip operations are not be generated.
69 This may make the optimize routine use significantly less memory
70 and take less time to optimize $icode f$$.
71 If conditional skip operations are generated,
72 it may save a significant amount of time when
73 using $icode f$$ for $cref forward$$ or $cref reverse$$ mode calculations;
74 see $cref number_skip$$.
75 
76 $subhead no_compare_op$$
77 If the sub-string $code no_compare_op$$ appears in $icode options$$,
78 comparison operators will be removed from the optimized function.
79 These operators are necessary for the
80 $cref compare_change$$ functions to be meaningful.
81 On the other hand, they are not necessary, and take extra time,
82 when the compare_change functions are not used.
83 
84 $subhead no_print_for_op$$
85 If the sub-string $code no_compare_op$$ appears in $icode options$$,
86 $cref PrintFor$$ operations will be removed form the optimized function.
87 These operators are useful for reporting problems evaluating derivatives
88 at independent variable values different from those used to record a function.
89 
90 $head Examples$$
91 $children%
92  example/optimize/forward_active.cpp
93  %example/optimize/reverse_active.cpp
94  %example/optimize/compare_op.cpp
95  %example/optimize/print_for.cpp
96  %example/optimize/conditional_skip.cpp
97  %example/optimize/nest_conditional.cpp
98  %example/optimize/cumulative_sum.cpp
99 %$$
100 $table
101 $cref/forward_active.cpp/optimize_forward_active.cpp/$$ $cnext
102  $title optimize_forward_active.cpp$$
103 $rnext
104 $cref/reverse_active.cpp/optimize_reverse_active.cpp/$$ $cnext
105  $title optimize_reverse_active.cpp$$
106 $rnext
107 $cref/compare_op.cpp/optimize_compare_op.cpp/$$ $cnext
108  $title optimize_compare_op.cpp$$
109 $rnext
110 $cref/print_for_op.cpp/optimize_print_for.cpp/$$ $cnext
111  $title optimize_print_for.cpp$$
112 $rnext
113 $cref/conditional_skip.cpp/optimize_conditional_skip.cpp/$$ $cnext
114  $title optimize_conditional_skip.cpp$$
115 $rnext
116 $cref/nest_conditional.cpp/optimize_nest_conditional.cpp/$$ $cnext
117  $title optimize_nest_conditional.cpp$$
118 $rnext
119 $cref/cumulative_sum.cpp/optimize_cumulative_sum.cpp/$$ $cnext
120  $title optimize_cumulative_sum.cpp$$
121 $tend
122 
123 $head Efficiency$$
124 If a $cref/zero order forward/forward_zero/$$ calculation is done during
125 the construction of $icode f$$, it will require more memory
126 and time than required after the optimization procedure.
127 In addition, it will need to be redone.
128 For this reason, it is more efficient to use
129 $codei%
130  ADFun<%Base%> %f%;
131  %f%.Dependent(%x%, %y%);
132  %f%.optimize();
133 %$$
134 instead of
135 $codei%
136  ADFun<%Base%> %f%(%x%, %y%)
137  %f%.optimize();
138 %$$
139 See the discussion about
140 $cref/sequence constructors/FunConstruct/Sequence Constructor/$$.
141 
142 $head Speed Testing$$
143 You can run the CppAD $cref/speed/speed_main/$$ tests and see
144 the corresponding changes in number of variables and execution time.
145 Note that there is an interaction between using
146 $cref/optimize/speed_main/Global Options/optimize/$$ and
147 $cref/onetape/speed_main/Global Options/onetape/$$.
148 If $icode onetape$$ is true and $icode optimize$$ is true,
149 the optimized tape will be reused many times.
150 If $icode onetape$$ is false and $icode optimize$$ is true,
151 the tape will be re-optimized for each test.
152 
153 $head Atomic Functions$$
154 There are some subtitle issue with optimized $cref atomic$$ functions
155 $latex v = g(u)$$:
156 
157 $subhead rev_sparse_jac$$
158 The $cref atomic_rev_sparse_jac$$ function is be used to determine
159 which components of $icode u$$ affect the dependent variables of $icode f$$.
160 For each atomic operation, the current
161 $cref/atomic_sparsity/atomic_option/atomic_sparsity/$$ setting is used
162 to determine if $code pack_sparsity_enum$$, $code bool_sparsity_enum$$,
163 or $code set_sparsity_enum$$ is used to determine dependency relations
164 between argument and result variables.
165 
166 $subhead nan$$
167 If $icode%u%[%i%]%$$ does not affect the value of
168 the dependent variables for $icode f$$,
169 the value of $icode%u%[%i%]%$$ is set to $cref nan$$.
170 
171 $head Checking Optimization$$
172 If $cref/NDEBUG/Faq/Speed/NDEBUG/$$ is not defined,
173 and $cref/f.size_order()/size_order/$$ is greater than zero,
174 a $cref forward_zero$$ calculation is done using the optimized version
175 of $icode f$$ and the results are checked to see that they are
176 the same as before.
177 If they are not the same, the
178 $cref ErrorHandler$$ is called with a known error message
179 related to $icode%f%.optimize()%$$.
180 
181 $end
182 -----------------------------------------------------------------------------
183 */
185 /*!
186 \file optimize.hpp
187 Optimize a player object operation sequence
188 */
189 namespace CppAD { // BEGIN_CPPAD_NAMESPACE
190 /*!
191 Optimize a player object operation sequence
192 
193 The operation sequence for this object is replaced by one with fewer operations
194 but the same funcition and derivative values.
195 
196 \tparam Base
197 base type for the operator; i.e., this operation was recorded
198 using AD<Base> and computations by this routine are done using type
199 \a Base.
200 
201 \param options
202 \li
203 If the sub-string "no_conditional_skip" appears,
204 conditional skip operations will not be generated.
205 This may make the optimize routine use significantly less memory
206 and take significantly less time.
207 \li
208 If the sub-string "no_compare_op" appears,
209 then comparison operators will be removed from the optimized tape.
210 These operators are necessary for the compare_change function to be
211 be meaningful in the resulting recording.
212 On the other hand, they are not necessary and take extra time
213 when compare_change is not used.
214 */
215 template <class Base>
216 void ADFun<Base>::optimize(const std::string& options)
217 { // place to store the optimized version of the recording
219 
220  // number of independent variables
221  size_t n = ind_taddr_.size();
222 
223 # ifndef NDEBUG
224  size_t i, j, m = dep_taddr_.size();
225  CppAD::vector<Base> x(n), y(m), check(m);
226  Base max_taylor(0);
227  bool check_zero_order = num_order_taylor_ > 0;
228  if( check_zero_order )
229  { // zero order coefficients for independent vars
230  for(j = 0; j < n; j++)
231  { CPPAD_ASSERT_UNKNOWN( play_.GetOp(j+1) == local::InvOp );
232  CPPAD_ASSERT_UNKNOWN( ind_taddr_[j] == j+1 );
233  x[j] = taylor_[ ind_taddr_[j] * cap_order_taylor_ + 0];
234  }
235  // zero order coefficients for dependent vars
236  for(i = 0; i < m; i++)
237  { CPPAD_ASSERT_UNKNOWN( dep_taddr_[i] < num_var_tape_ );
238  y[i] = taylor_[ dep_taddr_[i] * cap_order_taylor_ + 0];
239  }
240  // maximum zero order coefficient not counting BeginOp at beginning
241  // (which is correpsonds to uninitialized memory).
242  for(i = 1; i < num_var_tape_; i++)
243  { if( abs_geq(taylor_[i*cap_order_taylor_+0] , max_taylor) )
244  max_taylor = taylor_[i*cap_order_taylor_+0];
245  }
246  }
247 # endif
248 
249  // create the optimized recording
250  local::optimize::optimize_run<Base>(options, n, dep_taddr_, &play_, &rec);
251 
252  // number of variables in the recording
253  num_var_tape_ = rec.num_var_rec();
254 
255  // now replace the recording
256  play_.get(rec, n);
257 
258  // set flag so this function knows it has been optimized
259  has_been_optimized_ = true;
260 
261  // free memory allocated for sparse Jacobian calculation
262  // (the results are no longer valid)
263  for_jac_sparse_pack_.resize(0, 0);
264  for_jac_sparse_set_.resize(0,0);
265 
266  // free old Taylor coefficient memory
267  taylor_.clear();
268  num_order_taylor_ = 0;
269  cap_order_taylor_ = 0;
270 
271  // resize and initilaize conditional skip vector
272  // (must use player size because it now has the recoreder information)
273  cskip_op_.resize( play_.num_op_rec() );
274 
275  // resize subgraph_info_
276  subgraph_info_.resize(
277  ind_taddr_.size(), // n_ind
278  dep_taddr_.size(), // n_dep
279  play_.num_op_rec(), // n_op
280  play_.num_var_rec() // n_var
281  );
282 
283 # ifndef NDEBUG
284  if( check_zero_order )
285  {
286  // zero order forward calculation using new operation sequence
287  check = Forward(0, x);
288 
289  // check results
290  Base eps99 = Base(99) * CppAD::numeric_limits<Base>::epsilon();
291  for(i = 0; i < m; i++)
292  if( ! abs_geq( eps99 * max_taylor , check[i] - y[i] ) )
293  { std::string msg = "Error during check of f.optimize().";
294  msg += "\neps99 * max_taylor = " + to_string(eps99 * max_taylor);
295  msg += "\ncheck[i] = " + to_string(check[i]);
296  msg += "\ny[i] = " + to_string(y[i]);
298  abs_geq( eps99 * max_taylor , check[i] - y[i] ) ,
299  msg.c_str()
300  );
301  }
302 
303  // Erase memory that this calculation was done so NDEBUG gives
304  // same final state for this object (from users perspective)
305  num_order_taylor_ = 0;
306  }
307 # endif
308 }
309 
310 } // END_CPPAD_NAMESPACE
311 # endif
#define CPPAD_ASSERT_KNOWN(exp, msg)
Check that exp is true, if not print msg and terminate execution.
static Float epsilon(void)
machine epsilon
size_t num_var_rec(void) const
Number of variables currently stored in the recording.
Definition: recorder.hpp:136
bool abs_geq(const std::complex< double > &x, const std::complex< double > &y)
Class used to store an operation sequence while it is being recorded (the operation sequence is copie...
Definition: declare_ad.hpp:28
std::string to_string(const Type &value)
Definition: to_string.hpp:166
#define CPPAD_ASSERT_UNKNOWN(exp)
Check that exp is true, if not terminate execution.
Convert a player object to an optimized recorder object.
void optimize(const std::string &options="")
Optimize a player object operation sequence.
Definition: optimize.hpp:216