source: trunk/cppad/example/eigen_cholesky.hpp @ 3941

Last change on this file since 3941 was 3941, checked in by bradbell, 2 years ago

merge to branch: trunk
from repository: https://github.com/coin-or/CppAD
start hash code: b7056a15a1028d7be587b70a3ecc44b1f42dc05e
end hash code: c8c4cc081accff3628e7e66370ec01e4c99afe8d

commit c8c4cc081accff3628e7e66370ec01e4c99afe8d
Author: Brad Bell <bradbell@…>
Date: Thu Jun 1 23:16:39 2017 -0600

Changes automatically generated by the autotools.

commit f4392bc3eee8f6d0ccd45a0bb3be51181e211680
Author: Brad Bell <bradbell@…>
Date: Thu Jun 1 23:11:56 2017 -0600

  1. Add colpack_jac.cpp example (rename colpack_jac.cpp->colpack_jacobian.cpp).
  2. Add colpack_hescpp example (rename colpack_hes.cpp->colpack_hessian.cpp).


test_one.sh.in: adapt to using test_boolofvoid for testing.
sparse_hes.hpp: fix bug in cppad.symmetric case.

commit 086b8a8709b0c9cb01ce2cf8bc7910e903105ff7
Author: Brad Bell <bradbell@…>
Date: Thu Jun 1 08:54:59 2017 -0600

  1. Fix bug in use of colpack (see kludge in comments).
  2. Fix colpack.symmetric (not general) and add colpack.general.
  3. Deprecate colpack.star.
  4. More autotools from install to deprecated.
  5. Advance to cppad-20170601.

commit 23f26c060648f5c6fc62a1598c659aeccc5ca46f
Author: Brad Bell <bradbell@…>
Date: Tue May 30 08:14:04 2017 -0700

Advance to cppad-20170530.

commit 97f8c08509865d1bfb7ec2e5cd557ddc979f8412
Author: Brad Bell <bradbell@…>
Date: Tue May 30 07:38:47 2017 -0700

debug_rel branch:
There is a problem with speed sparse_hessian debug that goes back to master.
Supresss debug in cppad speed tests until it is fixed.

commit 39ea0d7d9c041784ccd26ce80d19a7ab02752818
Author: Brad Bell <bradbell@…>
Date: Mon May 29 22:34:22 2017 -0700

debug_rel branch:
run_cmake.sh: fix debug_none case.
CMakeLists.txt: use cppad_debug_which to determine debug or release.
CMakeLists.txt: let set_compile_flags determkine build type.

commit 191553e54dca407207789cf0d7c6c27fe6188775
Author: Brad Bell <bradbell@…>
Date: Mon May 29 19:53:08 2017 -0700

debug_rel branch:
Use set_compile_flags in introduction.

commit fba276a84e58d9a0d0944168d5706b7446beb32c
Author: Brad Bell <bradbell@…>
Date: Mon May 29 19:46:30 2017 -0700

debug_rel branch:
Use set_compile_flags in eample/multi_thread subdirectories.

commit 66c8cdb266fa3af29b211b8c870a3aed7a13b021
Author: Brad Bell <bradbell@…>
Date: Mon May 29 18:56:48 2017 -0700

debug_rel branch:
Use set_compile_flags in speed directory.

commit c431b15ee7714d3106234bc527ba2f9a836750e1
Author: Brad Bell <bradbell@…>
Date: Mon May 29 18:36:51 2017 -0700

debug_rel branch:
Convert cppad_ipopt to use set_compile_flags and cppad_debug_which.


CMakeLists.txt: alwasy compile for release to reduce testing time.

commit 2c95b0019f1b665fb14b9f00b049e8b5fb11f89d
Author: Brad Bell <bradbell@…>
Date: Mon May 29 16:55:07 2017 -0700

debug_rel branch:
Add cppad_debug_which to the cmake command line.

commit fd8d1498cf6dc092deca41f764cbb2a001a4cc88
Author: Brad Bell <bradbell@…>
Date: Mon May 29 08:14:23 2017 -0700

debug_rel branch:
Change random_debug_release -> set_compile_flags.

commit 159f5a5aa09012213a52f4ed1c9f0607129a5fe7
Author: Brad Bell <bradbell@…>
Date: Mon May 29 06:50:43 2017 -0700

debug_rel branch:
Update the autotools automatically generated build files.


batch_edit.sh: Start comments about a plan for editing all the source files.
get_sacado.sh: advance to trilions-12.10.11.
makefile.am: advance to trilinos-12.10.1

commit 302153317cd296ec6f927c3202cf96bf38594bbb
Author: Brad Bell <bradbell@…>
Date: Mon May 29 05:20:00 2017 -0700

debug_rel branch:
Add error message if sacado configuration file does not exist.

commit 3f01a631ae808c3a1359e53e1cd55e9a0ea88711
Author: Brad Bell <bradbell@…>
Date: Mon May 29 04:24:00 2017 -0700

debug_rel branch:
CMakeLists.txt: automate naming of libraries Sacado needs.
checkpoint.cpp: fix warnings.

commit dd240928c0c8b6972a8197c985ccc01f08b8886b
Author: Brad Bell <bradbell@…>
Date: Sun May 28 08:25:20 2017 -0700

debug_rel branch:
sparse_sub_hes.cpp: add missing cases found by clang compiler.

commit 30a0c35f1ac50ec425be9a2b7b026284026eccd7
Author: Brad Bell <bradbell@…>
Date: Sun May 28 07:57:36 2017 -0700

debug_rel branch:
eigen_cholesky.hpp: fix compiler warning.
harmonic_time.cpp: remove include that is not used.
forward_active.cpp: fix compiler warning.

commit 4876d14e49dc235865b1574fb38a55cf5ea7a422
Author: Brad Bell <bradbell@…>
Date: Sun May 28 06:19:48 2017 -0700

debug_rel branch:
random_debug_release.cmake: fix comment, remove message replaced by random_choice_0123 in output.
multiple_solution.cpp: fix warnings with clang compiler.
eigen_cholesky.hpp: fix warnings with clang compiler.
compare_change.cpp: fix CPPAD_DEBUG_AND_RELEASE case.

commit 2c51a18f35188d04d2f94069382439580e23f4ac
Author: Brad Bell <bradbell@…>
Date: Sat May 27 21:04:37 2017 -0700

debug_rel branch:
Advance version to cppad-20170527.

commit 4500887b362537774b05e954ad2a95b65a7b8ba0
Author: Brad Bell <bradbell@…>
Date: Sat May 27 09:04:56 2017 -0700

debug_rel branch:
Ramdomly select debug or release flags in example directory.


CMakeLists.txt: always debug for multi_threed examples.

commit 140b5269a0b1a30643894e5a7a8c9a5eb1310301
Author: Brad Bell <bradbell@…>
Date: Sat May 27 08:10:51 2017 -0700

debug_rel branch:
Changing how we set all debug and release flags.

commit e6fb2639db1288fb75de4030b5906df1e41756f9
Author: Brad Bell <bradbell@…>
Date: Sat May 27 07:30:24 2017 -0700

debug_rel branch:
Replace use of cppad_extra_debug by CPPAD_DEBUG_AND_RELEASE.

commit fbbfd0f6e94862174a8a7a17308489ffddb28084
Author: Brad Bell <bradbell@…>
Date: Sat May 27 05:55:58 2017 -0700

debug_rel branch:
Improve random selection of which files are build for release or debug.


forward.cpp: use new -DCPPAD_DEBUG_AND_RELEASE flag.

commit 284be366fb5e2f685a0c71ea6a0e3f74584bf187
Author: Brad Bell <bradbell@…>
Date: Thu May 25 07:39:32 2017 -0700

debug_rel branch:
Add test that failed before change to player.


player.hpp: Fix so it has the same size in debug and release more.
checkpoint.cpp: fix warning when compiling for release.
run_cmake.sh: prepare to use random number to switch debug and release set.
CMakeLists.txt: switch to only test debug (for now).

commit f32375b77e3825628fee6cb160f691a32c48b796
Author: Brad Bell <bradbell@…>
Date: Wed May 24 12:04:27 2017 -0700

debug_rel branch:
forward.cpp: fix a warning during release build.

commit 5fcc7eb78ae8de9f1dbc6c4f0c76fe38e8aeba95
Author: Brad Bell <bradbell@…>
Date: Wed May 24 10:11:12 2017 -0700

debug_rel branch:
CMakeLists.txt: make easy to mix debug and release builds.
eigen_mat_inv.hpp: fix release version warning.

commit 696266f3d62079f5e3bfb1a0f60a7e4f8134e068
Author: Brad Bell <bradbell@…>
Date: Wed May 24 05:43:29 2017 -0700

push_git2svn.py: user ./build in place of ./build/work.
testvector.hpp: improve comments about replacing CPPAD_TESTVECTOR.

File size: 12.1 KB
Line 
1// $Id$
2# ifndef CPPAD_EXAMPLE_EIGEN_CHOLESKY_HPP
3# define CPPAD_EXAMPLE_EIGEN_CHOLESKY_HPP
4
5/* --------------------------------------------------------------------------
6CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell
7
8CppAD is distributed under multiple licenses. This distribution is under
9the terms of the
10                    Eclipse Public License Version 1.0.
11
12A copy of this license is included in the COPYING file of this distribution.
13Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
14-------------------------------------------------------------------------- */
15
16/*
17$begin atomic_eigen_cholesky.hpp$$
18$spell
19        Eigen
20        Taylor
21        Cholesky
22        op
23$$
24
25$section Atomic Eigen Cholesky Factorization Class$$
26
27$head Purpose$$
28Construct an atomic operation that computes a lower triangular matrix
29$latex L $$ such that $latex L L^\R{T} = A$$
30for any positive integer $latex p$$
31and symmetric positive definite matrix $latex A \in \B{R}^{p \times p}$$.
32
33$head Start Class Definition$$
34$srccode%cpp% */
35# include <cppad/cppad.hpp>
36# include <Eigen/Dense>
37
38
39/* %$$
40$head Public$$
41
42$subhead Types$$
43$srccode%cpp% */
44namespace { // BEGIN_EMPTY_NAMESPACE
45
46template <class Base>
47class atomic_eigen_cholesky : public CppAD::atomic_base<Base> {
48public:
49        // -----------------------------------------------------------
50        // type of elements during calculation of derivatives
51        typedef Base              scalar;
52        // type of elements during taping
53        typedef CppAD::AD<scalar> ad_scalar;
54        //
55        // type of matrix during calculation of derivatives
56        typedef Eigen::Matrix<
57                scalar, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>        matrix;
58        // type of matrix during taping
59        typedef Eigen::Matrix<
60                ad_scalar, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor > ad_matrix;
61        //
62        // lower triangular scalar matrix
63        typedef Eigen::TriangularView<matrix, Eigen::Lower>             lower_view;
64/* %$$
65$subhead Constructor$$
66$srccode%cpp% */
67        // constructor
68        atomic_eigen_cholesky(void) : CppAD::atomic_base<Base>(
69                "atom_eigen_cholesky"                             ,
70                CppAD::atomic_base<Base>::set_sparsity_enum
71        )
72        { }
73/* %$$
74$subhead op$$
75$srccode%cpp% */
76        // use atomic operation to invert an AD matrix
77        ad_matrix op(const ad_matrix& arg)
78        {       size_t nr = size_t( arg.rows() );
79                size_t ny = ( (nr + 1 ) * nr ) / 2;
80                size_t nx = 1 + ny;
81                assert( nr == size_t( arg.cols() ) );
82                // -------------------------------------------------------------------
83                // packed version of arg
84                CPPAD_TESTVECTOR(ad_scalar) packed_arg(nx);
85                size_t index = 0;
86                packed_arg[index++] = ad_scalar( nr );
87                // lower triangle of symmetric matrix A
88                for(size_t i = 0; i < nr; i++)
89                {       for(size_t j = 0; j <= i; j++)
90                                packed_arg[index++] = arg(i, j);
91                }
92                assert( index == nx );
93                // -------------------------------------------------------------------
94                // packed version of result = arg^{-1}.
95                // This is an atomic_base function call that CppAD uses to
96                // store the atomic operation on the tape.
97                CPPAD_TESTVECTOR(ad_scalar) packed_result(ny);
98                (*this)(packed_arg, packed_result);
99                // -------------------------------------------------------------------
100                // unpack result matrix L
101                ad_matrix result = ad_matrix::Zero(nr, nr);
102                index = 0;
103                for(size_t i = 0; i < nr; i++)
104                {       for(size_t j = 0; j <= i; j++)
105                                result(i, j) = packed_result[index++];
106                }
107                return result;
108        }
109        /* %$$
110$head Private$$
111
112$subhead Variables$$
113$srccode%cpp% */
114private:
115        // -------------------------------------------------------------
116        // one forward mode vector of matrices for argument and result
117        CppAD::vector<matrix> f_arg_, f_result_;
118        // one reverse mode vector of matrices for argument and result
119        CppAD::vector<matrix> r_arg_, r_result_;
120        // -------------------------------------------------------------
121/* %$$
122$subhead forward$$
123$srccode%cpp% */
124        // forward mode routine called by CppAD
125        virtual bool forward(
126                // lowest order Taylor coefficient we are evaluating
127                size_t                          p ,
128                // highest order Taylor coefficient we are evaluating
129                size_t                          q ,
130                // which components of x are variables
131                const CppAD::vector<bool>&      vx ,
132                // which components of y are variables
133                CppAD::vector<bool>&            vy ,
134                // tx [ j * (q+1) + k ] is x_j^k
135                const CppAD::vector<scalar>&    tx ,
136                // ty [ i * (q+1) + k ] is y_i^k
137                CppAD::vector<scalar>&          ty
138        )
139        {       size_t n_order = q + 1;
140                size_t nr      = size_t( CppAD::Integer( tx[ 0 * n_order + 0 ] ) );
141                size_t ny      = ((nr + 1) * nr) / 2;
142# ifndef NDEBUG
143                size_t nx      = 1 + ny;
144# endif
145                assert( vx.size() == 0 || nx == vx.size() );
146                assert( vx.size() == 0 || ny == vy.size() );
147                assert( nx * n_order == tx.size() );
148                assert( ny * n_order == ty.size() );
149                //
150                // -------------------------------------------------------------------
151                // make sure f_arg_ and f_result_ are large enough
152                assert( f_arg_.size() == f_result_.size() );
153                if( f_arg_.size() < n_order )
154                {       f_arg_.resize(n_order);
155                        f_result_.resize(n_order);
156                        //
157                        for(size_t k = 0; k < n_order; k++)
158                        {       f_arg_[k].resize(nr, nr);
159                                f_result_[k].resize(nr, nr);
160                        }
161                }
162                // -------------------------------------------------------------------
163                // unpack tx into f_arg_
164                for(size_t k = 0; k < n_order; k++)
165                {       size_t index = 1;
166                        // unpack arg values for this order
167                        for(size_t i = 0; i < nr; i++)
168                        {       for(size_t j = 0; j <= i; j++)
169                                {       f_arg_[k](i, j) = tx[ index * n_order + k ];
170                                        f_arg_[k](j, i) = f_arg_[k](i, j);
171                                        index++;
172                                }
173                        }
174                }
175                // -------------------------------------------------------------------
176                // result for each order
177                // (we could avoid recalculting f_result_[k] for k=0,...,p-1)
178                //
179                Eigen::LLT<matrix> cholesky(f_arg_[0]);
180                f_result_[0]   = cholesky.matrixL();
181                lower_view L_0 = f_result_[0].template triangularView<Eigen::Lower>();
182                for(size_t k = 1; k < n_order; k++)
183                {       // initialize sum as A_k
184                        matrix f_sum = f_arg_[k];
185                        // compute A_k - B_k
186                        for(size_t ell = 1; ell < k; ell++)
187                                f_sum -= f_result_[ell] * f_result_[k-ell].transpose();
188                        // compute L_0^{-1} * (A_k - B_k) * L_0^{-T}
189                        matrix temp = L_0.template solve<Eigen::OnTheLeft>(f_sum);
190                        temp   = L_0.transpose().template solve<Eigen::OnTheRight>(temp);
191                        // divide the diagonal by 2
192                        for(size_t i = 0; i < nr; i++)
193                                temp(i, i) /= scalar(2.0);
194                        // L_k = L_0 * low[ L_0^{-1} * (A_k - B_k) * L_0^{-T} ]
195                        lower_view view = temp.template triangularView<Eigen::Lower>();
196                        f_result_[k] = f_result_[0] * view;
197                }
198                // -------------------------------------------------------------------
199                // pack result_ into ty
200                for(size_t k = 0; k < n_order; k++)
201                {       size_t index = 0;
202                        for(size_t i = 0; i < nr; i++)
203                        {       for(size_t j = 0; j <= i; j++)
204                                {       ty[ index * n_order + k ] = f_result_[k](i, j);
205                                        index++;
206                                }
207                        }
208                }
209                // -------------------------------------------------------------------
210                // check if we are computing vy
211                if( vx.size() == 0 )
212                        return true;
213                // ------------------------------------------------------------------
214                // This is a very dumb algorithm that over estimates which
215                // elements of the inverse are variables (which is not efficient).
216                bool var = false;
217                for(size_t i = 0; i < ny; i++)
218                        var |= vx[1 + i];
219                for(size_t i = 0; i < ny; i++)
220                        vy[i] = var;
221                //
222                return true;
223        }
224/* %$$
225$subhead reverse$$
226$srccode%cpp% */
227        // reverse mode routine called by CppAD
228        virtual bool reverse(
229                // highest order Taylor coefficient that we are computing derivative of
230                size_t                     q ,
231                // forward mode Taylor coefficients for x variables
232                const CppAD::vector<double>&     tx ,
233                // forward mode Taylor coefficients for y variables
234                const CppAD::vector<double>&     ty ,
235                // upon return, derivative of G[ F[ {x_j^k} ] ] w.r.t {x_j^k}
236                CppAD::vector<double>&           px ,
237                // derivative of G[ {y_i^k} ] w.r.t. {y_i^k}
238                const CppAD::vector<double>&     py
239        )
240        {       size_t n_order = q + 1;
241                size_t nr = size_t( CppAD::Integer( tx[ 0 * n_order + 0 ] ) );
242# ifndef NDEBUG
243                size_t ny = ( (nr + 1 ) * nr ) / 2;
244                size_t nx = 1 + ny;
245# endif
246                //
247                assert( nx * n_order == tx.size() );
248                assert( ny * n_order == ty.size() );
249                assert( px.size()    == tx.size() );
250                assert( py.size()    == ty.size() );
251                // -------------------------------------------------------------------
252                // make sure f_arg_ is large enough
253                assert( f_arg_.size() == f_result_.size() );
254                // must have previous run forward with order >= n_order
255                assert( f_arg_.size() >= n_order );
256                // -------------------------------------------------------------------
257                // make sure r_arg_, r_result_ are large enough
258                assert( r_arg_.size() == r_result_.size() );
259                if( r_arg_.size() < n_order )
260                {       r_arg_.resize(n_order);
261                        r_result_.resize(n_order);
262                        //
263                        for(size_t k = 0; k < n_order; k++)
264                        {       r_arg_[k].resize(nr, nr);
265                                r_result_[k].resize(nr, nr);
266                        }
267                }
268                // -------------------------------------------------------------------
269                // unpack tx into f_arg_
270                for(size_t k = 0; k < n_order; k++)
271                {       size_t index = 1;
272                        // unpack arg values for this order
273                        for(size_t i = 0; i < nr; i++)
274                        {       for(size_t j = 0; j <= i; j++)
275                                {       f_arg_[k](i, j) = tx[ index * n_order + k ];
276                                        f_arg_[k](j, i) = f_arg_[k](i, j);
277                                        index++;
278                                }
279                        }
280                }
281                // -------------------------------------------------------------------
282                // unpack py into r_result_
283                for(size_t k = 0; k < n_order; k++)
284                {       r_result_[k] = matrix::Zero(nr, nr);
285                        size_t index = 0;
286                        for(size_t i = 0; i < nr; i++)
287                        {       for(size_t j = 0; j <= i; j++)
288                                {       r_result_[k](i, j) = py[ index * n_order + k ];
289                                        index++;
290                                }
291                        }
292                }
293                // -------------------------------------------------------------------
294                // initialize r_arg_ as zero
295                for(size_t k = 0; k < n_order; k++)
296                        r_arg_[k]   = matrix::Zero(nr, nr);
297                // -------------------------------------------------------------------
298                // matrix reverse mode calculation
299                lower_view L_0 = f_result_[0].template triangularView<Eigen::Lower>();
300                //
301                for(size_t k1 = n_order; k1 > 1; k1--)
302                {       size_t k = k1 - 1;
303                        //
304                        // L_0^T * bar{L}_k
305                        matrix tmp1 = L_0.transpose() * r_result_[k];
306                        //
307                        //low[ L_0^T * bar{L}_k ]
308                        for(size_t i = 0; i < nr; i++)
309                                tmp1(i, i) /= scalar(2.0);
310                        matrix tmp2 = tmp1.template triangularView<Eigen::Lower>();
311                        //
312                        // L_0^{-T} low[ L_0^T * bar{L}_k ]
313                        tmp1 = L_0.transpose().template solve<Eigen::OnTheLeft>( tmp2 );
314                        //
315                        // M_k = L_0^{-T} * low[ L_0^T * bar{L}_k ]^{T} L_0^{-1}
316                        matrix M_k = L_0.transpose().template
317                                solve<Eigen::OnTheLeft>( tmp1.transpose() );
318                        //
319                        // remove L_k and compute bar{B}_k
320                        matrix barB_k = scalar(0.5) * ( M_k + M_k.transpose() );
321                        r_arg_[k]    += barB_k;
322                        barB_k        = scalar(-1.0) * barB_k;
323                        //
324                        // 2.0 * lower( bar{B}_k L_k )
325                        matrix temp = scalar(2.0) * barB_k * f_result_[k];
326                        temp        = temp.template triangularView<Eigen::Lower>();
327                        //
328                        // remove C_k
329                        r_result_[0] += temp;
330                        //
331                        // remove B_k
332                        for(size_t ell = 1; ell < k; ell++)
333                        {       // bar{L}_ell = 2 * lower( \bar{B}_k * L_{k-ell} )
334                                temp = scalar(2.0) * barB_k * f_result_[k-ell];
335                                r_result_[ell] += temp.template triangularView<Eigen::Lower>();
336                        }
337                }
338                // M_0 = L_0^{-T} * low[ L_0^T * bar{L}_0 ]^{T} L_0^{-1}
339                matrix M_0 = L_0.transpose() * r_result_[0];
340                for(size_t i = 0; i < nr; i++)
341                        M_0(i, i) /= scalar(2.0);
342                M_0 = M_0.template triangularView<Eigen::Lower>();
343                M_0 = L_0.template solve<Eigen::OnTheRight>( M_0 );
344                M_0 = L_0.transpose().template solve<Eigen::OnTheLeft>( M_0 );
345                // remove L_0
346                r_arg_[0] += scalar(0.5) * ( M_0 + M_0.transpose() );
347                // -------------------------------------------------------------------
348                // pack r_arg into px
349                // note that only the lower triangle of barA_k is stored in px
350                for(size_t k = 0; k < n_order; k++)
351                {       size_t index = 0;
352                        px[ index * n_order + k ] = 0.0;
353                        index++;
354                        for(size_t i = 0; i < nr; i++)
355                        {       for(size_t j = 0; j < i; j++)
356                                {       px[ index * n_order + k ] = 2.0 * r_arg_[k](i, j);
357                                        index++;
358                                }
359                                px[ index * n_order + k] = r_arg_[k](i, i);
360                                index++;
361                        }
362                }
363                // -------------------------------------------------------------------
364                return true;
365        }
366/* %$$
367$head End Class Definition$$
368$srccode%cpp% */
369}; // End of atomic_eigen_cholesky class
370
371}  // END_EMPTY_NAMESPACE
372/* %$$
373$end
374*/
375
376
377# endif
Note: See TracBrowser for help on using the repository browser.