12#ifndef EIGEN_INCOMPLETE_LUT_H
13#define EIGEN_INCOMPLETE_LUT_H
16#include "./InternalHeaderCheck.h"
31template <
typename VectorV,
typename VectorI>
32Index QuickSplit(VectorV& row, VectorI& ind, Index ncut) {
33 using RealScalar =
typename VectorV::RealScalar;
42 if (ncut < first || ncut > last)
return 0;
46 RealScalar abskey = numext::abs(row(mid));
47 for (Index j = first + 1; j <= last; j++) {
48 if (numext::abs(row(j)) > abskey) {
50 swap(row(mid), row(j));
51 swap(ind(mid), ind(j));
55 swap(row(mid), row(first));
56 swap(ind(mid), ind(first));
62 }
while (mid != ncut);
101template <
typename Scalar_,
typename StorageIndex_ =
int>
105 using Base::m_isInitialized;
108 using Scalar = Scalar_;
109 using StorageIndex = StorageIndex_;
110 using RealScalar =
typename NumTraits<Scalar>::Real;
115 enum { ColsAtCompileTime = Dynamic, MaxColsAtCompileTime = Dynamic };
119 : m_droptol(NumTraits<Scalar>::dummy_precision()),
121 m_analysisIsOk(
false),
122 m_factorizationIsOk(
false) {}
124 template <
typename MatrixType>
125 explicit IncompleteLUT(
const MatrixType& mat,
const RealScalar& droptol = NumTraits<Scalar>::dummy_precision(),
127 : m_droptol(droptol), m_fillfactor(fillfactor), m_analysisIsOk(
false), m_factorizationIsOk(
false) {
128 eigen_assert(fillfactor != 0);
133 const FactorType
matrixL()
const;
136 const FactorType
matrixU()
const;
138 constexpr Index rows()
const noexcept {
return m_lu.rows(); }
140 constexpr Index cols()
const noexcept {
return m_lu.cols(); }
152 eigen_assert(m_isInitialized &&
"IncompleteLUT is not initialized.");
156 template <
typename MatrixType>
157 void analyzePattern(
const MatrixType& amat);
159 template <
typename MatrixType>
160 void factorize(
const MatrixType& amat);
171 template <
typename MatrixType>
172 IncompleteLUT&
compute(
const MatrixType& amat) {
173 analyzePattern(amat);
181 template <
typename Rhs,
typename Dest>
182 void _solve_impl(
const Rhs& b, Dest& x)
const {
184 x = m_lu.template triangularView<UnitLower>().solve(x);
185 x = m_lu.template triangularView<Upper>().solve(x);
192 inline bool operator()(
const Index& row,
const Index& col,
const Scalar&)
const {
return row != col; }
195 template <
typename MatrixType>
196 Index computeRowMatching(
const MatrixType& amat);
200 RealScalar m_droptol;
203 bool m_factorizationIsOk;
215template <
typename Scalar,
typename StorageIndex>
217 this->m_droptol = droptol;
224template <
typename Scalar,
typename StorageIndex>
226 this->m_fillfactor = fillfactor;
234template <
typename Scalar,
typename StorageIndex>
236 eigen_assert(m_factorizationIsOk &&
"factorize() should be called first");
237 return m_lu.template triangularView<UnitLower>();
245template <
typename Scalar,
typename StorageIndex>
247 eigen_assert(m_factorizationIsOk &&
"Factorization must be computed first.");
248 return m_lu.template triangularView<Upper>();
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();
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;
271 const StorageIndex kUnmatched = StorageIndex(-1);
273 std::vector<StorageIndex> match_row(n, kUnmatched);
274 std::vector<StorageIndex> match_col(n, kUnmatched);
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);
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) {
296 if (match_col[i] == kUnmatched) {
297 match_row[j] = convert_index<StorageIndex>(i);
298 match_col[i] = convert_index<StorageIndex>(j);
304 std::vector<StorageIndex> visited(n, kUnmatched);
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);
314 for (Index start = 0; start < n; ++start) {
315 if (match_row[start] != kUnmatched)
continue;
316 StorageIndex epoch = convert_index<StorageIndex>(start);
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);
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;
330 while (pos < col_end) {
331 Index i = inner[pos];
333 if (visited[i] == epoch)
continue;
336 if (match_col[i] == kUnmatched) {
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);
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);
361 if (!advanced && !stack_col.empty()) {
362 stack_col.pop_back();
363 stack_pos.pop_back();
364 stack_chosen_row.pop_back();
372 std::vector<bool> col_used(n,
false), row_used(n,
false);
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);
378 row_used[match_row[j]] =
true;
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);
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");
400 computeRowMatching(amat);
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);
417 ordering(permuted_pattern, m_P);
418 m_Pinv = m_P.inverse();
421 m_PinvPr = m_Pinv * m_Pr;
422 m_analysisIsOk =
true;
423 m_factorizationIsOk =
false;
424 m_isInitialized =
true;
427template <
typename Scalar,
typename StorageIndex>
428template <
typename MatrixType_>
429void IncompleteLUT<Scalar, StorageIndex>::factorize(
const MatrixType_& amat) {
430 using internal::convert_index;
433 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(amat,
"The factorization should be done on a square matrix");
434 Index n = amat.cols();
443 eigen_assert(m_analysisIsOk &&
"You must first call analyzePattern()");
446 mat = row_permuted_mat.twistedBy(m_Pinv);
447 Index zero_pivots = 0;
455 Index fill_in = (amat.nonZeros() * m_fillfactor) / numext::maxi(n, Index(1)) + 1;
456 if (fill_in > n) fill_in = n;
459 Index nnzL = fill_in / 2;
461 m_lu.reserve(n * (nnzL + nnzU + 1));
464 for (Index ii = 0; ii < n; ii++) {
469 ju(ii) = convert_index<StorageIndex>(ii);
471 jr(ii) = convert_index<StorageIndex>(ii);
472 RealScalar rownorm = 0;
474 typename FactorType::InnerIterator j_it(mat, ii);
475 for (; j_it; ++j_it) {
476 Index k = j_it.index();
479 ju(sizel) = convert_index<StorageIndex>(k);
480 u(sizel) = j_it.value();
481 jr(k) = convert_index<StorageIndex>(sizel);
483 }
else if (k == ii) {
484 u(ii) = j_it.value();
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);
493 rownorm += numext::abs2(j_it.value());
502 rownorm = numext::sqrt(rownorm);
511 Index minrow = ju.segment(jj, sizel - jj).minCoeff(&k);
513 if (minrow != ju(jj)) {
517 jr(minrow) = convert_index<StorageIndex>(jj);
518 jr(j) = convert_index<StorageIndex>(k);
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();
531 if (numext::abs(fact) <= m_droptol) {
538 for (; ki_it; ++ki_it) {
539 Scalar prod = fact * ki_it.value();
540 Index j = ki_it.index();
549 eigen_internal_assert(sizeu <= n);
554 eigen_internal_assert(sizel <= ii);
556 ju(newpos) = convert_index<StorageIndex>(j);
558 jr(j) = convert_index<StorageIndex>(newpos);
564 ju(len) = convert_index<StorageIndex>(minrow);
571 for (Index k = 0; k < sizeu; k++) jr(ju(ii + k)) = -1;
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);
584 for (Index k = 0; k < len; k++) m_lu.insertBackByOuterInnerUnordered(ii, ju(k)) = u(k);
588 if (u(ii) == Scalar(0)) {
589 u(ii) = numext::sqrt(m_droptol) * rownorm;
592 m_lu.insertBackByOuterInnerUnordered(ii, ii) = u(ii);
597 for (Index k = 1; k < sizeu; k++) {
598 if (numext::abs(u(ii + k)) > m_droptol * rownorm) {
600 u(ii + len) = u(ii + k);
601 ju(ii + len) = ju(ii + k);
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);
611 for (Index k = ii + 1; k < ii + len; k++) m_lu.insertBackByOuterInnerUnordered(ii, ju(k)) = u(k);
614 m_lu.makeCompressed();
616 m_factorizationIsOk =
true;
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
SparseSolverBase()=default
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