Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
IncompleteLUT.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) 2014 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_LUT_H
13#define EIGEN_INCOMPLETE_LUT_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
31template <typename VectorV, typename VectorI>
32Index QuickSplit(VectorV& row, VectorI& ind, Index ncut) {
33 using RealScalar = typename VectorV::RealScalar;
34 using std::swap;
35 Index mid;
36 Index n = row.size(); /* length of the vector */
37 Index first, last;
38
39 ncut--; /* to fit the zero-based indices */
40 first = 0;
41 last = n - 1;
42 if (ncut < first || ncut > last) return 0;
43
44 do {
45 mid = first;
46 RealScalar abskey = numext::abs(row(mid));
47 for (Index j = first + 1; j <= last; j++) {
48 if (numext::abs(row(j)) > abskey) {
49 ++mid;
50 swap(row(mid), row(j));
51 swap(ind(mid), ind(j));
52 }
53 }
54 /* Interchange for the pivot element */
55 swap(row(mid), row(first));
56 swap(ind(mid), ind(first));
57
58 if (mid > ncut)
59 last = mid - 1;
60 else if (mid < ncut)
61 first = mid + 1;
62 } while (mid != ncut);
63
64 return 0; /* mid is equal to ncut */
65}
66
67} // end namespace internal
68
101template <typename Scalar_, typename StorageIndex_ = int>
102class IncompleteLUT : public SparseSolverBase<IncompleteLUT<Scalar_, StorageIndex_> > {
103 protected:
105 using Base::m_isInitialized;
106
107 public:
108 using Scalar = Scalar_;
109 using StorageIndex = StorageIndex_;
110 using RealScalar = typename NumTraits<Scalar>::Real;
111 using Vector = Matrix<Scalar, Dynamic, 1>;
112 using VectorI = Matrix<StorageIndex, Dynamic, 1>;
114
115 enum { ColsAtCompileTime = Dynamic, MaxColsAtCompileTime = Dynamic };
116
117 public:
118 IncompleteLUT()
119 : m_droptol(NumTraits<Scalar>::dummy_precision()),
120 m_fillfactor(10),
121 m_analysisIsOk(false),
122 m_factorizationIsOk(false) {}
123
124 template <typename MatrixType>
125 explicit IncompleteLUT(const MatrixType& mat, const RealScalar& droptol = NumTraits<Scalar>::dummy_precision(),
126 int fillfactor = 10)
127 : m_droptol(droptol), m_fillfactor(fillfactor), m_analysisIsOk(false), m_factorizationIsOk(false) {
128 eigen_assert(fillfactor != 0);
129 compute(mat);
130 }
131
133 const FactorType matrixL() const;
134
136 const FactorType matrixU() const;
137
138 constexpr Index rows() const noexcept { return m_lu.rows(); }
139
140 constexpr Index cols() const noexcept { return m_lu.cols(); }
141
152 eigen_assert(m_isInitialized && "IncompleteLUT is not initialized.");
153 return m_info;
154 }
155
156 template <typename MatrixType>
157 void analyzePattern(const MatrixType& amat);
158
159 template <typename MatrixType>
160 void factorize(const MatrixType& amat);
161
171 template <typename MatrixType>
172 IncompleteLUT& compute(const MatrixType& amat) {
173 analyzePattern(amat);
174 factorize(amat);
175 return *this;
176 }
177
178 void setDroptol(const RealScalar& droptol);
179 void setFillfactor(int fillfactor);
180
181 template <typename Rhs, typename Dest>
182 void _solve_impl(const Rhs& b, Dest& x) const {
183 x = m_PinvPr * b;
184 x = m_lu.template triangularView<UnitLower>().solve(x);
185 x = m_lu.template triangularView<Upper>().solve(x);
186 x = m_P * x;
187 }
188
189 protected:
191 struct keep_diag {
192 inline bool operator()(const Index& row, const Index& col, const Scalar&) const { return row != col; }
193 };
194
195 template <typename MatrixType>
196 Index computeRowMatching(const MatrixType& amat);
197
198 protected:
199 FactorType m_lu;
200 RealScalar m_droptol;
201 int m_fillfactor;
202 bool m_analysisIsOk;
203 bool m_factorizationIsOk;
204 ComputationInfo m_info;
205 PermutationMatrix<Dynamic, Dynamic, StorageIndex> m_P; // Fill-reducing permutation
206 PermutationMatrix<Dynamic, Dynamic, StorageIndex> m_Pinv; // Inverse permutation
207 PermutationMatrix<Dynamic, Dynamic, StorageIndex> m_Pr; // Static row permutation (matching-based)
208 PermutationMatrix<Dynamic, Dynamic, StorageIndex> m_PinvPr; // Cached composition m_Pinv * m_Pr for solve
209};
210
215template <typename Scalar, typename StorageIndex>
216void IncompleteLUT<Scalar, StorageIndex>::setDroptol(const RealScalar& droptol) {
217 this->m_droptol = droptol;
218}
219
224template <typename Scalar, typename StorageIndex>
226 this->m_fillfactor = fillfactor;
227}
228
234template <typename Scalar, typename StorageIndex>
235const typename IncompleteLUT<Scalar, StorageIndex>::FactorType IncompleteLUT<Scalar, StorageIndex>::matrixL() const {
236 eigen_assert(m_factorizationIsOk && "factorize() should be called first");
237 return m_lu.template triangularView<UnitLower>();
238}
239
245template <typename Scalar, typename StorageIndex>
246const typename IncompleteLUT<Scalar, StorageIndex>::FactorType IncompleteLUT<Scalar, StorageIndex>::matrixU() const {
247 eigen_assert(m_factorizationIsOk && "Factorization must be computed first.");
248 return m_lu.template triangularView<Upper>();
249}
250
251// Compute a row permutation m_Pr such that (m_Pr * amat) has a structurally
252// nonzero diagonal wherever one exists. Returns the number of matched columns.
253// Uses a maximum bipartite cardinality matching on the sparsity pattern, with
254// a greedy initialization that prefers the natural diagonal so that matrices
255// already having a nonzero diagonal yield the identity permutation.
256template <typename Scalar, typename StorageIndex>
257template <typename MatrixType_>
258Index IncompleteLUT<Scalar, StorageIndex>::computeRowMatching(const MatrixType_& amat) {
259 using internal::convert_index;
260 const Index n = amat.rows();
261 // We only need amat's column-major sparsity pattern; never read scalar
262 // values. The pattern view aliases amat's index storage when amat is
263 // already a column-major SparseMatrix, and otherwise materializes a CSC
264 // pattern into the scratch buffers.
267 internal::SparsityPatternRef<StorageIndex> pat = internal::make_col_major_pattern_ref(amat, outer_buf, inner_buf);
268 const StorageIndex* outer = pat.outer;
269 const StorageIndex* inner = pat.inner;
270
271 const StorageIndex kUnmatched = StorageIndex(-1);
272 // match_row[j] = original row matched to column j; match_col[i] = column matched to row i.
273 std::vector<StorageIndex> match_row(n, kUnmatched);
274 std::vector<StorageIndex> match_col(n, kUnmatched);
275
276 // The matching uses the stored sparsity pattern only and is independent of
277 // numerical values. This preserves the analyzePattern/factorize contract:
278 // the same analysis is reusable for any matrix sharing this stored pattern.
279 // Phase 1: greedy diagonal preference.
280 for (Index j = 0; j < n; ++j) {
281 const Index col_end = outer[j] + pat.nonZeros(j);
282 for (Index k = outer[j]; k < col_end; ++k) {
283 if (Index(inner[k]) == j) {
284 match_row[j] = convert_index<StorageIndex>(j);
285 match_col[j] = convert_index<StorageIndex>(j);
286 break;
287 }
288 }
289 }
290 // Phase 2: greedy off-diagonal pickup of any free row.
291 for (Index j = 0; j < n; ++j) {
292 if (match_row[j] != kUnmatched) continue;
293 const Index col_end = outer[j] + pat.nonZeros(j);
294 for (Index k = outer[j]; k < col_end; ++k) {
295 Index i = inner[k];
296 if (match_col[i] == kUnmatched) {
297 match_row[j] = convert_index<StorageIndex>(i);
298 match_col[i] = convert_index<StorageIndex>(j);
299 break;
300 }
301 }
302 }
303 // Phase 3: augmenting paths for any column still unmatched.
304 std::vector<StorageIndex> visited(n, kUnmatched);
305 // Iterative DFS: the stack frames are (column, edge index, chosen row).
306 // chosen_row[k] is the row that frame k will commit to if a path is found.
307 std::vector<Index> stack_col;
308 std::vector<Index> stack_pos;
309 std::vector<Index> stack_chosen_row;
310 stack_col.reserve(n);
311 stack_pos.reserve(n);
312 stack_chosen_row.reserve(n);
313
314 for (Index start = 0; start < n; ++start) {
315 if (match_row[start] != kUnmatched) continue;
316 StorageIndex epoch = convert_index<StorageIndex>(start);
317 stack_col.clear();
318 stack_pos.clear();
319 stack_chosen_row.clear();
320 stack_col.push_back(start);
321 stack_pos.push_back(outer[start]);
322 stack_chosen_row.push_back(-1);
323
324 while (!stack_col.empty()) {
325 Index j = stack_col.back();
326 Index pos = stack_pos.back();
327 Index col_end = outer[j] + pat.nonZeros(j);
328 bool advanced = false;
329
330 while (pos < col_end) {
331 Index i = inner[pos];
332 ++pos;
333 if (visited[i] == epoch) continue;
334 visited[i] = epoch;
335
336 if (match_col[i] == kUnmatched) {
337 // Found an augmenting path: commit it.
338 stack_chosen_row.back() = i;
339 stack_pos.back() = pos;
340 for (size_t k = 0; k < stack_col.size(); ++k) {
341 Index col = stack_col[k];
342 Index row = stack_chosen_row[k];
343 match_row[col] = convert_index<StorageIndex>(row);
344 match_col[row] = convert_index<StorageIndex>(col);
345 }
346 stack_col.clear();
347 break;
348 } else {
349 // Descend into the column currently matched to row i.
350 stack_chosen_row.back() = i;
351 stack_pos.back() = pos;
352 Index next_col = match_col[i];
353 stack_col.push_back(next_col);
354 stack_pos.push_back(outer[next_col]);
355 stack_chosen_row.push_back(-1);
356 advanced = true;
357 break;
358 }
359 }
360
361 if (!advanced && !stack_col.empty()) {
362 stack_col.pop_back();
363 stack_pos.pop_back();
364 stack_chosen_row.pop_back();
365 }
366 }
367 }
368
369 // Build the row permutation. Matched columns get their matching row;
370 // any leftover columns are filled in identity-fashion with the leftover rows.
371 m_Pr.resize(n);
372 std::vector<bool> col_used(n, false), row_used(n, false);
373 Index matched = 0;
374 for (Index j = 0; j < n; ++j) {
375 if (match_row[j] != kUnmatched) {
376 m_Pr.indices()(match_row[j]) = convert_index<StorageIndex>(j);
377 col_used[j] = true;
378 row_used[match_row[j]] = true;
379 ++matched;
380 }
381 }
382 Index next_col = 0;
383 for (Index i = 0; i < n; ++i) {
384 if (row_used[i]) continue;
385 while (next_col < n && col_used[next_col]) ++next_col;
386 m_Pr.indices()(i) = convert_index<StorageIndex>(next_col);
387 ++next_col;
388 }
389 return matched;
390}
391
392template <typename Scalar, typename StorageIndex>
393template <typename MatrixType_>
394void IncompleteLUT<Scalar, StorageIndex>::analyzePattern(const MatrixType_& amat) {
395 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(amat, "The factorization should be done on a square matrix");
396 // 1. Compute a static row permutation that makes the diagonal structurally
397 // nonzero. This is a workaround for the lack of partial pivoting in ILUT.
398 // For matrices that already have a nonzero diagonal, this returns the
399 // identity permutation and is essentially free.
400 computeRowMatching(amat);
401
402 // 2. Compute the Fill-reducing permutation on the row-permuted matrix.
403 // Since ILUT does not perform any numerical pivoting, it is highly
404 // preferable to keep the diagonal through symmetric permutations. AMD
405 // computes a fill-reducing ordering for a symmetric matrix and only reads
406 // the sparsity pattern; build a value-free, row-permuted representation
407 // (1-byte placeholder Scalar, indices remapped through m_Pr) and feed that
408 // to AMDOrdering, avoiding the previous mat1/mat2/AtA value copies.
410 {
413 internal::SparsityPatternRef<StorageIndex> pat = internal::make_col_major_pattern_ref(amat, outer_buf, inner_buf);
414 internal::materialize_col_major_pattern(pat, m_Pr.indices().data(), permuted_pattern);
415 }
417 ordering(permuted_pattern, m_P);
418 m_Pinv = m_P.inverse(); // cache the inverse permutation
419 // Cache the composition m_Pinv * m_Pr so _solve_impl applies a single
420 // permutation to the RHS instead of two.
421 m_PinvPr = m_Pinv * m_Pr;
422 m_analysisIsOk = true;
423 m_factorizationIsOk = false;
424 m_isInitialized = true;
425}
426
427template <typename Scalar, typename StorageIndex>
428template <typename MatrixType_>
429void IncompleteLUT<Scalar, StorageIndex>::factorize(const MatrixType_& amat) {
430 using internal::convert_index;
431 using std::swap;
432
433 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(amat, "The factorization should be done on a square matrix");
434 Index n = amat.cols(); // Size of the matrix
435 m_lu.resize(n, n);
436 // Declare Working vectors and variables
437 Vector u(n); // real values of the row -- maximum size is n --
438 VectorI ju(n); // column position of the values in u -- maximum size is n
439 VectorI jr(n); // Indicate the position of the nonzero elements in the vector u -- A zero location is indicated by -1
440
441 // Apply the static row permutation (from analyzePattern), then the
442 // fill-reducing symmetric permutation.
443 eigen_assert(m_analysisIsOk && "You must first call analyzePattern()");
444 SparseMatrix<Scalar, RowMajor, StorageIndex> row_permuted_mat = m_Pr * amat;
446 mat = row_permuted_mat.twistedBy(m_Pinv);
447 Index zero_pivots = 0;
448
449 // Initialization
450 jr.fill(-1);
451 ju.fill(0);
452 u.fill(0);
453
454 // number of largest elements to keep in each row:
455 Index fill_in = (amat.nonZeros() * m_fillfactor) / numext::maxi(n, Index(1)) + 1;
456 if (fill_in > n) fill_in = n;
457
458 // number of largest nonzero elements to keep in the L and the U part of the current row:
459 Index nnzL = fill_in / 2;
460 Index nnzU = nnzL;
461 m_lu.reserve(n * (nnzL + nnzU + 1));
462
463 // global loop over the rows of the sparse matrix
464 for (Index ii = 0; ii < n; ii++) {
465 // 1 - copy the lower and the upper part of the row i of mat in the working vector u
466
467 Index sizeu = 1; // number of nonzero elements in the upper part of the current row
468 Index sizel = 0; // number of nonzero elements in the lower part of the current row
469 ju(ii) = convert_index<StorageIndex>(ii);
470 u(ii) = 0;
471 jr(ii) = convert_index<StorageIndex>(ii);
472 RealScalar rownorm = 0;
473
474 typename FactorType::InnerIterator j_it(mat, ii); // Iterate through the current row ii
475 for (; j_it; ++j_it) {
476 Index k = j_it.index();
477 if (k < ii) {
478 // copy the lower part
479 ju(sizel) = convert_index<StorageIndex>(k);
480 u(sizel) = j_it.value();
481 jr(k) = convert_index<StorageIndex>(sizel);
482 ++sizel;
483 } else if (k == ii) {
484 u(ii) = j_it.value();
485 } else {
486 // copy the upper part
487 Index jpos = ii + sizeu;
488 ju(jpos) = convert_index<StorageIndex>(k);
489 u(jpos) = j_it.value();
490 jr(k) = convert_index<StorageIndex>(jpos);
491 ++sizeu;
492 }
493 rownorm += numext::abs2(j_it.value());
494 }
495
496 // 2 - detect possible zero row
497 if (rownorm == 0) {
498 m_info = NumericalIssue;
499 return;
500 }
501 // Take the 2-norm of the current row as a relative tolerance
502 rownorm = numext::sqrt(rownorm);
503
504 // 3 - eliminate the previous nonzero rows
505 Index jj = 0;
506 Index len = 0;
507 while (jj < sizel) {
508 // In order to eliminate in the correct order,
509 // we must select first the smallest column index among ju(jj:sizel)
510 Index k;
511 Index minrow = ju.segment(jj, sizel - jj).minCoeff(&k); // k is relative to the segment
512 k += jj;
513 if (minrow != ju(jj)) {
514 // swap the two locations
515 Index j = ju(jj);
516 swap(ju(jj), ju(k));
517 jr(minrow) = convert_index<StorageIndex>(jj);
518 jr(j) = convert_index<StorageIndex>(k);
519 swap(u(jj), u(k));
520 }
521 // Reset this location
522 jr(minrow) = -1;
523
524 // Start elimination
525 typename FactorType::InnerIterator ki_it(m_lu, minrow);
526 while (ki_it && ki_it.index() < minrow) ++ki_it;
527 eigen_internal_assert(ki_it && ki_it.col() == minrow);
528 Scalar fact = u(jj) / ki_it.value();
529
530 // drop too small elements
531 if (numext::abs(fact) <= m_droptol) {
532 jj++;
533 continue;
534 }
535
536 // linear combination of the current row ii and the row minrow
537 ++ki_it;
538 for (; ki_it; ++ki_it) {
539 Scalar prod = fact * ki_it.value();
540 Index j = ki_it.index();
541 Index jpos = jr(j);
542 if (jpos == -1) // fill-in element
543 {
544 Index newpos;
545 if (j >= ii) // dealing with the upper part
546 {
547 newpos = ii + sizeu;
548 sizeu++;
549 eigen_internal_assert(sizeu <= n);
550 } else // dealing with the lower part
551 {
552 newpos = sizel;
553 sizel++;
554 eigen_internal_assert(sizel <= ii);
555 }
556 ju(newpos) = convert_index<StorageIndex>(j);
557 u(newpos) = -prod;
558 jr(j) = convert_index<StorageIndex>(newpos);
559 } else
560 u(jpos) -= prod;
561 }
562 // store the pivot element
563 u(len) = fact;
564 ju(len) = convert_index<StorageIndex>(minrow);
565 ++len;
566
567 jj++;
568 } // end of the elimination on the row ii
569
570 // reset the upper part of the pointer jr to zero
571 for (Index k = 0; k < sizeu; k++) jr(ju(ii + k)) = -1;
572
573 // 4 - partially sort and insert the elements in the m_lu matrix
574
575 // sort the L-part of the row
576 sizel = len;
577 len = (std::min)(sizel, nnzL);
578 typename Vector::SegmentReturnType ul(u.segment(0, sizel));
579 typename VectorI::SegmentReturnType jul(ju.segment(0, sizel));
580 internal::QuickSplit(ul, jul, len);
581
582 // store the largest m_fill elements of the L part
583 m_lu.startVec(ii);
584 for (Index k = 0; k < len; k++) m_lu.insertBackByOuterInnerUnordered(ii, ju(k)) = u(k);
585
586 // store the diagonal element
587 // apply a shifting rule to avoid zero pivots (we are doing an incomplete factorization)
588 if (u(ii) == Scalar(0)) {
589 u(ii) = numext::sqrt(m_droptol) * rownorm;
590 ++zero_pivots;
591 }
592 m_lu.insertBackByOuterInnerUnordered(ii, ii) = u(ii);
593
594 // sort the U-part of the row
595 // apply the dropping rule first
596 len = 0;
597 for (Index k = 1; k < sizeu; k++) {
598 if (numext::abs(u(ii + k)) > m_droptol * rownorm) {
599 ++len;
600 u(ii + len) = u(ii + k);
601 ju(ii + len) = ju(ii + k);
602 }
603 }
604 sizeu = len + 1; // +1 to take into account the diagonal element
605 len = (std::min)(sizeu, nnzU);
606 typename Vector::SegmentReturnType uu(u.segment(ii + 1, sizeu - 1));
607 typename VectorI::SegmentReturnType juu(ju.segment(ii + 1, sizeu - 1));
608 internal::QuickSplit(uu, juu, len);
609
610 // store the largest elements of the U part
611 for (Index k = ii + 1; k < ii + len; k++) m_lu.insertBackByOuterInnerUnordered(ii, ju(k)) = u(k);
612 }
613 m_lu.finalize();
614 m_lu.makeCompressed();
615
616 m_factorizationIsOk = true;
617 // If we had to shift any zero pivot, the factorization is not faithful to
618 // the input matrix and the resulting preconditioner may be useless.
619 // Report this to the caller via NumericalIssue rather than silently
620 // returning Success.
621 m_info = (zero_pivots == 0) ? Success : NumericalIssue;
622}
623
624} // end namespace Eigen
625
626#endif // EIGEN_INCOMPLETE_LUT_H
Definition Ordering.h:31
void setFillfactor(int fillfactor)
Definition IncompleteLUT.h:225
IncompleteLUT & compute(const MatrixType &amat)
Definition IncompleteLUT.h:172
const FactorType matrixL() const
Extraction Method for L-Factor.
Definition IncompleteLUT.h:235
const FactorType matrixU() const
Extraction Method for U-Factor.
Definition IncompleteLUT.h:246
void setDroptol(const RealScalar &droptol)
Definition IncompleteLUT.h:216
ComputationInfo info() const
Reports whether previous computation was successful.
Definition IncompleteLUT.h:151
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Permutation matrix.
Definition PermutationMatrix.h:346
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
ComputationInfo
Definition Constants.h:455
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
Matrix< Type, Size, 1 > Vector
Size×1 vector of type Type.
Definition Matrix.h:532
Definition IncompleteLUT.h:191