Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseLU.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) 2012-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_SPARSE_LU_H
13#define EIGEN_SPARSE_LU_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20template <typename MatrixType_, typename OrderingType_ = COLAMDOrdering<typename MatrixType_::StorageIndex>>
21class SparseLU;
22template <typename MappedSparseMatrixType>
23struct SparseLUMatrixLReturnType;
24template <typename MatrixLType, typename MatrixUType>
25struct SparseLUMatrixUReturnType;
26
27template <bool Conjugate, class SparseLUType>
28class SparseLUTransposeView : public SparseSolverBase<SparseLUTransposeView<Conjugate, SparseLUType>> {
29 protected:
31 using APIBase::m_isInitialized;
32
33 public:
34 using Scalar = typename SparseLUType::Scalar;
35 using StorageIndex = typename SparseLUType::StorageIndex;
36 using MatrixType = typename SparseLUType::MatrixType;
37 using OrderingType = typename SparseLUType::OrderingType;
38
39 enum { ColsAtCompileTime = MatrixType::ColsAtCompileTime, MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime };
40
41 SparseLUTransposeView() = default;
42 SparseLUTransposeView(const SparseLUTransposeView& view) : APIBase() {
43 this->m_sparseLU = view.m_sparseLU;
44 this->m_isInitialized = view.m_isInitialized;
45 }
46 void setIsInitialized(const bool isInitialized) { this->m_isInitialized = isInitialized; }
47 void setSparseLU(SparseLUType* sparseLU) { m_sparseLU = sparseLU; }
48 using APIBase::_solve_impl;
49 template <typename Rhs, typename Dest>
50 bool _solve_impl(const MatrixBase<Rhs>& B, MatrixBase<Dest>& X_base) const {
51 Dest& X(X_base.derived());
52 eigen_assert(m_sparseLU->info() == Success && "The matrix should be factorized first");
53 EIGEN_STATIC_ASSERT((Dest::Flags & RowMajorBit) == 0, THIS_METHOD_IS_ONLY_FOR_COLUMN_MAJOR_MATRICES);
54
55 // const_cast_derived() is needed to enable aliasing detection when applying the permutations.
56 for (Index j = 0; j < B.cols(); ++j) {
57 X.col(j) = m_sparseLU->colsPermutation() * B.const_cast_derived().col(j);
58 }
59 // Forward substitution with transposed or adjoint of U
60 m_sparseLU->matrixU().template solveTransposedInPlace<Conjugate>(X);
61
62 // Backward substitution with transposed or adjoint of L
63 m_sparseLU->matrixL().template solveTransposedInPlace<Conjugate>(X);
64
65 // Permute back the solution
66 for (Index j = 0; j < B.cols(); ++j) X.col(j) = m_sparseLU->rowsPermutation().transpose() * X.col(j);
67 return true;
68 }
69 inline Index rows() const { return m_sparseLU->rows(); }
70 inline Index cols() const { return m_sparseLU->cols(); }
71
72 private:
73 SparseLUType* m_sparseLU = nullptr;
74 SparseLUTransposeView& operator=(const SparseLUTransposeView&) = delete;
75};
76
150template <typename MatrixType_, typename OrderingType_>
151class SparseLU : public SparseSolverBase<SparseLU<MatrixType_, OrderingType_>>,
152 public internal::SparseLUImpl<typename MatrixType_::Scalar, typename MatrixType_::StorageIndex> {
153 protected:
155 using APIBase::m_isInitialized;
156
157 public:
158 using APIBase::_solve_impl;
159
160 using MatrixType = MatrixType_;
161 using OrderingType = OrderingType_;
162 using Scalar = typename MatrixType::Scalar;
163 using RealScalar = typename MatrixType::RealScalar;
164 using StorageIndex = typename MatrixType::StorageIndex;
167 using ScalarVector = Matrix<Scalar, Dynamic, 1>;
168 using IndexVector = Matrix<StorageIndex, Dynamic, 1>;
171
172 enum { ColsAtCompileTime = MatrixType::ColsAtCompileTime, MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime };
173
174 public:
180 : m_lastError(""), m_Ustore(0, 0, 0, 0, 0, 0), m_symmetricmode(false), m_diagpivotthresh(1.0), m_detPermR(1) {
181 initperfvalues();
182 }
183
187 explicit SparseLU(const MatrixType& matrix)
188 : m_lastError(""), m_Ustore(0, 0, 0, 0, 0, 0), m_symmetricmode(false), m_diagpivotthresh(1.0), m_detPermR(1) {
189 initperfvalues();
190 compute(matrix);
191 }
192
193 ~SparseLU() {
194 // Free all explicit dynamic pointers
195 }
196
197 void analyzePattern(const MatrixType& matrix);
198 void factorize(const MatrixType& matrix);
199 void simplicialfactorize(const MatrixType& matrix);
200
211 void compute(const MatrixType& matrix) {
212 // Analyze
213 analyzePattern(matrix);
214 // Factorize
215 factorize(matrix);
216 }
217
230 const SparseLUTransposeView<false, SparseLU<MatrixType_, OrderingType_>> transpose() {
231 SparseLUTransposeView<false, SparseLU<MatrixType_, OrderingType_>> transposeView;
232 transposeView.setSparseLU(this);
233 transposeView.setIsInitialized(this->m_isInitialized);
234 return transposeView;
235 }
236
251 const SparseLUTransposeView<true, SparseLU<MatrixType_, OrderingType_>> adjoint() {
252 SparseLUTransposeView<true, SparseLU<MatrixType_, OrderingType_>> adjointView;
253 adjointView.setSparseLU(this);
254 adjointView.setIsInitialized(this->m_isInitialized);
255 return adjointView;
256 }
257
260 inline Index rows() const { return m_mat.rows(); }
263 inline Index cols() const { return m_mat.cols(); }
266 void isSymmetric(bool sym) { m_symmetricmode = sym; }
267
276 SparseLUMatrixLReturnType<SCMatrix> matrixL() const { return SparseLUMatrixLReturnType<SCMatrix>(m_Lstore); }
285 SparseLUMatrixUReturnType<SCMatrix, Map<SparseMatrix<Scalar, ColMajor, StorageIndex>>> matrixU() const {
286 return SparseLUMatrixUReturnType<SCMatrix, Map<SparseMatrix<Scalar, ColMajor, StorageIndex>>>(m_Lstore, m_Ustore);
287 }
288
294 inline const PermutationType& rowsPermutation() const { return m_perm_r; }
300 inline const PermutationType& colsPermutation() const { return m_perm_c; }
302 void setPivotThreshold(const RealScalar& thresh) { m_diagpivotthresh = thresh; }
303
304#ifdef EIGEN_PARSED_BY_DOXYGEN
313 template <typename Rhs>
315#endif // EIGEN_PARSED_BY_DOXYGEN
316
328 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
329 return m_info;
330 }
331
336 std::string lastErrorMessage() const { return m_lastError; }
337
338 template <typename Rhs, typename Dest>
339 bool _solve_impl(const MatrixBase<Rhs>& B, MatrixBase<Dest>& X_base) const {
340 Dest& X(X_base.derived());
341 eigen_assert(m_factorizationIsOk && "The matrix should be factorized first");
342 EIGEN_STATIC_ASSERT((Dest::Flags & RowMajorBit) == 0, THIS_METHOD_IS_ONLY_FOR_COLUMN_MAJOR_MATRICES);
343
344 // Permute the right hand side to form X = Pr*B
345 // on return, X is overwritten by the computed solution
346 X.resize(B.rows(), B.cols());
347
348 // const_cast_derived() is needed to enable aliasing detection when applying the permutations.
349 for (Index j = 0; j < B.cols(); ++j) X.col(j) = rowsPermutation() * B.const_cast_derived().col(j);
350
351 // Forward substitution with L
352 this->matrixL().solveInPlace(X);
353 this->matrixU().solveInPlace(X);
354
355 // Permute back the solution
356 for (Index j = 0; j < B.cols(); ++j) X.col(j) = colsPermutation().inverse() * X.col(j);
357
358 return true;
359 }
360
372 Scalar absDeterminant() const {
373 eigen_assert(m_factorizationIsOk && "The matrix should be factorized first.");
374 return diagonalProduct().abs();
375 }
376
387 Scalar logAbsDeterminant() const {
388 eigen_assert(m_factorizationIsOk && "The matrix should be factorized first.");
389 EIGEN_IF_CONSTEXPR (internal::has_scaled_product<Scalar>::value) return diagonalProduct().logAbs();
390 Scalar det = Scalar(0.);
391 for (Index j = 0; j < this->cols(); ++j) {
392 for (typename SCMatrix::InnerIterator it(m_Lstore, j); it; ++it) {
393 if (it.row() < j) continue;
394 if (it.row() == j) {
395 det += numext::log(numext::abs(it.value()));
396 break;
397 }
398 }
399 }
400 return det;
401 }
402
410 Scalar signDeterminant() const {
411 eigen_assert(m_factorizationIsOk && "The matrix should be factorized first.");
412 // Initialize with the determinant of the row matrix
413 Scalar det = Scalar(1);
414 // Note that the diagonal blocks of U are stored in supernodes,
415 // which are available in the L part :)
416 for (Index j = 0; j < this->cols(); ++j) {
417 for (typename SCMatrix::InnerIterator it(m_Lstore, j); it; ++it) {
418 if (it.index() == j) {
419 const Scalar pivotSign = numext::sign(it.value());
420 if (pivotSign == Scalar(0)) return Scalar(0);
421 det *= pivotSign;
422 break;
423 }
424 }
425 }
426 return det * Scalar(m_detPermR * m_detPermC);
427 }
428
435 Scalar determinant() const {
436 eigen_assert(m_factorizationIsOk && "The matrix should be factorized first.");
437 const Scalar det = diagonalProduct().value();
438 return (m_detPermR * m_detPermC) > 0 ? det : -det;
439 }
440
443 Index nnzL() const { return m_nnzL; }
446 Index nnzU() const { return m_nnzU; }
447
448 protected:
449 // Functions
450
451 // The product of the diagonal of U. The diagonal blocks of U are stored in the supernodes of L.
452 internal::scaled_product<Scalar> diagonalProduct() const {
453 internal::scaled_product<Scalar> product;
454 for (Index j = 0; j < this->cols(); ++j) {
455 for (typename SCMatrix::InnerIterator it(m_Lstore, j); it; ++it) {
456 if (it.index() == j) {
457 product.multiply(it.value());
458 break;
459 }
460 }
461 }
462 return product;
463 }
464
465 void initperfvalues() {
466 m_perfv.panel_size = 16;
467 m_perfv.relax = 1;
468 m_perfv.maxsuper = 128;
469 m_perfv.rowblk = 16;
470 m_perfv.colblk = 8;
471 m_perfv.fillfactor = 20;
472 }
473
474 // Variables
475 mutable ComputationInfo m_info;
476 bool m_factorizationIsOk;
477 bool m_analysisIsOk;
478 std::string m_lastError;
479 NCMatrix m_mat; // The input (permuted ) matrix
480 SCMatrix m_Lstore; // The lower triangular matrix (supernodal)
481 Map<SparseMatrix<Scalar, ColMajor, StorageIndex>> m_Ustore; // The upper triangular matrix
482 PermutationType m_perm_c; // Column permutation
483 PermutationType m_perm_r; // Row permutation
484 IndexVector m_etree; // Column elimination tree
485
486 typename Base::GlobalLU_t m_glu;
487
488 // SparseLU options
489 bool m_symmetricmode;
490 // values for performance
491 internal::perfvalues m_perfv;
492 RealScalar m_diagpivotthresh; // Specifies the threshold used for a diagonal entry to be an acceptable pivot
493 Index m_nnzL, m_nnzU; // Nonzeros in L and U factors
494 Index m_detPermR, m_detPermC; // Determinants of the permutation matrices
495 private:
496 SparseLU(const SparseLU&) = delete;
497}; // End class SparseLU
498
499// Functions needed by the analysis phase
516template <typename MatrixType, typename OrderingType>
518 // TODO It is possible as in SuperLU to compute row and column scaling vectors to equilibrate the matrix mat.
519
520 // Firstly, copy the whole input matrix.
521 m_mat = mat;
522
523 // Compute fill-in ordering
524 OrderingType ord;
525 ord(m_mat, m_perm_c);
526
527 // Apply the permutation to the column of the input matrix
528 if (m_perm_c.size()) {
529 // Switch to uncompressed mode so innerNonZeroPtr() exists and can be
530 // permuted consistently with outerIndexPtr().
531 // Downstream sparse traversals may also rely on these per-column counts
532 // while m_mat remains uncompressed.
533 m_mat.uncompress();
534 // A compressed column-major input already exposes valid column pointers.
535 // Otherwise snapshot the internal column-major structure before permuting in place.
536 const bool useInputOuterIndex = !MatrixType::IsRowMajor && mat.isCompressed();
537 ei_declare_aligned_stack_constructed_variable(
538 StorageIndex, outerIndexPtr, m_mat.cols() + 1,
539 useInputOuterIndex ? const_cast<StorageIndex*>(mat.outerIndexPtr()) : 0);
540 if (!useInputOuterIndex)
541 IndexVector::Map(outerIndexPtr, m_mat.cols() + 1) = IndexVector::Map(m_mat.outerIndexPtr(), m_mat.cols() + 1);
542
543 // Apply the permutation and compute the nnz per column.
544 for (Index i = 0; i < mat.cols(); i++) {
545 m_mat.outerIndexPtr()[m_perm_c.indices()(i)] = outerIndexPtr[i];
546 m_mat.innerNonZeroPtr()[m_perm_c.indices()(i)] = outerIndexPtr[i + 1] - outerIndexPtr[i];
547 }
548 }
549
550 // Compute the column elimination tree of the permuted matrix
551 IndexVector firstRowElt;
552 internal::coletree(m_mat, m_etree, firstRowElt);
553
554 // In symmetric mode, do not do postorder here
555 if (!m_symmetricmode) {
556 IndexVector post, iwork;
557 // Post order etree
558 internal::treePostorder(StorageIndex(m_mat.cols()), m_etree, post);
559
560 // Renumber etree in postorder
561 Index m = m_mat.cols();
562 iwork.resize(m);
563 for (Index i = 0; i < m; ++i) iwork(post(i)) = post(m_etree(i));
564 m_etree = iwork;
565
566 // Postmultiply A*Pc by post, i.e reorder the matrix according to the postorder of the etree
567 PermutationType post_perm(m);
568 for (Index i = 0; i < m; i++) post_perm.indices()(i) = post(i);
569
570 // Combine the two permutations : postorder the permutation for future use
571 if (m_perm_c.size()) {
572 m_perm_c = post_perm * m_perm_c;
573 }
574
575 } // end postordering
576
577 m_analysisIsOk = true;
578}
579
580// Functions needed by the numerical factorization phase
581
601template <typename MatrixType, typename OrderingType>
602void SparseLU<MatrixType, OrderingType>::factorize(const MatrixType& matrix) {
603 using internal::emptyIdxLU;
604 eigen_assert(m_analysisIsOk && "analyzePattern() should be called first");
605 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(matrix, "Only for squared matrices");
606
607 m_isInitialized = true;
608
609 // Reset state from any prior factorize() so info() and lastErrorMessage()
610 // describe this call's outcome, not the previous matrix's.
611 m_info = Success;
612 m_lastError.clear();
613
614 // Apply the column permutation computed in analyzepattern()
615 m_mat = matrix;
616 if (m_perm_c.size()) {
617 // Switch to uncompressed mode so innerNonZeroPtr() exists and can be
618 // permuted consistently with outerIndexPtr().
619 m_mat.uncompress();
620 const bool useInputOuterIndex = !MatrixType::IsRowMajor && matrix.isCompressed();
621 ei_declare_aligned_stack_constructed_variable(
622 StorageIndex, outerIndexPtr, m_mat.cols() + 1,
623 useInputOuterIndex ? const_cast<StorageIndex*>(matrix.outerIndexPtr()) : 0);
624 if (!useInputOuterIndex)
625 IndexVector::Map(outerIndexPtr, m_mat.cols() + 1) = IndexVector::Map(m_mat.outerIndexPtr(), m_mat.cols() + 1);
626 for (Index i = 0; i < matrix.cols(); i++) {
627 m_mat.outerIndexPtr()[m_perm_c.indices()(i)] = outerIndexPtr[i];
628 m_mat.innerNonZeroPtr()[m_perm_c.indices()(i)] = outerIndexPtr[i + 1] - outerIndexPtr[i];
629 }
630 } else { // FIXME This should not be needed if the empty permutation is handled transparently
631 m_perm_c.resize(matrix.cols());
632 for (StorageIndex i = 0; i < matrix.cols(); ++i) m_perm_c.indices()(i) = i;
633 }
634
635 Index m = m_mat.rows();
636 Index n = m_mat.cols();
637 Index nnz = m_mat.nonZeros();
638 Index maxpanel = m_perfv.panel_size * m;
639 // Allocate working storage common to the factor routines
640 Index lwork = 0;
641 // Return the size of actually allocated memory when allocation failed,
642 // and 0 on success.
643 Index info = Base::memInit(m, n, nnz, lwork, m_perfv.fillfactor, m_perfv.panel_size, m_glu);
644 if (info) {
645 m_lastError = "UNABLE TO ALLOCATE WORKING MEMORY\n\n";
646 m_factorizationIsOk = false;
647 return;
648 }
649
650 // Set up pointers for integer working arrays
651 IndexVector segrep(m);
652 segrep.setZero();
653 IndexVector parent(m);
654 parent.setZero();
655 IndexVector xplore(m);
656 xplore.setZero();
657 IndexVector repfnz(maxpanel);
658 IndexVector panel_lsub(maxpanel);
659 IndexVector xprune(n);
660 xprune.setZero();
661 IndexVector marker(m * internal::LUNoMarker);
662 marker.setZero();
663
664 repfnz.setConstant(-1);
665 panel_lsub.setConstant(-1);
666
667 // Set up pointers for scalar working arrays
668 ScalarVector dense;
669 dense.setZero(maxpanel);
670 ScalarVector tempv;
671 tempv.setZero(internal::LUnumTempV(m, m_perfv.panel_size, m_perfv.maxsuper, /*m_perfv.rowblk*/ m));
672
673 // Compute the inverse of perm_c
674 PermutationType iperm_c(m_perm_c.inverse());
675
676 // Identify initial relaxed snodes
677 IndexVector relax_end(n);
678 if (m_symmetricmode == true)
679 Base::heap_relax_snode(n, m_etree, m_perfv.relax, marker, relax_end);
680 else
681 Base::relax_snode(n, m_etree, m_perfv.relax, marker, relax_end);
682
683 m_perm_r.resize(m);
684 m_perm_r.indices().setConstant(-1);
685 marker.setConstant(-1);
686 m_detPermR = 1; // Record the determinant of the row permutation
687
688 m_glu.supno(0) = emptyIdxLU;
689 m_glu.xsup.setConstant(0);
690 m_glu.xsup(0) = m_glu.xlsub(0) = m_glu.xusub(0) = m_glu.xlusup(0) = Index(0);
691
692 // Work on one 'panel' at a time. A panel is one of the following :
693 // (a) a relaxed supernode at the bottom of the etree, or
694 // (b) panel_size contiguous columns, <panel_size> defined by the user
695 Index jcol;
696 Index pivrow; // Pivotal row number in the original row matrix
697 Index nseg1; // Number of segments in U-column above panel row jcol
698 Index nseg; // Number of segments in each U-column
699 Index irep;
700 Index i, k, jj;
701 for (jcol = 0; jcol < n;) {
702 // Adjust panel size so that a panel won't overlap with the next relaxed snode.
703 Index panel_size = m_perfv.panel_size; // upper bound on panel width
704 for (k = jcol + 1; k < (std::min)(jcol + panel_size, n); k++) {
705 if (relax_end(k) != emptyIdxLU) {
706 panel_size = k - jcol;
707 break;
708 }
709 }
710 if (k == n) panel_size = n - jcol;
711
712 // Symbolic outer factorization on a panel of columns
713 Base::panel_dfs(m, panel_size, jcol, m_mat, m_perm_r.indices(), nseg1, dense, panel_lsub, segrep, repfnz, xprune,
714 marker, parent, xplore, m_glu);
715
716 // Numeric sup-panel updates in topological order
717 Base::panel_bmod(m, panel_size, jcol, nseg1, dense, tempv, segrep, repfnz, m_glu);
718
719 // Sparse LU within the panel, and below the panel diagonal
720 for (jj = jcol; jj < jcol + panel_size; jj++) {
721 k = (jj - jcol) * m; // Column index for w-wide arrays
722
723 nseg = nseg1; // begin after all the panel segments
724 // Depth-first-search for the current column
725 VectorBlock<IndexVector> panel_lsubk(panel_lsub, k, m);
726 VectorBlock<IndexVector> repfnz_k(repfnz, k, m);
727 // Return 0 on success and > 0 number of bytes allocated when run out of space.
728 info = Base::column_dfs(m, jj, m_perm_r.indices(), m_perfv.maxsuper, nseg, panel_lsubk, segrep, repfnz_k, xprune,
729 marker, parent, xplore, m_glu);
730 if (info) {
731 m_lastError = "UNABLE TO EXPAND MEMORY IN COLUMN_DFS() ";
732 m_info = NumericalIssue;
733 m_factorizationIsOk = false;
734 return;
735 }
736 // Numeric updates to this column
737 VectorBlock<ScalarVector> dense_k(dense, k, m);
738 VectorBlock<IndexVector> segrep_k(segrep, nseg1, m - nseg1);
739 // Return 0 on success and > 0 number of bytes allocated when run out of space.
740 info = Base::column_bmod(jj, (nseg - nseg1), dense_k, tempv, segrep_k, repfnz_k, jcol, m_glu);
741 if (info) {
742 m_lastError = "UNABLE TO EXPAND MEMORY IN COLUMN_BMOD() ";
743 m_info = NumericalIssue;
744 m_factorizationIsOk = false;
745 return;
746 }
747
748 // Copy the U-segments to ucol(*)
749 // Return 0 on success and > 0 number of bytes allocated when run out of space.
750 info = Base::copy_to_ucol(jj, nseg, segrep, repfnz_k, m_perm_r.indices(), dense_k, m_glu);
751 if (info) {
752 m_lastError = "UNABLE TO EXPAND MEMORY IN COPY_TO_UCOL() ";
753 m_info = NumericalIssue;
754 m_factorizationIsOk = false;
755 return;
756 }
757
758 // Form the L-segment
759 // Return 0 if success, i > 0 if U(i, i) is exactly zero.
760 info = Base::pivotL(jj, m_diagpivotthresh, m_perm_r.indices(), iperm_c.indices(), pivrow, m_glu);
761 if (info) {
762 m_lastError = "THE MATRIX IS STRUCTURALLY SINGULAR";
763#ifndef EIGEN_NO_IO
764 std::ostringstream returnInfo;
765 returnInfo << " ... ZERO COLUMN AT ";
766 returnInfo << info;
767 m_lastError += returnInfo.str();
768#endif
769 m_info = NumericalIssue;
770 m_factorizationIsOk = false;
771 return;
772 }
773
774 // Prune columns (0:jj-1) using column jj
775 Base::pruneL(jj, m_perm_r.indices(), pivrow, nseg, segrep, repfnz_k, xprune, m_glu);
776
777 // Reset repfnz for this column
778 for (i = 0; i < nseg; i++) {
779 irep = segrep(i);
780 repfnz_k(irep) = emptyIdxLU;
781 }
782 } // end SparseLU within the panel
783 jcol += panel_size; // Move to the next panel
784 } // end for -- end elimination
785
786 m_detPermR = m_perm_r.determinant();
787 m_detPermC = m_perm_c.determinant();
788
789 // Count the number of nonzeros in factors
790 Base::countnz(n, m_nnzL, m_nnzU, m_glu);
791 // Apply permutation to the L subscripts
792 Base::fixupL(n, m_perm_r.indices(), m_glu);
793
794 // Create supernode matrix L
795 m_Lstore.setInfos(m, n, m_glu.lusup, m_glu.xlusup, m_glu.lsub, m_glu.xlsub, m_glu.supno, m_glu.xsup);
796 // Create the column major upper sparse matrix U;
797 new (&m_Ustore) Map<SparseMatrix<Scalar, ColMajor, StorageIndex>>(m, n, m_nnzU, m_glu.xusub.data(), m_glu.usub.data(),
798 m_glu.ucol.data());
799
800 m_info = Success;
801 m_factorizationIsOk = true;
802}
803
804template <typename MappedSupernodalType>
805struct SparseLUMatrixLReturnType : internal::no_assignment_operator {
806 using Scalar = typename MappedSupernodalType::Scalar;
807 explicit SparseLUMatrixLReturnType(const MappedSupernodalType& mapL) : m_mapL(mapL) {}
808 Index rows() const { return m_mapL.rows(); }
809 Index cols() const { return m_mapL.cols(); }
810 template <typename Dest>
811 void solveInPlace(MatrixBase<Dest>& X) const {
812 m_mapL.solveInPlace(X);
813 }
814 template <bool Conjugate, typename Dest>
815 void solveTransposedInPlace(MatrixBase<Dest>& X) const {
816 m_mapL.template solveTransposedInPlace<Conjugate>(X);
817 }
818
819 SparseMatrix<Scalar, ColMajor, Index> toSparse() const {
820 ArrayXi colCount = ArrayXi::Ones(cols());
821 for (Index i = 0; i < cols(); i++) {
822 typename MappedSupernodalType::InnerIterator iter(m_mapL, i);
823 for (; iter; ++iter) {
824 if (iter.row() > iter.col()) {
825 colCount(iter.col())++;
826 }
827 }
828 }
829 SparseMatrix<Scalar, ColMajor, Index> sL(rows(), cols());
830 sL.reserve(colCount);
831 for (Index i = 0; i < cols(); i++) {
832 sL.insert(i, i) = 1.0;
833 typename MappedSupernodalType::InnerIterator iter(m_mapL, i);
834 for (; iter; ++iter) {
835 if (iter.row() > iter.col()) {
836 sL.insert(iter.row(), iter.col()) = iter.value();
837 }
838 }
839 }
840 sL.makeCompressed();
841 return sL;
842 }
843
844 const MappedSupernodalType& m_mapL;
845};
846
847template <typename MatrixLType, typename MatrixUType>
848struct SparseLUMatrixUReturnType : internal::no_assignment_operator {
849 using Scalar = typename MatrixLType::Scalar;
850 SparseLUMatrixUReturnType(const MatrixLType& mapL, const MatrixUType& mapU) : m_mapL(mapL), m_mapU(mapU) {}
851 Index rows() const { return m_mapL.rows(); }
852 Index cols() const { return m_mapL.cols(); }
853
854 template <typename Dest>
855 void solveInPlace(MatrixBase<Dest>& X) const {
856 Index nrhs = X.cols();
857 // Backward solve with U
858 for (Index k = m_mapL.nsuper(); k >= 0; k--) {
859 Index fsupc = m_mapL.supToCol()[k];
860 Index lda = m_mapL.colIndexPtr()[fsupc + 1] - m_mapL.colIndexPtr()[fsupc]; // leading dimension
861 Index nsupc = m_mapL.supToCol()[k + 1] - fsupc;
862 Index luptr = m_mapL.colIndexPtr()[fsupc];
863
864 if (nsupc == 1) {
865 for (Index j = 0; j < nrhs; j++) {
866 X(fsupc, j) /= m_mapL.valuePtr()[luptr];
867 }
868 } else {
869 // FIXME: the following lines should use Block expressions and not Map!
870 Map<const Matrix<Scalar, Dynamic, Dynamic, ColMajor>, 0, OuterStride<>> A(&(m_mapL.valuePtr()[luptr]), nsupc,
871 nsupc, OuterStride<>(lda));
872 typename Dest::RowsBlockXpr U = X.derived().middleRows(fsupc, nsupc);
873 U = A.template triangularView<Upper>().solve(U);
874 }
875
876 for (Index j = 0; j < nrhs; ++j) {
877 for (Index jcol = fsupc; jcol < fsupc + nsupc; jcol++) {
878 typename MatrixUType::InnerIterator it(m_mapU, jcol);
879 for (; it; ++it) {
880 Index irow = it.index();
881 X(irow, j) -= X(jcol, j) * it.value();
882 }
883 }
884 }
885 } // End For U-solve
886 }
887
888 template <bool Conjugate, typename Dest>
889 void solveTransposedInPlace(MatrixBase<Dest>& X) const {
890 Index nrhs = X.cols();
891 // Forward solve with U
892 for (Index k = 0; k <= m_mapL.nsuper(); k++) {
893 Index fsupc = m_mapL.supToCol()[k];
894 Index lda = m_mapL.colIndexPtr()[fsupc + 1] - m_mapL.colIndexPtr()[fsupc]; // leading dimension
895 Index nsupc = m_mapL.supToCol()[k + 1] - fsupc;
896 Index luptr = m_mapL.colIndexPtr()[fsupc];
897
898 for (Index j = 0; j < nrhs; ++j) {
899 for (Index jcol = fsupc; jcol < fsupc + nsupc; jcol++) {
900 typename MatrixUType::InnerIterator it(m_mapU, jcol);
901 for (; it; ++it) {
902 Index irow = it.index();
903 X(jcol, j) -= X(irow, j) * (Conjugate ? numext::conj(it.value()) : it.value());
904 }
905 }
906 }
907 if (nsupc == 1) {
908 for (Index j = 0; j < nrhs; j++) {
909 X(fsupc, j) /= (Conjugate ? numext::conj(m_mapL.valuePtr()[luptr]) : m_mapL.valuePtr()[luptr]);
910 }
911 } else {
912 Map<const Matrix<Scalar, Dynamic, Dynamic, ColMajor>, 0, OuterStride<>> A(&(m_mapL.valuePtr()[luptr]), nsupc,
913 nsupc, OuterStride<>(lda));
914 typename Dest::RowsBlockXpr U = X.derived().middleRows(fsupc, nsupc);
915 EIGEN_IF_CONSTEXPR (Conjugate)
916 U = A.adjoint().template triangularView<Lower>().solve(U);
917 else
918 U = A.transpose().template triangularView<Lower>().solve(U);
919 }
920 } // End For U-solve
921 }
922
923 SparseMatrix<Scalar, RowMajor, Index> toSparse() {
924 ArrayXi rowCount = ArrayXi::Zero(rows());
925 for (Index i = 0; i < cols(); i++) {
926 typename MatrixLType::InnerIterator iter(m_mapL, i);
927 for (; iter; ++iter) {
928 if (iter.row() <= iter.col()) {
929 rowCount(iter.row())++;
930 }
931 }
932 }
933
934 SparseMatrix<Scalar, RowMajor, Index> sU(rows(), cols());
935 sU.reserve(rowCount);
936 for (Index i = 0; i < cols(); i++) {
937 typename MatrixLType::InnerIterator iter(m_mapL, i);
938 for (; iter; ++iter) {
939 if (iter.row() <= iter.col()) {
940 sU.insert(iter.row(), iter.col()) = iter.value();
941 }
942 }
943 }
944 sU.makeCompressed();
945 const SparseMatrix<Scalar, RowMajor, Index> u = m_mapU; // convert to RowMajor
946 sU += u;
947 return sU;
948 }
949
950 const MatrixLType& m_mapL;
951 const MatrixUType& m_mapU;
952};
953
954} // End namespace Eigen
955
956#endif
constexpr ColXpr col(Index i)
Definition DenseBase.h:1082
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
InverseReturnType inverse() const
Definition PermutationMatrix.h:229
Permutation matrix.
Definition PermutationMatrix.h:346
constexpr const IndicesType & indices() const
Definition PermutationMatrix.h:400
Derived & setConstant(Index size, const Scalar &val)
Definition CwiseNullaryOp.h:349
Derived & setZero(Index size)
Definition CwiseNullaryOp.h:536
constexpr void resize(Index rows, Index cols)
Definition PlainObjectBase.h:282
Pseudo expression representing a solving operation.
Definition Solve.h:63
Sparse supernodal LU factorization for general matrices.
Definition SparseLU.h:152
SparseLUMatrixUReturnType< SCMatrix, Map< SparseMatrix< Scalar, ColMajor, StorageIndex > > > matrixU() const
Give the MatrixU.
Definition SparseLU.h:285
void setPivotThreshold(const RealScalar &thresh)
Definition SparseLU.h:302
Index cols() const
Give the number of columns.
Definition SparseLU.h:263
Scalar logAbsDeterminant() const
Give the natural log of the absolute determinant.
Definition SparseLU.h:387
Index rows() const
Give the number of rows.
Definition SparseLU.h:260
Index nnzU() const
Give the number of non zero in matrix U.
Definition SparseLU.h:446
const SparseLUTransposeView< true, SparseLU< MatrixType_, OrderingType_ > > adjoint()
Return a solver for the adjointed matrix.
Definition SparseLU.h:251
Solve< SparseLU, Rhs > solve(const MatrixBase< Rhs > &B) const
Solve a system .
void factorize(const MatrixType &matrix)
Factorize the matrix to get the solver ready.
Definition SparseLU.h:602
Scalar determinant() const
Give the determinant.
Definition SparseLU.h:435
Scalar signDeterminant() const
Give the sign of the determinant.
Definition SparseLU.h:410
std::string lastErrorMessage() const
Give a human readable error.
Definition SparseLU.h:336
SparseLUMatrixLReturnType< SCMatrix > matrixL() const
Give the matrixL.
Definition SparseLU.h:276
void compute(const MatrixType &matrix)
Analyze and factorize the matrix so the solver is ready to solve.
Definition SparseLU.h:211
ComputationInfo info() const
Reports whether previous computation was successful.
Definition SparseLU.h:327
const PermutationType & colsPermutation() const
Give the column matrix permutation.
Definition SparseLU.h:300
SparseLU()
Basic constructor of the solver.
Definition SparseLU.h:179
void analyzePattern(const MatrixType &matrix)
Compute the column permutation.
Definition SparseLU.h:517
Index nnzL() const
Give the number of non zero in matrix L.
Definition SparseLU.h:443
const PermutationType & rowsPermutation() const
Give the row matrix permutation.
Definition SparseLU.h:294
void isSymmetric(bool sym)
Let you set that the pattern of the input matrix is symmetric.
Definition SparseLU.h:266
Scalar absDeterminant() const
Give the absolute value of the determinant.
Definition SparseLU.h:372
SparseLU(const MatrixType &matrix)
Constructor of the solver already based on a specific matrix.
Definition SparseLU.h:187
const SparseLUTransposeView< false, SparseLU< MatrixType_, OrderingType_ > > transpose()
Return a solver for the transposed matrix.
Definition SparseLU.h:230
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
A base class for sparse solvers.
Definition SparseSolverBase.h:68
Expression of a fixed-size or dynamic-size sub-vector.
Definition VectorBlock.h:59
a class to manipulate the L supernodal factor from the SparseLU factorization
Definition SparseLU_SupernodalMatrix.h:33
Definition SparseLUImpl.h:24
void relax_snode(const Index n, IndexVector &et, const Index relax_columns, IndexVector &descendants, IndexVector &relax_end)
Identify the initial relaxed supernodes.
Definition SparseLU_relax_snode.h:51
Index column_dfs(const Index m, const Index jcol, IndexVector &perm_r, Index maxsuper, Index &nseg, BlockIndexVector lsub_col, IndexVector &segrep, BlockIndexVector repfnz, IndexVector &xprune, IndexVector &marker, IndexVector &parent, IndexVector &xplore, GlobalLU_t &glu)
Performs a symbolic factorization on column jcol and decide the supernode boundary.
Definition SparseLU_column_dfs.h:91
void fixupL(const Index n, const IndexVector &perm_r, GlobalLU_t &glu)
Fix up the data storage lsub for L-subscripts.
Definition SparseLU_Utils.h:52
Index copy_to_ucol(const Index jcol, const Index nseg, IndexVector &segrep, BlockIndexVector repfnz, IndexVector &perm_r, BlockScalarVector dense, GlobalLU_t &glu)
Performs numeric block updates (sup-col) in topological order.
Definition SparseLU_copy_to_ucol.h:54
void heap_relax_snode(const Index n, IndexVector &et, const Index relax_columns, IndexVector &descendants, IndexVector &relax_end)
Identify the initial relaxed supernodes.
Definition SparseLU_heap_relax_snode.h:50
void panel_dfs(const Index m, const Index w, const Index jcol, MatrixType &A, IndexVector &perm_r, Index &nseg, ScalarVector &dense, IndexVector &panel_lsub, IndexVector &segrep, IndexVector &repfnz, IndexVector &xprune, IndexVector &marker, IndexVector &parent, IndexVector &xplore, GlobalLU_t &glu)
Performs a symbolic factorization on a panel of columns [jcol, jcol+w)
Definition SparseLU_panel_dfs.h:195
void countnz(const Index n, Index &nnzL, Index &nnzU, GlobalLU_t &glu)
Count Nonzero elements in the factors.
Definition SparseLU_Utils.h:24
Index column_bmod(const Index jcol, const Index nseg, BlockScalarVector dense, ScalarVector &tempv, BlockIndexVector segrep, BlockIndexVector repfnz, Index fpanelc, GlobalLU_t &glu)
Performs numeric block updates (sup-col) in topological order.
Definition SparseLU_column_bmod.h:57
Index pivotL(const Index jcol, const RealScalar &diagpivotthresh, IndexVector &perm_r, IndexVector &iperm_c, Index &pivrow, GlobalLU_t &glu)
Performs the numerical pivoting on the current column of L, and the CDIV operation.
Definition SparseLU_pivotL.h:64
Index memInit(Index m, Index n, Index annz, Index lwork, Index fillratio, Index panel_size, GlobalLU_t &glu)
Allocate various working space for the numerical factorization phase.
Definition SparseLU_Memory.h:135
void pruneL(const Index jcol, const IndexVector &perm_r, const Index pivrow, const Index nseg, const IndexVector &segrep, BlockIndexVector repfnz, IndexVector &xprune, GlobalLU_t &glu)
Prunes the L-structure.
Definition SparseLU_pruneL.h:57
void panel_bmod(const Index m, const Index w, const Index jcol, const Index nseg, ScalarVector &dense, ScalarVector &tempv, IndexVector &segrep, IndexVector &repfnz, GlobalLU_t &glu)
Performs numeric block updates (sup-panel) in topological order.
Definition SparseLU_panel_bmod.h:60
ComputationInfo
Definition Constants.h:455
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
constexpr unsigned int RowMajorBit
Definition Constants.h:71