Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SimplicialCholesky_impl.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2012 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11/*
12NOTE: these functions have been adapted from the LDL library:
13
14LDL Copyright (c) 2005 by Timothy A. Davis. All Rights Reserved.
15
16The author of LDL, Timothy A. Davis., has executed a license with Google LLC
17to permit distribution of this code and derivative works as part of Eigen under
18the Mozilla Public License v. 2.0, as stated at the top of this file.
19 */
20
21#ifndef EIGEN_SIMPLICIAL_CHOLESKY_IMPL_H
22#define EIGEN_SIMPLICIAL_CHOLESKY_IMPL_H
23
24// IWYU pragma: private
25#include "./InternalHeaderCheck.h"
26
27namespace Eigen {
28
29namespace internal {
30
31template <typename Scalar, typename StorageIndex>
32struct simpl_chol_helper {
33 using CholMatrixType = SparseMatrix<Scalar, ColMajor, StorageIndex>;
34 using InnerIterator = typename CholMatrixType::InnerIterator;
35 using VectorI = Matrix<StorageIndex, Dynamic, 1>;
36 static constexpr StorageIndex kEmpty = -1;
37
38 // Implementation of a stack or last-in first-out structure with some debugging machinery.
39 struct Stack {
40 StorageIndex* m_data;
41 Index m_size;
42#ifndef EIGEN_NO_DEBUG
43 const Index m_maxSize;
44 Stack(StorageIndex* data, StorageIndex size, StorageIndex maxSize)
45 : m_data(data), m_size(convert_index<Index>(size)), m_maxSize(convert_index<Index>(maxSize)) {
46 eigen_assert(size >= 0);
47 eigen_assert(maxSize >= size);
48 }
49#else
50 Stack(StorageIndex* data, StorageIndex size, StorageIndex /*maxSize*/)
51 : m_data(data), m_size(convert_index<Index>(size)) {}
52#endif
53 bool empty() const { return m_size == 0; }
54 Index size() const { return m_size; }
55 StorageIndex back() const {
56 eigen_assert(m_size > 0);
57 return m_data[m_size - 1];
58 }
59 void push(const StorageIndex& value) {
60#ifndef EIGEN_NO_DEBUG
61 eigen_assert(m_size < m_maxSize);
62#endif
63 m_data[m_size] = value;
64 m_size++;
65 }
66 void pop() {
67 eigen_assert(m_size > 0);
68 m_size--;
69 }
70 };
71
72 // Implementation of a disjoint-set or union-find structure with path compression.
73 struct DisjointSet {
74 StorageIndex* m_set;
75 DisjointSet(StorageIndex* set, StorageIndex size) : m_set(set) { std::iota(set, set + size, 0); }
76 // Find the set representative or root of `u`.
77 StorageIndex find(StorageIndex u) const {
78 eigen_assert(u != kEmpty);
79 while (m_set[u] != u) {
80 // manually unroll the loop by a factor of 2 to improve performance
81 u = m_set[m_set[u]];
82 }
83 return u;
84 }
85 // Perform full path compression such that each node from `u` to `v` points to `v`.
86 void compress(StorageIndex u, StorageIndex v) {
87 eigen_assert(u != kEmpty);
88 eigen_assert(v != kEmpty);
89 while (m_set[u] != v) {
90 StorageIndex next = m_set[u];
91 m_set[u] = v;
92 u = next;
93 }
94 }
95 };
96
97 // Computes the higher adjacency pattern by transposing the input lower adjacency matrix.
98 // Only the index arrays are calculated, as the values are not needed for the symbolic factorization.
99 // The outer index array provides the size requirements of the inner index array.
100
101 // Computes the outer index array of the higher adjacency matrix.
102 static void calc_hadj_outer(const StorageIndex size, const CholMatrixType& ap, StorageIndex* outerIndex) {
103 for (StorageIndex j = 1; j < size; j++) {
104 for (InnerIterator it(ap, convert_index<Index>(j)); it; ++it) {
105 StorageIndex i = it.index();
106 if (i < j) outerIndex[i + 1]++;
107 }
108 }
109 std::partial_sum(outerIndex, outerIndex + size + 1, outerIndex);
110 }
111
112 // inner index array
113 static void calc_hadj_inner(const StorageIndex size, const CholMatrixType& ap, const StorageIndex* outerIndex,
114 StorageIndex* innerIndex, StorageIndex* tmp) {
115 std::fill_n(tmp, size, 0);
116
117 for (StorageIndex j = 1; j < size; j++) {
118 for (InnerIterator it(ap, convert_index<Index>(j)); it; ++it) {
119 StorageIndex i = it.index();
120 if (i < j) {
121 StorageIndex b = outerIndex[i] + tmp[i];
122 innerIndex[b] = j;
123 tmp[i]++;
124 }
125 }
126 }
127 }
128
129 // Adapted from:
130 // Joseph W. Liu. (1986).
131 // A compact row storage scheme for Cholesky factors using elimination trees.
132 // ACM Trans. Math. Softw. 12, 2 (June 1986), 127-148. https://doi.org/10.1145/6497.6499
133
134 // Computes the elimination forest of the lower adjacency matrix, a compact representation of the sparse L factor.
135 // The L factor may contain multiple elimination trees if a column contains only its diagonal element.
136 // Each elimination tree is an n-ary tree in which each node points to its parent.
137 static void calc_etree(const StorageIndex size, const CholMatrixType& ap, StorageIndex* parent, StorageIndex* tmp) {
138 std::fill_n(parent, size, kEmpty);
139
140 DisjointSet ancestor(tmp, size);
141
142 for (StorageIndex j = 1; j < size; j++) {
143 for (InnerIterator it(ap, convert_index<Index>(j)); it; ++it) {
144 StorageIndex i = it.index();
145 if (i < j) {
146 StorageIndex r = ancestor.find(i);
147 if (r != j) parent[r] = j;
148 ancestor.compress(i, j);
149 }
150 }
151 }
152 }
153
154 // Computes the child pointers of the parent tree to facilitate a depth-first search traversal.
155 static void calc_lineage(const StorageIndex size, const StorageIndex* parent, StorageIndex* firstChild,
156 StorageIndex* firstSibling) {
157 std::fill_n(firstChild, size, kEmpty);
158 std::fill_n(firstSibling, size, kEmpty);
159
160 for (StorageIndex j = 0; j < size; j++) {
161 StorageIndex p = parent[j];
162 if (p == kEmpty) continue;
163 StorageIndex c = firstChild[p];
164 if (c == kEmpty)
165 firstChild[p] = j;
166 else {
167 while (firstSibling[c] != kEmpty) c = firstSibling[c];
168 firstSibling[c] = j;
169 }
170 }
171 }
172
173 // Computes a post-ordered traversal of the elimination tree.
174 static void calc_post(const StorageIndex size, const StorageIndex* parent, StorageIndex* firstChild,
175 const StorageIndex* firstSibling, StorageIndex* post, StorageIndex* dfs) {
176 Stack post_stack(post, 0, size);
177 for (StorageIndex j = 0; j < size; j++) {
178 if (parent[j] != kEmpty) continue;
179 // Begin at a root
180 Stack dfs_stack(dfs, 0, size);
181 dfs_stack.push(j);
182 while (!dfs_stack.empty()) {
183 StorageIndex i = dfs_stack.back();
184 StorageIndex c = firstChild[i];
185 if (c == kEmpty) {
186 post_stack.push(i);
187 dfs_stack.pop();
188 } else {
189 dfs_stack.push(c);
190 // Remove the path from `i` to `c` for future traversals.
191 firstChild[i] = firstSibling[c];
192 }
193 }
194 }
195 eigen_assert(post_stack.size() == size);
196 eigen_assert(std::all_of(firstChild, firstChild + size, [](StorageIndex a) { return a == kEmpty; }));
197 }
198
199 // Adapted from:
200 // Gilbert, J. R., Ng, E., & Peyton, B. W. (1994).
201 // An efficient algorithm to compute row and column counts for sparse Cholesky factorization.
202 // SIAM Journal on Matrix Analysis and Applications, 15(4), 1075-1091.
203
204 // Computes the non-zero pattern of the L factor.
205 static void calc_colcount(const StorageIndex size, const StorageIndex* hadjOuter, const StorageIndex* hadjInner,
206 const StorageIndex* parent, StorageIndex* prevLeaf, StorageIndex* tmp,
207 const StorageIndex* post, StorageIndex* nonZerosPerCol, bool doLDLT) {
208 // initialize nonZerosPerCol with 1 for leaves, 0 for non-leaves
209 std::fill_n(nonZerosPerCol, size, 1);
210 for (StorageIndex j = 0; j < size; j++) {
211 StorageIndex p = parent[j];
212 // p is not a leaf
213 if (p != kEmpty) nonZerosPerCol[p] = 0;
214 }
215
216 DisjointSet parentSet(tmp, size);
217 // prevLeaf is already initialized
218 eigen_assert(std::all_of(prevLeaf, prevLeaf + size, [](StorageIndex a) { return a == kEmpty; }));
219
220 for (StorageIndex j_ = 0; j_ < size; j_++) {
221 StorageIndex j = post[j_];
222 nonZerosPerCol[j] += hadjOuter[j + 1] - hadjOuter[j];
223 for (StorageIndex k = hadjOuter[j]; k < hadjOuter[j + 1]; k++) {
224 StorageIndex i = hadjInner[k];
225 eigen_assert(i > j);
226 StorageIndex prev = prevLeaf[i];
227 if (prev != kEmpty) {
228 StorageIndex q = parentSet.find(prev);
229 parentSet.compress(prev, q);
230 nonZerosPerCol[q]--;
231 }
232 prevLeaf[i] = j;
233 }
234 StorageIndex p = parent[j];
235 if (p != kEmpty) parentSet.compress(j, p);
236 }
237
238 for (StorageIndex j = 0; j < size; j++) {
239 StorageIndex p = parent[j];
240 if (p != kEmpty) nonZerosPerCol[p] += nonZerosPerCol[j] - 1;
241 if (doLDLT) nonZerosPerCol[j]--;
242 }
243 }
244
245 // Finalizes the non-zero pattern of the L factor and allocates the memory for the factorization.
246 static void init_matrix(const StorageIndex size, const StorageIndex* nonZerosPerCol, CholMatrixType& L) {
247 eigen_assert(L.outerIndexPtr()[0] == 0);
248 std::partial_sum(nonZerosPerCol, nonZerosPerCol + size, L.outerIndexPtr() + 1);
249 L.resizeNonZeros(convert_index<Index>(L.outerIndexPtr()[size]));
250 }
251
252 // Driver routine for the symbolic sparse Cholesky factorization.
253 static void run(const StorageIndex size, const CholMatrixType& ap, CholMatrixType& L, VectorI& parent,
254 VectorI& workSpace, bool doLDLT) {
255 parent.resize(convert_index<Index>(size));
256 workSpace.resize(4 * convert_index<Index>(size));
257 L.resize(convert_index<Index>(size), convert_index<Index>(size));
258
259 StorageIndex* tmp1 = workSpace.data();
260 StorageIndex* tmp2 = workSpace.data() + size;
261 StorageIndex* tmp3 = workSpace.data() + 2 * size;
262 StorageIndex* tmp4 = workSpace.data() + 3 * size;
263
264 // Borrow L's outer index array for the higher adjacency pattern.
265 StorageIndex* hadj_outer = L.outerIndexPtr();
266 calc_hadj_outer(size, ap, hadj_outer);
267 // Request additional temporary storage for the inner indices of the higher adjacency pattern.
268 ei_declare_aligned_stack_constructed_variable(StorageIndex, hadj_inner, convert_index<Index>(hadj_outer[size]),
269 nullptr);
270 calc_hadj_inner(size, ap, hadj_outer, hadj_inner, tmp1);
271
272 calc_etree(size, ap, parent.data(), tmp1);
273 calc_lineage(size, parent.data(), tmp1, tmp2);
274 calc_post(size, parent.data(), tmp1, tmp2, tmp3, tmp4);
275 calc_colcount(size, hadj_outer, hadj_inner, parent.data(), tmp1, tmp2, tmp3, tmp4, doLDLT);
276 init_matrix(size, tmp4, L);
277 }
278};
279
280// Required pre-C++17 for ODR; redundant and deprecated since (C++17 makes
281// constexpr static data members implicitly inline).
282#if EIGEN_COMP_CXXVER < 17
283template <typename Scalar, typename StorageIndex>
284constexpr StorageIndex simpl_chol_helper<Scalar, StorageIndex>::kEmpty;
285#endif
286
287} // namespace internal
288
289template <typename Derived>
290void SimplicialCholeskyBase<Derived>::analyzePattern_preordered(const CholMatrixType& ap, bool doLDLT) {
291 using Helper = internal::simpl_chol_helper<Scalar, StorageIndex>;
292
293 eigen_assert(ap.innerSize() == ap.outerSize());
294 const StorageIndex size = internal::convert_index<StorageIndex>(ap.outerSize());
295
296 Helper::run(size, ap, m_matrix, m_parent, m_workSpace, doLDLT);
297
298 m_isInitialized = true;
299 m_info = Success;
300 m_analysisIsOk = true;
301 m_factorizationIsOk = false;
302}
303
304template <typename Derived>
305template <bool DoLDLT, bool NonHermitian>
306void SimplicialCholeskyBase<Derived>::factorize_preordered(const CholMatrixType& ap) {
307 EIGEN_IF_CONSTEXPR (internal::packet_traits<Scalar>::Vectorizable && internal::packet_traits<Scalar>::HasMul &&
308 internal::packet_traits<Scalar>::HasSub && !NumTraits<Scalar>::IsComplex) {
309 const StorageIndex* outer = m_matrix.outerIndexPtr();
310 for (Index i = 0; i < m_matrix.cols(); ++i) {
311 // Exclude the diagonal (LLT) and the entry appended after the last update.
312 if (outer[i + 1] - outer[i] > internal::kSparseScatterPacketMinSize + (DoLDLT ? 0 : 1)) {
313 factorize_preordered_impl<DoLDLT, NonHermitian, true>(ap);
314 return;
315 }
316 }
317 }
318 factorize_preordered_impl<DoLDLT, NonHermitian, false>(ap);
319}
320
321template <typename Derived>
322template <bool DoLDLT, bool NonHermitian, bool UsePackets>
323void SimplicialCholeskyBase<Derived>::factorize_preordered_impl(const CholMatrixType& ap) {
324 const StorageIndex size = StorageIndex(ap.rows());
325
326 eigen_assert(m_analysisIsOk && "You must first call analyzePattern()");
327 EIGEN_INTERNAL_ASSERT_SQUARE(ap);
328 eigen_assert(m_parent.size() == size);
329 eigen_assert(m_workSpace.size() >= 3 * size);
330
331 const StorageIndex* Lp = m_matrix.outerIndexPtr();
332 StorageIndex* Li = m_matrix.innerIndexPtr();
333 Scalar* Lx = m_matrix.valuePtr();
334
335 ei_declare_aligned_stack_constructed_variable(Scalar, y, internal::convert_index<Index>(size), 0);
336 StorageIndex* nonZerosPerCol = m_workSpace.data();
337 StorageIndex* pattern = m_workSpace.data() + size;
338 StorageIndex* tags = m_workSpace.data() + 2 * size;
339
340 bool ok = true;
341 m_diag.resize(DoLDLT ? internal::convert_index<Index>(size) : 0);
342
343 for (StorageIndex k = 0; k < size; ++k) {
344 // compute nonzero pattern of kth row of L, in topological order
345 y[k] = Scalar(0); // Y(0:k) is now all zero
346 StorageIndex top = size; // stack for pattern is empty
347 tags[k] = k; // mark node k as visited
348 nonZerosPerCol[k] = 0; // count of nonzeros in column k of L
349 for (typename CholMatrixType::InnerIterator it(ap, internal::convert_index<Index>(k)); it; ++it) {
350 StorageIndex i = it.index();
351 if (i <= k) {
352 y[i] += getSymm(it.value()); /* scatter A(i,k) into Y (sum duplicates) */
353 Index len;
354 for (len = 0; tags[i] != k; i = m_parent[internal::convert_index<Index>(i)]) {
355 pattern[len++] = i; /* L(k,i) is nonzero */
356 tags[i] = k; /* mark i as visited */
357 }
358 while (len > 0) pattern[--top] = pattern[--len];
359 }
360 }
361
362 /* compute numerical values kth row of L (a sparse triangular solve) */
363
364 DiagonalScalar d =
365 getDiag(y[k]) * m_shiftScale + m_shiftOffset; // get D(k,k), apply the shift function, and clear Y(k)
366 y[k] = Scalar(0);
367 for (; top < size; ++top) {
368 Index i = internal::convert_index<Index>(pattern[top]); /* pattern[top:n-1] is pattern of L(:,k) */
369 Scalar yi = y[i]; /* get and clear Y(i) */
370 y[i] = Scalar(0);
371
372 /* the nonzero entry L(k,i) */
373 Scalar l_ki;
374 EIGEN_IF_CONSTEXPR (DoLDLT)
375 l_ki = yi / getDiag(m_diag[i]);
376 else
377 yi = l_ki = yi / Lx[Lp[i]];
378
379 Index p2 = internal::convert_index<Index>(Lp[i] + nonZerosPerCol[i]);
380 Index p = internal::convert_index<Index>(Lp[i]) + (DoLDLT ? 0 : 1);
381 EIGEN_IF_CONSTEXPR (UsePackets)
382 p += internal::sparse_scatter_sub_packets<!NonHermitian>(y, Li + p, Lx + p, p2 - p, yi);
383 for (; p < p2; ++p) y[Li[p]] -= getSymm(Lx[p]) * yi;
384 d -= getDiag(l_ki * getSymm(yi));
385 Li[p] = k; /* store L(k,i) in column form of L */
386 Lx[p] = l_ki;
387 ++nonZerosPerCol[i]; /* increment count of nonzeros in col i */
388 }
389 EIGEN_IF_CONSTEXPR (DoLDLT) {
390 m_diag[internal::convert_index<Index>(k)] = d;
391 if (d == RealScalar(0)) {
392 ok = false; /* failure, D(k,k) is zero */
393 break;
394 }
395 } else {
396 Index p = internal::convert_index<Index>(Lp[k] + nonZerosPerCol[k]++);
397 Li[p] = k; /* store L(k,k) = sqrt (d) in column k */
398 bool failed;
399 EIGEN_IF_CONSTEXPR (NonHermitian) {
400 // A complex symmetric matrix may have a pivot of any phase, whose square root is complex: only zero fails.
401 // A real pivot must be positive, as for the Hermitian LLT; sqrt of a negative one would be NaN.
402 failed = NumTraits<Scalar>::IsComplex ? (d == RealScalar(0)) : (numext::real(d) <= RealScalar(0));
403 } else {
404 failed = numext::real(d) <= RealScalar(0);
405 }
406 if (failed) {
407 ok = false; /* failure, matrix is not positive definite */
408 break;
409 }
410 Lx[p] = numext::sqrt(d);
411 }
412 }
413
414 m_info = ok ? Success : NumericalIssue;
415 m_factorizationIsOk = true;
416}
417
418} // end namespace Eigen
419
420#endif // EIGEN_SIMPLICIAL_CHOLESKY_IMPL_H
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457