Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
IncompleteCholesky.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr>
5// Copyright (C) 2015 Gael Guennebaud <gael.guennebaud@inria.fr>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_INCOMPLETE_CHOlESKY_H
13#define EIGEN_INCOMPLETE_CHOlESKY_H
14
15#include <vector>
16#include <list>
17
18// IWYU pragma: private
19#include "./InternalHeaderCheck.h"
20
21namespace Eigen {
51template <typename Scalar, int UpLo_ = Lower, typename OrderingType_ = AMDOrdering<int> >
52class IncompleteCholesky : public SparseSolverBase<IncompleteCholesky<Scalar, UpLo_, OrderingType_> > {
53 protected:
55 using Base::m_isInitialized;
56
57 public:
58 using RealScalar = typename NumTraits<Scalar>::Real;
59 using OrderingType = OrderingType_;
60 using PermutationType = typename OrderingType::PermutationType;
61 using StorageIndex = typename PermutationType::StorageIndex;
63 using VectorSx = Matrix<Scalar, Dynamic, 1>;
64 using VectorRx = Matrix<RealScalar, Dynamic, 1>;
65 using VectorIx = Matrix<StorageIndex, Dynamic, 1>;
66 using VectorList = std::vector<std::list<StorageIndex>>;
67 enum { UpLo = UpLo_ };
68 enum { ColsAtCompileTime = Dynamic, MaxColsAtCompileTime = Dynamic };
69
70 public:
77 IncompleteCholesky() : m_initialShift(1e-3), m_analysisIsOk(false), m_factorizationIsOk(false) {}
78
81 template <typename MatrixType>
82 IncompleteCholesky(const MatrixType& matrix)
83 : m_initialShift(1e-3), m_analysisIsOk(false), m_factorizationIsOk(false) {
84 compute(matrix);
85 }
86
88 constexpr Index rows() const noexcept { return m_L.rows(); }
89
91 constexpr Index cols() const noexcept { return m_L.cols(); }
92
102 eigen_assert(m_isInitialized && "IncompleteCholesky is not initialized.");
103 return m_info;
104 }
105
108 void setInitialShift(RealScalar shift) { m_initialShift = shift; }
109
112 template <typename MatrixType>
113 void analyzePattern(const MatrixType& mat) {
114 OrderingType ord;
115 PermutationType pinv;
116 ord(mat.template selfadjointView<UpLo>(), pinv);
117 if (pinv.size() > 0)
118 m_perm = pinv.inverse();
119 else
120 m_perm.resize(0);
121 m_L.resize(mat.rows(), mat.cols());
122 m_analysisIsOk = true;
123 m_isInitialized = true;
124 m_info = Success;
125 }
126
134 template <typename MatrixType>
135 void factorize(const MatrixType& mat);
136
143 template <typename MatrixType>
144 void compute(const MatrixType& mat) {
145 analyzePattern(mat);
146 factorize(mat);
147 }
148
149 // internal
150 template <typename Rhs, typename Dest>
151 void _solve_impl(const Rhs& b, Dest& x) const {
152 eigen_assert(m_factorizationIsOk && "factorize() should be called first");
153 if (m_perm.rows() == b.rows())
154 x = m_perm * b;
155 else
156 x = b;
157 x = m_scale.asDiagonal() * x;
158 x = m_L.template triangularView<Lower>().solve(x);
159 x = m_L.adjoint().template triangularView<Upper>().solve(x);
160 x = m_scale.asDiagonal() * x;
161 if (m_perm.rows() == b.rows()) x = m_perm.inverse() * x;
162 }
163
165 const FactorType& matrixL() const {
166 eigen_assert(m_factorizationIsOk && "factorize() should be called first");
167 return m_L;
168 }
169
171 const VectorRx& scalingS() const {
172 eigen_assert(m_factorizationIsOk && "factorize() should be called first");
173 return m_scale;
174 }
175
177 const PermutationType& permutationP() const {
178 eigen_assert(m_analysisIsOk && "analyzePattern() should be called first");
179 return m_perm;
180 }
181
183 RealScalar shift() const { return m_shift; }
184
185 protected:
186 FactorType m_L; // The lower part stored in CSC
187 VectorRx m_scale; // The vector for scaling the matrix
188 RealScalar m_initialShift; // The initial shift parameter
189 bool m_analysisIsOk;
190 bool m_factorizationIsOk;
191 ComputationInfo m_info;
192 PermutationType m_perm;
193 RealScalar m_shift; // The final shift parameter.
194
195 private:
196 inline void updateList(Ref<const VectorIx> colPtr, Ref<VectorIx> rowIdx, Ref<VectorSx> vals, const Index& col,
197 const Index& jk, VectorIx& firstElt, VectorList& listCol);
198};
199
200// Based on the following paper:
201// C-J. Lin and J. J. Moré, Incomplete Cholesky Factorizations with
202// Limited memory, SIAM J. Sci. Comput. 21(1), pp. 24-45, 1999
203// http://ftp.mcs.anl.gov/pub/tech_reports/reports/P682.pdf
204template <typename Scalar, int UpLo_, typename OrderingType>
205template <typename MatrixType_>
207 eigen_assert(m_analysisIsOk && "analyzePattern() should be called first");
208
209 // Dropping strategy : Keep only the p largest elements per column, where p is the number of elements in the column of
210 // the original matrix. Other strategies will be added
211
212 // Apply the fill-reducing permutation computed in analyzePattern()
213 if (m_perm.rows() == mat.rows()) // To detect the null permutation
214 {
215 // The temporary is needed to make sure that the diagonal entry is properly sorted
216 FactorType tmp(mat.rows(), mat.cols());
217 tmp = mat.template selfadjointView<UpLo_>().twistedBy(m_perm);
218 m_L.template selfadjointView<Lower>() = tmp.template selfadjointView<Lower>();
219 } else {
220 m_L.template selfadjointView<Lower>() = mat.template selfadjointView<UpLo_>();
221 }
222
223 // The algorithm will insert increasingly large shifts on the diagonal until
224 // factorization succeeds. Therefore we have to make sure that there is a
225 // space in the datastructure to store such values, even if the original
226 // matrix has a zero on the diagonal.
227 bool modified = false;
228 for (Index i = 0; i < mat.cols(); ++i) {
229 bool inserted = false;
230 m_L.findOrInsertCoeff(i, i, &inserted);
231 if (inserted) {
232 modified = true;
233 }
234 }
235 if (modified) m_L.makeCompressed();
236
237 Index n = m_L.cols();
238 Index nnz = m_L.nonZeros();
239 Map<VectorSx> vals(m_L.valuePtr(), nnz); // values
240 Map<VectorIx> rowIdx(m_L.innerIndexPtr(), nnz); // Row indices
241 Map<VectorIx> colPtr(m_L.outerIndexPtr(), n + 1); // Pointer to the beginning of each column
242 VectorIx firstElt(n); // for each j, points to the next entry in vals that will be used in the factorization
243 VectorList listCol(n); // listCol(j) is a linked list of columns to update column j
244 VectorSx col_vals(n); // Store the nonzero values in each column
245 VectorIx col_irow(n); // Row indices of nonzero elements in each column
246 VectorIx col_pattern(n);
247 col_pattern.fill(-1);
248 StorageIndex col_nnz;
249
250 // Computes the scaling factors
251 m_scale.resize(n);
252 m_scale.setZero();
253 for (Index j = 0; j < n; j++)
254 for (Index k = colPtr[j]; k < colPtr[j + 1]; k++) {
255 m_scale(j) += numext::abs2(vals(k));
256 if (rowIdx[k] != j) m_scale(rowIdx[k]) += numext::abs2(vals(k));
257 }
258
259 m_scale = m_scale.cwiseSqrt().cwiseSqrt();
260
261 for (Index j = 0; j < n; ++j)
262 if (m_scale(j) > (std::numeric_limits<RealScalar>::min)())
263 m_scale(j) = RealScalar(1) / m_scale(j);
264 else
265 m_scale(j) = 1;
266
267 // TODO: disable scaling when roughly uniform to speed up solve().
268
269 // Scale and compute the shift for the matrix
270 RealScalar mindiag = NumTraits<RealScalar>::highest();
271 for (Index j = 0; j < n; j++) {
272 for (Index k = colPtr[j]; k < colPtr[j + 1]; k++) vals[k] *= (m_scale(j) * m_scale(rowIdx[k]));
273 eigen_internal_assert(rowIdx[colPtr[j]] == j &&
274 "IncompleteCholesky: only the lower triangular part must be stored");
275 mindiag = numext::mini(numext::real(vals[colPtr[j]]), mindiag);
276 }
277
278 FactorType L_save = m_L;
279
280 m_shift = RealScalar(0);
281 if (mindiag <= RealScalar(0.)) m_shift = m_initialShift - mindiag;
282
283 m_info = NumericalIssue;
284
285 // Try to perform the incomplete factorization using the current shift
286 int iter = 0;
287 do {
288 // Apply the shift to the diagonal elements of the matrix
289 for (Index j = 0; j < n; j++) vals[colPtr[j]] += m_shift;
290
291 // jki version of the Cholesky factorization
292 Index j = 0;
293 for (; j < n; ++j) {
294 // Left-looking factorization of the j-th column
295 // First, load the j-th column into col_vals
296 Scalar diag = vals[colPtr[j]]; // It is assumed that only the lower part is stored
297 col_nnz = 0;
298 for (Index i = colPtr[j] + 1; i < colPtr[j + 1]; i++) {
299 StorageIndex l = rowIdx[i];
300 col_vals(col_nnz) = vals[i];
301 col_irow(col_nnz) = l;
302 col_pattern(l) = col_nnz;
303 col_nnz++;
304 }
305 {
306 typename std::list<StorageIndex>::iterator k;
307 // Browse all previous columns that will update column j
308 for (k = listCol[j].begin(); k != listCol[j].end(); k++) {
309 Index jk = firstElt(*k); // First element to use in the column
310 eigen_internal_assert(rowIdx[jk] == j);
311 Scalar v_j_jk = numext::conj(vals[jk]);
312
313 jk += 1;
314 for (Index i = jk; i < colPtr[*k + 1]; i++) {
315 StorageIndex l = rowIdx[i];
316 if (col_pattern[l] < 0) {
317 col_vals(col_nnz) = vals[i] * v_j_jk;
318 col_irow[col_nnz] = l;
319 col_pattern(l) = col_nnz;
320 col_nnz++;
321 } else
322 col_vals(col_pattern[l]) -= vals[i] * v_j_jk;
323 }
324 updateList(colPtr, rowIdx, vals, *k, jk, firstElt, listCol);
325 }
326 }
327
328 // Scale the current column
329 if (numext::real(diag) <= 0) {
330 if (++iter >= 10) return;
331
332 // increase shift
333 m_shift = numext::maxi(m_initialShift, RealScalar(2) * m_shift);
334 // restore m_L, col_pattern, and listCol
335 vals = Map<const VectorSx>(L_save.valuePtr(), nnz);
336 rowIdx = Map<const VectorIx>(L_save.innerIndexPtr(), nnz);
337 colPtr = Map<const VectorIx>(L_save.outerIndexPtr(), n + 1);
338 col_pattern.fill(-1);
339 for (Index i = 0; i < n; ++i) listCol[i].clear();
340
341 break;
342 }
343
344 RealScalar rdiag = numext::sqrt(numext::real(diag));
345 vals[colPtr[j]] = rdiag;
346 for (Index k = 0; k < col_nnz; ++k) {
347 Index i = col_irow[k];
348 // Scale
349 col_vals(k) /= rdiag;
350 // Update the remaining diagonals with col_vals
351 vals[colPtr[i]] -= numext::abs2(col_vals(k));
352 }
353 // Select the largest p elements
354 // p is the original number of elements in the column (without the diagonal)
355 Index p = colPtr[j + 1] - colPtr[j] - 1;
356 Ref<VectorSx> cvals = col_vals.head(col_nnz);
357 Ref<VectorIx> cirow = col_irow.head(col_nnz);
358 internal::QuickSplit(cvals, cirow, p);
359 // Insert the largest p elements in the matrix
360 Index cpt = 0;
361 for (Index i = colPtr[j] + 1; i < colPtr[j + 1]; i++) {
362 vals[i] = col_vals(cpt);
363 rowIdx[i] = col_irow(cpt);
364 // restore col_pattern:
365 col_pattern(col_irow(cpt)) = -1;
366 cpt++;
367 }
368 // Get the first smallest row index and put it after the diagonal element
369 Index jk = colPtr(j) + 1;
370 updateList(colPtr, rowIdx, vals, j, jk, firstElt, listCol);
371 }
372
373 if (j == n) {
374 m_factorizationIsOk = true;
375 m_info = Success;
376 }
377 } while (m_info != Success);
378}
379
380template <typename Scalar, int UpLo_, typename OrderingType>
381inline void IncompleteCholesky<Scalar, UpLo_, OrderingType>::updateList(Ref<const VectorIx> colPtr,
382 Ref<VectorIx> rowIdx, Ref<VectorSx> vals,
383 const Index& col, const Index& jk,
384 VectorIx& firstElt, VectorList& listCol) {
385 if (jk < colPtr(col + 1)) {
386 Index p = colPtr(col + 1) - jk;
387 Index minpos;
388 rowIdx.segment(jk, p).minCoeff(&minpos);
389 minpos += jk;
390 if (rowIdx(minpos) != rowIdx(jk)) {
391 // Swap
392 std::swap(rowIdx(jk), rowIdx(minpos));
393 std::swap(vals(jk), vals(minpos));
394 }
395 firstElt(col) = internal::convert_index<StorageIndex, Index>(jk);
396 listCol[rowIdx(jk)].push_back(internal::convert_index<StorageIndex, Index>(col));
397 }
398}
399
400} // end namespace Eigen
401
402#endif
ComputationInfo info() const
Reports whether previous computation was successful.
Definition IncompleteCholesky.h:101
IncompleteCholesky(const MatrixType &matrix)
Definition IncompleteCholesky.h:82
const VectorRx & scalingS() const
Definition IncompleteCholesky.h:171
const FactorType & matrixL() const
Definition IncompleteCholesky.h:165
const PermutationType & permutationP() const
Definition IncompleteCholesky.h:177
constexpr Index rows() const noexcept
Definition IncompleteCholesky.h:88
void factorize(const MatrixType &mat)
Performs the numerical factorization of the input matrix mat.
IncompleteCholesky()
Definition IncompleteCholesky.h:77
void compute(const MatrixType &mat)
Definition IncompleteCholesky.h:144
void analyzePattern(const MatrixType &mat)
Computes the fill reducing permutation vector using the sparsity pattern of mat.
Definition IncompleteCholesky.h:113
constexpr Index cols() const noexcept
Definition IncompleteCholesky.h:91
RealScalar shift() const
Definition IncompleteCholesky.h:183
void setInitialShift(RealScalar shift)
Set the initial shift parameter .
Definition IncompleteCholesky.h:108
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
A matrix or vector expression mapping an existing expression.
Definition Ref.h:261
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
ComputationInfo
Definition Constants.h:455
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457