source: trunk/cppad_lib/cppad_colpack.cpp @ 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: 7.7 KB
Line 
1/* --------------------------------------------------------------------------
2CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell
3
4CppAD is distributed under multiple licenses. This distribution is under
5the terms of the
6                    Eclipse Public License Version 1.0.
7
8A copy of this license is included in the COPYING file of this distribution.
9Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
10-------------------------------------------------------------------------- */
11# include <vector>
12# include <cppad/utility/vector.hpp>
13# include <cppad/configure.hpp>
14# include <cppad/core/define.hpp>
15# include <cppad/core/cppad_assert.hpp>
16
17# if CPPAD_HAS_COLPACK == 0
18namespace CppAD { namespace local {
19        CPPAD_LIB_EXPORT void this_routine_should_never_get_called(void)
20        {       CPPAD_ASSERT_UNKNOWN(false); }
21}
22# else // CPPAD_HAS_COLPACK
23# include <ColPack/ColPackHeaders.h>
24
25namespace CppAD { namespace local { // BEGIN_CPPAD_LOCAL_NAMESPACE
26
27/*!
28\file cppad_colpack.cpp
29The CppAD interface to the Colpack coloring algorithms.
30*/
31
32/*!
33Determine which rows of a general sparse matrix can be computed together.
34
35\param color
36is a vector with color.size() == m.
37For i = 0 , ... , m-1, color[i] is the color for the corresponding row
38of the matrix. If color[i1]==color[i2], (i1, j1) is in sparsity pattern,
39and (i2, j2) is in sparsity pattern, then j1 is not equal to j2.
40
41\param m
42is the number of rows in the matrix.
43
44\param n
45is the number of columns in the matrix.
46
47\param adolc_pattern
48is a vector with adolc_pattern.size() == m.
49For i = 0 , ... , m-1, and for k = 1, ... ,adolc_pattern[i][0],
50the entry with index (i, adolc_pattern[i][k]) is a non-zero
51in the sparsity pattern for the matrix.
52*/
53// ----------------------------------------------------------------------
54CPPAD_LIB_EXPORT void cppad_colpack_general(
55        CppAD::vector<size_t>&               color         ,
56        size_t                               m             ,
57        size_t                               n             ,
58        const CppAD::vector<unsigned int*>&  adolc_pattern )
59{       size_t i, k;
60        CPPAD_ASSERT_UNKNOWN( adolc_pattern.size() == m );
61        CPPAD_ASSERT_UNKNOWN( color.size() == m );
62
63        // Use adolc sparsity pattern to create corresponding bipartite graph
64        ColPack::BipartiteGraphPartialColoringInterface graph(
65                        SRC_MEM_ADOLC,
66                        adolc_pattern.data(),
67                        m,
68                        n
69        );
70
71        // row ordered Partial-Distance-Two-Coloring of the bipartite graph
72        graph.PartialDistanceTwoColoring(
73                "SMALLEST_LAST", "ROW_PARTIAL_DISTANCE_TWO"
74        );
75
76        // Use coloring information to create seed matrix
77        int n_seed_row;
78        int n_seed_col;
79        double** seed_matrix = graph.GetSeedMatrix(&n_seed_row, &n_seed_col);
80        CPPAD_ASSERT_UNKNOWN( size_t(n_seed_col) == m );
81
82        // now return coloring in format required by CppAD
83        for(i = 0; i < m; i++)
84                color[i] = m;
85        for(k = 0; k < size_t(n_seed_row); k++)
86        {       for(i = 0; i < m; i++)
87                {       if( seed_matrix[k][i] != 0.0 )
88                        {       // check that entries in the seed matrix are zero or one
89                                CPPAD_ASSERT_UNKNOWN( seed_matrix[k][i] == 1.0 );
90                                // check that no row appears twice in the coloring
91                                CPPAD_ASSERT_UNKNOWN( color[i] == m );
92                                // only need include rows with non-zero entries
93                                if( adolc_pattern[i][0] != 0 )
94                                {       // set color for this row
95                                        color[i] = k;
96                                }
97                        }
98                }
99        }
100# ifndef NDEBUG
101        // check non-zero versus color for each row
102        for(i = 0; i < m; i++)
103        {
104                // if there is a color for row i, check that it has non-zero entries
105                if(color[i] < m )
106                        CPPAD_ASSERT_UNKNOWN( adolc_pattern[i][0] != 0 );
107
108                // if there is no color for row i, check that it is empty
109                if( color[i] == m )
110                        CPPAD_ASSERT_UNKNOWN( adolc_pattern[i][0] == 0 );
111        }
112
113        // check that no rows with the same color have non-zero entries
114        // with the same column index
115        CppAD::vector<bool> found(n);
116        for(k = 0; k < size_t(n_seed_row); k++)
117        {       // k is the color index
118                // found: column already has a non-zero entries for this color
119                for(size_t j = 0; j < n; j++)
120                        found[j] = false;
121                // for each row with color k
122                for(i = 0; i < m; i++) if( color[i] == k )
123                {       // for each non-zero entry in this row
124                        for(size_t ell = 0; ell < adolc_pattern[i][0]; ell++)
125                        {       // column index for this entry
126                                size_t j = adolc_pattern[i][1 + ell];
127                                // check that this is the first non-zero in this column
128                                CPPAD_ASSERT_UNKNOWN( ! found[j] );
129                                // found a non-zero in this column
130                                found[j] = true;
131                        }
132                }
133        }
134# endif
135        return;
136}
137// ----------------------------------------------------------------------
138/*!
139Determine which rows of a symmetrix sparse matrix can be computed together.
140
141\param color
142is a vector with color.size() == m.
143For i = 0 , ... , m-1, color[i] is the color for the corresponding row
144of the matrix. We say that a sparsity pattern entry (i, j) is valid if
145for all i1, such that i1 != i and color[i1]==color[i],
146and all j1, such that (i1, j1) is in sparsity pattern, j1 != j.
147The coloring is chosen so that for all (i, j) in the sparsity pattern;
148either (i, j) or (j, i) is valid (possibly both).
149
150\param m
151is the number of rows (and columns) in the matrix.
152
153\param adolc_pattern
154is a vector with adolc_pattern.size() == m.
155For i = 0 , ... , m-1, and for k = 1, ... ,adolc_pattern[i][0],
156the entry with index (i, adolc_pattern[i][k]) is
157in the sparsity pattern for the symmetric matrix.
158*/
159CPPAD_LIB_EXPORT void cppad_colpack_symmetric(
160        CppAD::vector<size_t>&               color         ,
161        size_t                               m             ,
162        const CppAD::vector<unsigned int*>&  adolc_pattern )
163{       size_t i;
164        CPPAD_ASSERT_UNKNOWN( adolc_pattern.size() == m );
165        CPPAD_ASSERT_UNKNOWN( color.size() == m );
166
167        // Use adolc sparsity pattern to create corresponding bipartite graph
168        ColPack::GraphColoringInterface graph(
169                        SRC_MEM_ADOLC,
170                        adolc_pattern.data(),
171                        m
172        );
173
174        // Use STAR coloring because it has a direct recovery scheme; i.e.,
175        // not necessary to solve equations to extract values.
176        graph.Coloring("SMALLEST_LAST", "STAR");
177
178        // Use coloring information to create seed matrix
179        int n_seed_row;
180        int n_seed_col;
181        double** seed_matrix = graph.GetSeedMatrix(&n_seed_row, &n_seed_col);
182        CPPAD_ASSERT_UNKNOWN( size_t(n_seed_row) == m );
183
184        // now return coloring for each row in format required by CppAD
185        for(i = 0; i < m; i++)
186                color[i] = m;
187        for(i = 0; i < m; i++)
188        {       for(size_t k = 0; k < size_t(n_seed_col); k++)
189                {       if( seed_matrix[i][k] != 0.0 )
190                        {       // check that entries in seed matrix are zero or one
191                                CPPAD_ASSERT_UNKNOWN( seed_matrix[i][k] == 1.0 );
192                                // check that now row appears twice in the coloring
193                                CPPAD_ASSERT_UNKNOWN( color[i] == m );
194                                // only need include rows with non-zero entries
195                                if( adolc_pattern[i][0] != 0 )
196                                {       // set color for this row
197                                        color[i] = k;
198                                }
199                        }
200                }
201        }
202
203# ifndef NDEBUG
204        // check that every entry in the symetric matrix can be direclty recovered
205        size_t i1, i2, j1, j2, k1, k2, nz1, nz2;
206        for(i1 = 0; i1 < m; i1++)
207        {       nz1 = size_t(adolc_pattern[i1][0]);
208                for(k1 = 1; k1 <= nz1; k1++)
209                {       j1 = adolc_pattern[i1][k1];
210                        // (i1, j1) is a non-zero in the sparsity pattern
211
212                        // check of a forward on color[i1] followed by a reverse
213                        // can recover entry (i1, j1)
214                        bool color_i1_ok = true;
215                        for(i2 = 0; i2 < m; i2++) if( i1 != i2 && color[i1] == color[i2] )
216                        {       nz2 = adolc_pattern[i2][0];
217                                for(k2 = 1; k2 <= nz2; k2++)
218                                {       j2 = adolc_pattern[i2][k2];
219                                        color_i1_ok &= (j1 != j2);
220                                }
221                        }
222
223                        // check of a forward on color[j1] followed by a reverse
224                        // can recover entry (j1, i1)
225                        bool color_j1_ok = true;
226                        for(j2 = 0; j2 < m; j2++) if( j1 != j2 && color[j1] == color[j2] )
227                        {       nz2 = adolc_pattern[j2][0];
228                                for(k2 = 1; k2 <= nz2; k2++)
229                                {       i2 = adolc_pattern[j2][k2];
230                                        color_j1_ok &= (i1 != i2);
231                                }
232                        }
233
234                        CPPAD_ASSERT_UNKNOWN( color_i1_ok || color_j1_ok );
235                }
236        }
237# endif
238        return;
239}
240
241} } // END_CPPAD_LOCAL_NAMESPACE
242
243# endif // CPPAD_HAS_COLPACK
Note: See TracBrowser for help on using the repository browser.