1 // $Id: sparse_binary_op.hpp 3865 2017-01-19 01:57:55Z bradbell $
2 # ifndef CPPAD_LOCAL_SPARSE_BINARY_OP_HPP
3 # define CPPAD_LOCAL_SPARSE_BINARY_OP_HPP
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 namespace CppAD { namespace local { // BEGIN_CPPAD_LOCAL_NAMESPACE
16 /*!
17 \file sparse_binary_op.hpp
18 Forward and reverse mode sparsity patterns for binary operators.
19 */
20
21
22 /*!
23 Forward mode Jacobian sparsity pattern for all binary operators.
24
25 The C++ source code corresponding to a binary operation has the form
26 \verbatim
27 z = fun(x, y)
28 \endverbatim
29 where fun is a C++ binary function and both x and y are variables,
30 or it has the form
31 \verbatim
32 z = x op y
33 \endverbatim
34 where op is a C++ binary unary operator and both x and y are variables.
35
36 \tparam Vector_set
37 is the type used for vectors of sets. It can be either
38 sparse_pack or sparse_list.
39
40 \param i_z
41 variable index corresponding to the result for this operation;
42 i.e., z.
43
44 \param arg
45 \a arg[0]
46 variable index corresponding to the left operand for this operator;
47 i.e., x.
48 \n
49 \n arg[1]
50 variable index corresponding to the right operand for this operator;
51 i.e., y.
52
53 \param sparsity
54 \b Input:
55 The set with index \a arg[0] in \a sparsity
56 is the sparsity bit pattern for x.
57 This identifies which of the independent variables the variable x
58 depends on.
59 \n
60 \n
61 \b Input:
62 The set with index \a arg[1] in \a sparsity
63 is the sparsity bit pattern for y.
64 This identifies which of the independent variables the variable y
65 depends on.
66 \n
67 \n
68 \b Output:
69 The set with index \a i_z in \a sparsity
70 is the sparsity bit pattern for z.
71 This identifies which of the independent variables the variable z
72 depends on.
73
74 \par Checked Assertions:
75 \li \a arg[0] < \a i_z
76 \li \a arg[1] < \a i_z
77 */
78
79 template <class Vector_set>
forward_sparse_jacobian_binary_op(size_t i_z,const addr_t * arg,Vector_set & sparsity)80 inline void forward_sparse_jacobian_binary_op(
81 size_t i_z ,
82 const addr_t* arg ,
83 Vector_set& sparsity )
84 {
85 // check assumptions
86 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
87 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
88
89 sparsity.binary_union(i_z, arg[0], arg[1], sparsity);
90
91 return;
92 }
93
94 /*!
95 Reverse mode Jacobian sparsity pattern for all binary operators.
96
97 The C++ source code corresponding to a unary operation has the form
98 \verbatim
99 z = fun(x, y)
100 \endverbatim
101 where fun is a C++ unary function and x and y are variables,
102 or it has the form
103 \verbatim
104 z = x op y
105 \endverbatim
106 where op is a C++ bianry operator and x and y are variables.
107
108 This routine is given the sparsity patterns
109 for a function G(z, y, x, ... )
110 and it uses them to compute the sparsity patterns for
111 \verbatim
112 H( y, x, w , u , ... ) = G[ z(x,y) , y , x , w , u , ... ]
113 \endverbatim
114
115 \tparam Vector_set
116 is the type used for vectors of sets. It can be either
117 sparse_pack or sparse_list.
118
119 \param i_z
120 variable index corresponding to the result for this operation;
121 i.e., z.
122
123 \param arg
124 \a arg[0]
125 variable index corresponding to the left operand for this operator;
126 i.e., x.
127
128 \n
129 \n arg[1]
130 variable index corresponding to the right operand for this operator;
131 i.e., y.
132
133 \param sparsity
134 The set with index \a i_z in \a sparsity
135 is the sparsity pattern for z corresponding ot the function G.
136 \n
137 \n
138 The set with index \a arg[0] in \a sparsity
139 is the sparsity pattern for x.
140 On input, it corresponds to the function G,
141 and on output it corresponds to H.
142 \n
143 \n
144 The set with index \a arg[1] in \a sparsity
145 is the sparsity pattern for y.
146 On input, it corresponds to the function G,
147 and on output it corresponds to H.
148 \n
149 \n
150
151 \par Checked Assertions:
152 \li \a arg[0] < \a i_z
153 \li \a arg[1] < \a i_z
154 */
155 template <class Vector_set>
reverse_sparse_jacobian_binary_op(size_t i_z,const addr_t * arg,Vector_set & sparsity)156 inline void reverse_sparse_jacobian_binary_op(
157 size_t i_z ,
158 const addr_t* arg ,
159 Vector_set& sparsity )
160 {
161 // check assumptions
162 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
163 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
164
165 sparsity.binary_union(arg[0], arg[0], i_z, sparsity);
166 sparsity.binary_union(arg[1], arg[1], i_z, sparsity);
167
168 return;
169 }
170 // ---------------------------------------------------------------------------
171 /*!
172 Reverse mode Hessian sparsity pattern for add and subtract operators.
173
174 The C++ source code corresponding to a unary operation has the form
175 \verbatim
176 z = x op y
177 \endverbatim
178 where op is + or - and x, y are variables.
179
180 \copydetails CppAD::local::reverse_sparse_hessian_binary_op
181 */
182 template <class Vector_set>
reverse_sparse_hessian_addsub_op(size_t i_z,const addr_t * arg,bool * jac_reverse,const Vector_set & for_jac_sparsity,Vector_set & rev_hes_sparsity)183 inline void reverse_sparse_hessian_addsub_op(
184 size_t i_z ,
185 const addr_t* arg ,
186 bool* jac_reverse ,
187 const Vector_set& for_jac_sparsity ,
188 Vector_set& rev_hes_sparsity )
189 {
190 // check assumptions
191 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
192 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
193
194 rev_hes_sparsity.binary_union(arg[0], arg[0], i_z, rev_hes_sparsity);
195 rev_hes_sparsity.binary_union(arg[1], arg[1], i_z, rev_hes_sparsity);
196
197 jac_reverse[arg[0]] |= jac_reverse[i_z];
198 jac_reverse[arg[1]] |= jac_reverse[i_z];
199
200 return;
201 }
202
203 /*!
204 Reverse mode Hessian sparsity pattern for multiplication operator.
205
206 The C++ source code corresponding to a unary operation has the form
207 \verbatim
208 z = x * y
209 \endverbatim
210 where x and y are variables.
211
212 \copydetails CppAD::local::reverse_sparse_hessian_binary_op
213 */
214 template <class Vector_set>
reverse_sparse_hessian_mul_op(size_t i_z,const addr_t * arg,bool * jac_reverse,const Vector_set & for_jac_sparsity,Vector_set & rev_hes_sparsity)215 inline void reverse_sparse_hessian_mul_op(
216 size_t i_z ,
217 const addr_t* arg ,
218 bool* jac_reverse ,
219 const Vector_set& for_jac_sparsity ,
220 Vector_set& rev_hes_sparsity )
221 {
222 // check assumptions
223 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
224 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
225
226 rev_hes_sparsity.binary_union(arg[0], arg[0], i_z, rev_hes_sparsity);
227 rev_hes_sparsity.binary_union(arg[1], arg[1], i_z, rev_hes_sparsity);
228
229 if( jac_reverse[i_z] )
230 { rev_hes_sparsity.binary_union(
231 arg[0], arg[0], arg[1], for_jac_sparsity);
232 rev_hes_sparsity.binary_union(
233 arg[1], arg[1], arg[0], for_jac_sparsity);
234 }
235
236 jac_reverse[arg[0]] |= jac_reverse[i_z];
237 jac_reverse[arg[1]] |= jac_reverse[i_z];
238 return;
239 }
240
241 /*!
242 Reverse mode Hessian sparsity pattern for division operator.
243
244 The C++ source code corresponding to a unary operation has the form
245 \verbatim
246 z = x / y
247 \endverbatim
248 where x and y are variables.
249
250 \copydetails CppAD::local::reverse_sparse_hessian_binary_op
251 */
252 template <class Vector_set>
reverse_sparse_hessian_div_op(size_t i_z,const addr_t * arg,bool * jac_reverse,const Vector_set & for_jac_sparsity,Vector_set & rev_hes_sparsity)253 inline void reverse_sparse_hessian_div_op(
254 size_t i_z ,
255 const addr_t* arg ,
256 bool* jac_reverse ,
257 const Vector_set& for_jac_sparsity ,
258 Vector_set& rev_hes_sparsity )
259 {
260 // check assumptions
261 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
262 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
263
264 rev_hes_sparsity.binary_union(arg[0], arg[0], i_z, rev_hes_sparsity);
265 rev_hes_sparsity.binary_union(arg[1], arg[1], i_z, rev_hes_sparsity);
266
267 if( jac_reverse[i_z] )
268 { rev_hes_sparsity.binary_union(
269 arg[0], arg[0], arg[1], for_jac_sparsity);
270 rev_hes_sparsity.binary_union(
271 arg[1], arg[1], arg[0], for_jac_sparsity);
272 rev_hes_sparsity.binary_union(
273 arg[1], arg[1], arg[1], for_jac_sparsity);
274 }
275
276 jac_reverse[arg[0]] |= jac_reverse[i_z];
277 jac_reverse[arg[1]] |= jac_reverse[i_z];
278 return;
279 }
280
281 /*!
282 Reverse mode Hessian sparsity pattern for power function.
283
284 The C++ source code corresponding to a unary operation has the form
285 \verbatim
286 z = pow(x, y)
287 \endverbatim
288 where x and y are variables.
289
290 \copydetails CppAD::local::reverse_sparse_hessian_binary_op
291 */
292 template <class Vector_set>
reverse_sparse_hessian_pow_op(size_t i_z,const addr_t * arg,bool * jac_reverse,const Vector_set & for_jac_sparsity,Vector_set & rev_hes_sparsity)293 inline void reverse_sparse_hessian_pow_op(
294 size_t i_z ,
295 const addr_t* arg ,
296 bool* jac_reverse ,
297 const Vector_set& for_jac_sparsity ,
298 Vector_set& rev_hes_sparsity )
299 {
300 // check assumptions
301 CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < i_z );
302 CPPAD_ASSERT_UNKNOWN( size_t(arg[1]) < i_z );
303
304 rev_hes_sparsity.binary_union(arg[0], arg[0], i_z, rev_hes_sparsity);
305 rev_hes_sparsity.binary_union(arg[1], arg[1], i_z, rev_hes_sparsity);
306
307 if( jac_reverse[i_z] )
308 {
309 rev_hes_sparsity.binary_union(
310 arg[0], arg[0], arg[0], for_jac_sparsity);
311 rev_hes_sparsity.binary_union(
312 arg[0], arg[0], arg[1], for_jac_sparsity);
313
314 rev_hes_sparsity.binary_union(
315 arg[1], arg[1], arg[0], for_jac_sparsity);
316 rev_hes_sparsity.binary_union(
317 arg[1], arg[1], arg[1], for_jac_sparsity);
318 }
319
320 // I cannot think of a case where this is necessary, but it including
321 // it makes it like the other cases.
322 jac_reverse[arg[0]] |= jac_reverse[i_z];
323 jac_reverse[arg[1]] |= jac_reverse[i_z];
324 return;
325 }
326 // ---------------------------------------------------------------------------
327 /*!
328 Forward mode Hessian sparsity pattern for multiplication operator.
329
330 The C++ source code corresponding to this operation is
331 \verbatim
332 w(x) = v0(x) * v1(x)
333 \endverbatim
334
335 \param arg
336 is the index of the argument vector for the multiplication operation; i.e.,
337 arg[0], arg[1] are the left and right operands.
338
339 \param for_jac_sparsity
340 for_jac_sparsity(arg[0]) constains the Jacobian sparsity for v0(x),
341 for_jac_sparsity(arg[1]) constains the Jacobian sparsity for v1(x).
342
343 \param for_hes_sparsity
344 On input, for_hes_sparsity includes the Hessian sparsity for v0(x)
345 and v1(x); i.e., the sparsity can be a super set.
346 Upon return it includes the Hessian sparsity for w(x)
347 */
348 template <class Vector_set>
forward_sparse_hessian_mul_op(const addr_t * arg,const Vector_set & for_jac_sparsity,Vector_set & for_hes_sparsity)349 inline void forward_sparse_hessian_mul_op(
350 const addr_t* arg ,
351 const Vector_set& for_jac_sparsity ,
352 Vector_set& for_hes_sparsity )
353 { // --------------------------------------------------
354 // set of independent variables that v0 depends on
355 typename Vector_set::const_iterator itr_0(for_jac_sparsity, arg[0]);
356
357 // loop over dependent variables with non-zero partial
358 size_t i_x = *itr_0;
359 while( i_x < for_jac_sparsity.end() )
360 { // N(i_x) = N(i_x) union L(v1)
361 for_hes_sparsity.binary_union(i_x, i_x, arg[1], for_jac_sparsity);
362 i_x = *(++itr_0);
363 }
364 // --------------------------------------------------
365 // set of independent variables that v1 depends on
366 typename Vector_set::const_iterator itr_1(for_jac_sparsity, arg[1]);
367
368 // loop over dependent variables with non-zero partial
369 i_x = *itr_1;
370 while( i_x < for_jac_sparsity.end() )
371 { // N(i_x) = N(i_x) union L(v0)
372 for_hes_sparsity.binary_union(i_x, i_x, arg[0], for_jac_sparsity);
373 i_x = *(++itr_1);
374 }
375 return;
376 }
377 /*!
378 Forward mode Hessian sparsity pattern for division operator.
379
380 The C++ source code corresponding to this operation is
381 \verbatim
382 w(x) = v0(x) / v1(x)
383 \endverbatim
384
385 \param arg
386 is the index of the argument vector for the division operation; i.e.,
387 arg[0], arg[1] are the left and right operands.
388
389 \param for_jac_sparsity
390 for_jac_sparsity(arg[0]) constains the Jacobian sparsity for v0(x),
391 for_jac_sparsity(arg[1]) constains the Jacobian sparsity for v1(x).
392
393 \param for_hes_sparsity
394 On input, for_hes_sparsity includes the Hessian sparsity for v0(x)
395 and v1(x); i.e., the sparsity can be a super set.
396 Upon return it includes the Hessian sparsity for w(x)
397 */
398 template <class Vector_set>
forward_sparse_hessian_div_op(const addr_t * arg,const Vector_set & for_jac_sparsity,Vector_set & for_hes_sparsity)399 inline void forward_sparse_hessian_div_op(
400 const addr_t* arg ,
401 const Vector_set& for_jac_sparsity ,
402 Vector_set& for_hes_sparsity )
403 { // --------------------------------------------------
404 // set of independent variables that v0 depends on
405 typename Vector_set::const_iterator itr_0(for_jac_sparsity, arg[0]);
406
407 // loop over dependent variables with non-zero partial
408 size_t i_x = *itr_0;
409 while( i_x < for_jac_sparsity.end() )
410 { // N(i_x) = N(i_x) union L(v1)
411 for_hes_sparsity.binary_union(i_x, i_x, arg[1], for_jac_sparsity);
412 i_x = *(++itr_0);
413 }
414 // --------------------------------------------------
415 // set of independent variables that v1 depends on
416 typename Vector_set::const_iterator itr_1(for_jac_sparsity, arg[1]);
417
418 // loop over dependent variables with non-zero partial
419 i_x = *itr_1;
420 while( i_x < for_jac_sparsity.end() )
421 { // N(i_x) = N(i_x) union L(v0)
422 for_hes_sparsity.binary_union(i_x, i_x, arg[0], for_jac_sparsity);
423 // N(i_x) = N(i_x) union L(v1)
424 for_hes_sparsity.binary_union(i_x, i_x, arg[1], for_jac_sparsity);
425 i_x = *(++itr_1);
426 }
427 return;
428 }
429 /*!
430 Forward mode Hessian sparsity pattern for power operator.
431
432 The C++ source code corresponding to this operation is
433 \verbatim
434 w(x) = pow( v0(x) , v1(x) )
435 \endverbatim
436
437 \param arg
438 is the index of the argument vector for the power operation; i.e.,
439 arg[0], arg[1] are the left and right operands.
440
441 \param for_jac_sparsity
442 for_jac_sparsity(arg[0]) constains the Jacobian sparsity for v0(x),
443 for_jac_sparsity(arg[1]) constains the Jacobian sparsity for v1(x).
444
445 \param for_hes_sparsity
446 On input, for_hes_sparsity includes the Hessian sparsity for v0(x)
447 and v1(x); i.e., the sparsity can be a super set.
448 Upon return it includes the Hessian sparsity for w(x)
449 */
450 template <class Vector_set>
forward_sparse_hessian_pow_op(const addr_t * arg,const Vector_set & for_jac_sparsity,Vector_set & for_hes_sparsity)451 inline void forward_sparse_hessian_pow_op(
452 const addr_t* arg ,
453 const Vector_set& for_jac_sparsity ,
454 Vector_set& for_hes_sparsity )
455 { // --------------------------------------------------
456 // set of independent variables that v0 depends on
457 typename Vector_set::const_iterator itr_0(for_jac_sparsity, arg[0]);
458
459 // loop over dependent variables with non-zero partial
460 size_t i_x = *itr_0;
461 while( i_x < for_jac_sparsity.end() )
462 { // N(i_x) = N(i_x) union L(v0)
463 for_hes_sparsity.binary_union(i_x, i_x, arg[0], for_jac_sparsity);
464 // N(i_x) = N(i_x) union L(v1)
465 for_hes_sparsity.binary_union(i_x, i_x, arg[1], for_jac_sparsity);
466 i_x = *(++itr_0);
467 }
468 // --------------------------------------------------
469 // set of independent variables that v1 depends on
470 typename Vector_set::const_iterator itr_1(for_jac_sparsity, arg[1]);
471
472 // loop over dependent variables with non-zero partial
473 i_x = *itr_1;
474 while( i_x < for_jac_sparsity.end() )
475 { // N(i_x) = N(i_x) union L(v0)
476 for_hes_sparsity.binary_union(i_x, i_x, arg[0], for_jac_sparsity);
477 // N(i_x) = N(i_x) union L(v1)
478 for_hes_sparsity.binary_union(i_x, i_x, arg[1], for_jac_sparsity);
479 i_x = *(++itr_1);
480 }
481 return;
482 }
483 // ---------------------------------------------------------------------------
484 } } // END_CPPAD_LOCAL_NAMESPACE
485 # endif
486