| // This file is part of Eigen, a lightweight C++ template library | |
| // for linear algebra. | |
| // | |
| // This Source Code Form is subject to the terms of the Mozilla | |
| // Public License v. 2.0. If a copy of the MPL was not distributed | |
| // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. | |
| // SPDX-FileCopyrightText: The Eigen Authors | |
| // SPDX-License-Identifier: MPL-2.0 | |
| #ifndef EIGEN_MULTIFRONTAL_LDLT_H | |
| #define EIGEN_MULTIFRONTAL_LDLT_H | |
| // IWYU pragma: private | |
| #include "./InternalHeaderCheck.h" | |
| namespace Eigen { | |
| /** \ingroup SparseCholesky_Module | |
| * \class MultifrontalLDLT | |
| * \brief Sparse multifrontal LDL^* factorization of a symmetric or Hermitian indefinite matrix | |
| * | |
| * This class computes \f$ P A P^T = L D L^* \f$, where \f$ P \f$ is a permutation, \f$ L \f$ is unit lower triangular | |
| * and \f$ D \f$ is block diagonal with 1x1 and 2x2 blocks. This is the form of the dense BunchKaufman, with different | |
| * pivot tests. | |
| * | |
| * The matrix is factored as a tree of small dense frontal matrices. A front can only pivot on its fully summed | |
| * columns, so a pivot must also bound the entries in rows that aren't fully summed yet. With threshold \f$ u \f$, a 1x1 | |
| * pivot on column \f$ j \f$ is accepted if | |
| * \f[ |a_{jj}| \ge u \max_{i \ne j} |a_{ij}| \f] | |
| * and a 2x2 pivot \f$ D \f$ on columns \f$ j \f$ and \f$ r \f$ is accepted if | |
| * \f[ |D^{-1}| \left( \max_{i \ne j,r} |a_{ij}|, \max_{i \ne j,r} |a_{ir}| \right)^T \le (1/u, 1/u)^T | |
| * \quad \text{and} \quad |\det D| \ge |a_{rj}|^2 / 2 . \f] | |
| * Columns with no acceptable pivot are delayed to the parent front, which adds them to its fully summed columns. The | |
| * root front has no other rows to bound, so \f$ u \le 1/2 \f$ guarantees it can pivot (Duff and Reid, 1983). | |
| * | |
| * analyzePattern() merges fronts into their parents if the merged front would hold few enough explicit zeros (Ashcraft | |
| * and Grimes, 1989). This costs some fill for larger, fewer fronts: they need less assembly, spend more time in dense | |
| * kernels, and have more fully summed columns to pivot on, so they delay fewer pivots. | |
| * | |
| * Delayed pivots add fill that the symbolic analysis doesn't predict, so the memory the factorization needs depends on | |
| * the matrix's values. This class doesn't scale the matrix. The pivot tests compare entries with each other, so a | |
| * single large row can delay columns all the way up the tree. Equilibrate such a matrix first (e.g., with Ruiz | |
| * scaling). | |
| * | |
| * The matrix is read as Hermitian, so only the real part of each diagonal entry is read, even if its imaginary part is | |
| * not finite. | |
| * | |
| * The elimination tree and the assembly maps come from analyzePattern() and are reused by each factorize(). The | |
| * workspace keeps its capacity, so its storage only grows if a factorization needs more memory than any before it. | |
| * Dense products on large fronts can allocate temporaries above \c EIGEN_STACK_ALLOCATION_LIMIT. | |
| * | |
| * Each front is factored in panels: a pivot updates the columns of its panel, and the rest of the front is updated | |
| * once per panel by a level-3 product. Solving likewise applies each front's factor to all right-hand sides at once. | |
| * | |
| * References: | |
| * - I. S. Duff and J. K. Reid, "The multifrontal solution of indefinite sparse symmetric linear equations", ACM TOMS | |
| * 9 (1983), pp. 302-325. | |
| * - J. R. Bunch and L. Kaufman, "Some stable methods for calculating inertia and solving symmetric linear systems", | |
| * Math. Comp. 31 (1977), pp. 163-179. | |
| * - J. W. H. Liu, "The role of elimination trees in sparse factorization", SIAM J. Matrix Anal. Appl. 11 (1990), | |
| * pp. 134-172. | |
| * - C. Ashcraft and R. Grimes, "The influence of relaxed supernode partitions on the multifrontal method", ACM TOMS | |
| * 15 (1989), pp. 291-309. | |
| * - J. R. Gilbert, E. G. Ng and B. W. Peyton, "An efficient algorithm to compute row and column counts for sparse | |
| * Cholesky factorization", SIAM J. Matrix Anal. Appl. 15 (1994), pp. 1075-1091. | |
| * | |
| * \tparam MatrixType_ the type of the sparse matrix A, it must be a SparseMatrix<> | |
| * \tparam UpLo_ the triangular part that will be used for the factorization: Lower (default) or Upper. The other | |
| * triangular part won't be read. | |
| * \tparam Ordering_ The fill-reducing ordering method. See the \link OrderingMethods_Module OrderingMethods \endlink | |
| * module for the list of built-in and external ordering methods. | |
| * | |
| * \implsparsesolverconcept | |
| * | |
| * \sa class SimplicialLDLT, class BunchKaufman, class AMDOrdering, class NaturalOrdering | |
| */ | |
| template <typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>> | |
| class MultifrontalLDLT : public SparseSolverBase<MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>> { | |
| using Base = SparseSolverBase<MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>>; | |
| using Base::m_isInitialized; | |
| public: | |
| using Base::_solve_impl; | |
| using MatrixType = MatrixType_; | |
| using OrderingType = Ordering_; | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename NumTraits<Scalar>::Real; | |
| using StorageIndex = typename MatrixType::StorageIndex; | |
| using VectorType = Matrix<Scalar, Dynamic, 1>; | |
| using RealVectorType = Matrix<RealScalar, Dynamic, 1>; | |
| using PermutationType = PermutationMatrix<Dynamic, Dynamic, StorageIndex>; | |
| using FactorType = SparseMatrix<Scalar, ColMajor, StorageIndex>; | |
| EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar) | |
| EIGEN_STATIC_ASSERT(UpLo_ == Lower || UpLo_ == Upper, MULTIFRONTALLDLT_ACCEPTS_UPPER_AND_LOWER_MODE_ONLY) | |
| static constexpr int UpLo = UpLo_; | |
| static constexpr int ColsAtCompileTime = Dynamic; | |
| static constexpr int MaxColsAtCompileTime = Dynamic; | |
| /** Default constructor */ | |
| MultifrontalLDLT() = default; | |
| /** Constructs the factorization of \a matrix. */ | |
| explicit MultifrontalLDLT(const MatrixType& matrix) { compute(matrix); } | |
| /** Sets the threshold \f$ u \f$ for accepting a pivot. It must be in (0, 1/2]. The default is 0.01. | |
| * | |
| * Smaller values delay fewer pivots, so they add less fill, but they allow larger entries in L. | |
| * | |
| * \returns a reference to \c *this. | |
| */ | |
| MultifrontalLDLT& setPivotThreshold(const RealScalar& threshold) { | |
| eigen_assert(threshold > RealScalar(0) && threshold <= RealScalar(0.5)); | |
| m_threshold = threshold; | |
| return *this; | |
| } | |
| /** \returns the pivot threshold. \sa setPivotThreshold() */ | |
| const RealScalar& pivotThreshold() const { return m_threshold; } | |
| /** Computes the symbolic analysis and the factorization of \a matrix. | |
| * | |
| * \returns a reference to \c *this. | |
| */ | |
| MultifrontalLDLT& compute(const MatrixType& matrix) { | |
| analyzePattern(matrix); | |
| factorize(matrix); | |
| return *this; | |
| } | |
| /** Performs the symbolic analysis of the sparsity pattern of \a matrix. | |
| * | |
| * \sa factorize(), compute() | |
| */ | |
| void analyzePattern(const MatrixType& matrix); | |
| /** Performs the numeric factorization of \a matrix, which must have the sparsity pattern given to analyzePattern(). | |
| * | |
| * \sa analyzePattern(), compute() | |
| */ | |
| void factorize(const MatrixType& matrix); | |
| /** \brief Reports whether the previous factorization was successful. | |
| * | |
| * \returns \c Success if every pivot was finite and nonzero, \c NumericalIssue if a pivot is zero (the matrix is | |
| * singular to working precision) or not finite (from a non-finite entry, a complex entry whose magnitude | |
| * overflows, or an update overflowing on finite input), and \c InvalidInput if no factorization was | |
| * computed. The imaginary part of a diagonal entry isn't read, so it doesn't affect the result. A zero | |
| * pivot gets a zero solution, so solve() still returns the solution of the remaining blocks if every pivot | |
| * is finite. If a pivot isn't finite, the result of solve() isn't meaningful. | |
| */ | |
| ComputationInfo info() const { | |
| eigen_assert(m_isInitialized && "Decomposition is not initialized."); | |
| return m_info; | |
| } | |
| Index rows() const { return m_P.rows(); } | |
| Index cols() const { return m_P.cols(); } | |
| /** \returns the diagonal of D, in pivot order. */ | |
| const RealVectorType& vectorD() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading D."); | |
| return m_D; | |
| } | |
| /** \returns the subdiagonal of D, in pivot order. Entry \c k is nonzero if and only if pivots \c k and \c k+1 form a | |
| * 2x2 block. */ | |
| const VectorType& subDiagonal() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading D."); | |
| return m_subdiagonal; | |
| } | |
| /** \returns the unit lower triangular factor \f$ L \f$ of the previous factorization, in pivot order, with its unit | |
| * diagonal stored. It is assembled from the fronts on each call, in O(nonZeros() + rows()) time and memory, and it | |
| * keeps the explicit zeros that nonZeros() counts. \f$ L_{k+1,k} = 0 \f$ where pivots \c k and \c k+1 form a | |
| * 2x2 block of D. | |
| * | |
| * \sa matrixU(), vectorD(), subDiagonal(), permutationP() | |
| */ | |
| FactorType matrixL() const; | |
| /** \returns the unit upper triangular factor \f$ U = L^* \f$ of the previous factorization. Like matrixL(), it is | |
| * assembled on each call. | |
| * | |
| * \sa matrixL() | |
| */ | |
| FactorType matrixU() const { return matrixL().adjoint(); } | |
| /** \returns the permutation \f$ P \f$ of the previous factorization. It combines the fill-reducing ordering, the | |
| * reordering of the elimination tree, and the delayed pivots, so unlike in SimplicialLDLT, it depends on the matrix's | |
| * values and can change with each factorize(). | |
| * | |
| * \sa permutationPinv() | |
| */ | |
| const PermutationType& permutationP() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the permutation."); | |
| return m_P; | |
| } | |
| /** \returns the inverse of the permutation \f$ P \f$. Entry \c k of its \c indices() is the row of pivot \c k in the | |
| * matrix given to factorize(). | |
| * | |
| * \sa permutationP() | |
| */ | |
| const PermutationType& permutationPinv() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the permutation."); | |
| return m_Pinv; | |
| } | |
| /** \returns the determinant of the matrix, \f$ \exp(\log|\det A|) \f$ times signDeterminant(). It is not finite if | |
| * any pivot is not finite, and otherwise zero if any pivot is zero. It has O(n) complexity, since the factorization | |
| * has already been computed. | |
| * | |
| * \warning A determinant can overflow or underflow even if the factorization is accurate. logAbsDeterminant() and | |
| * signDeterminant() don't. | |
| * | |
| * \sa absDeterminant(), logAbsDeterminant(), signDeterminant() | |
| */ | |
| Scalar determinant() const { return Scalar(absDeterminant()) * signDeterminant(); } | |
| /** \returns the absolute value of the determinant of the matrix. | |
| * | |
| * \warning Like determinant(), this can overflow or underflow. | |
| * | |
| * \sa determinant(), logAbsDeterminant() | |
| */ | |
| RealScalar absDeterminant() const { return numext::exp(logAbsDeterminant()); } | |
| /** \returns the natural log of the absolute value of the determinant of the matrix, | |
| * \f[ \log|\det A| = \sum_{1 \times 1} \log|d_k| + \sum_{2 \times 2} \left( 2 \log s_k + \log|\delta_k| \right), \f] | |
| * where a 2x2 block of D is \f$ s_k \f$ times a block with largest magnitude 1 and determinant \f$ \delta_k \f$. It | |
| * is \f$ -\infty \f$ if a pivot is zero, and not finite if a pivot is not finite. | |
| * | |
| * \sa determinant(), signDeterminant() | |
| */ | |
| RealScalar logAbsDeterminant() const; | |
| /** \returns the sign of the determinant of the matrix: \c 1, \c -1, or \c 0 if a pivot is zero or not finite. It is | |
| * \f$ (-1)^{n_-} \f$ for the inertia numNegative() = \f$ n_- \f$, so it doesn't overflow. | |
| * | |
| * \sa determinant(), logAbsDeterminant(), numNegative() | |
| */ | |
| Scalar signDeterminant() const { | |
| if (numZero() > 0 || numPositive() + numNegative() < rows()) return Scalar(0); | |
| return Scalar(numNegative() % 2 == 0 ? 1 : -1); | |
| } | |
| /** \returns the number of positive eigenvalues, read off the pivots of D by Sylvester's law of inertia. | |
| * | |
| * The signs come from the computed pivots, so this is the inertia of a matrix close to A rather than necessarily of | |
| * A. A non-finite pivot block is left out of all three counts, so they add up to rows() only if every pivot is | |
| * finite; info() reports \c NumericalIssue otherwise. | |
| * | |
| * \sa numNegative(), numZero() | |
| */ | |
| Index numPositive() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia."); | |
| return m_numPositive; | |
| } | |
| /** \returns the number of negative eigenvalues. \sa numPositive() */ | |
| Index numNegative() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia."); | |
| return m_numNegative; | |
| } | |
| /** \returns the number of pivots that are exactly zero. | |
| * | |
| * \warning A nonzero count means that A is singular to working precision, not that it is exactly singular: | |
| * rounding can turn a tiny pivot into an exact zero, and equally leave a tiny pivot in place of one. | |
| * | |
| * \sa numPositive() | |
| */ | |
| Index numZero() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia."); | |
| return m_numZero; | |
| } | |
| /** \returns true if the matrix is positive semidefinite: every pivot is finite and no eigenvalue is negative. */ | |
| bool isPositive() const { return numNegative() == 0 && numPositive() + numZero() == rows(); } | |
| /** \returns true if the matrix is negative semidefinite: every pivot is finite and no eigenvalue is positive. */ | |
| bool isNegative() const { return numPositive() == 0 && numNegative() + numZero() == rows(); } | |
| /** \returns the number of entries of L stored below its unit diagonal in the previous factorization. This includes | |
| * the explicit zeros of merged fronts, so it can exceed the fill of an unmerged factorization such as SimplicialLDLT. | |
| */ | |
| Index nonZeros() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the size of L."); | |
| return m_LNonZeros; | |
| } | |
| #ifndef EIGEN_PARSED_BY_DOXYGEN | |
| /** \internal */ | |
| template <typename Rhs, typename Dest> | |
| void _solve_impl(const MatrixBase<Rhs>& rhs, MatrixBase<Dest>& dest) const; | |
| #endif // EIGEN_PARSED_BY_DOXYGEN | |
| private: | |
| using FrontMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>; | |
| using FrontMap = Map<FrontMatrix>; | |
| using ConstFrontMap = Map<const FrontMatrix>; | |
| using VectorMap = Map<VectorType>; | |
| using ConstVectorMap = Map<const VectorType>; | |
| using IndexVectorType = Matrix<StorageIndex, Dynamic, 1>; | |
| // Columns of a front that a pivot updates directly. Wider panels do more of the work in level-2 updates, narrower | |
| // ones pay for more calls to the level-3 product. | |
| static constexpr Index kPanelWidth = 32; | |
| // Below this order a front is its own panel: there's too little work to repay a level-3 product. | |
| static constexpr Index kBlockedFrontMinOrder = 32; | |
| // Below this length, a plain loop beats the alignment peeling of a vectorized expression. Sparse KKT matrices are | |
| // dominated by fronts of a few columns, where this decides the factorization's speed. | |
| static constexpr Index kVectorizedMinLength = 16; | |
| // Up to this order, the loops over a front have compile-time bounds, so they unroll. | |
| static constexpr Index kSmallFrontMaxOrder = 8; | |
| // Below this mean length of the runs of a child's map into its parent, extend-add stays a scatter: walking short runs | |
| // costs more than the additions they'd vectorize. | |
| static constexpr Index kExtendAddMinRunLength = 4; | |
| // Below this size of L (order * pivots), solve() applies a front's factor in place rather than through dense products | |
| // on a gathered copy of its rows. | |
| static constexpr Index kDenseSolveMinSize = 4096; | |
| // An array whose storage survives popping and clearing, so refactoring doesn't reallocate or reinitialize it. | |
| // | |
| // This, m_front, and m_pivotScratch are aligned so that the factorization is bitwise reproducible. Vectorized kernels | |
| // switch between scalar and packet code at alignment boundaries, and the two can round differently. | |
| template <typename T> | |
| struct WorkStack { | |
| std::vector<T, aligned_allocator<T>> storage; | |
| std::size_t size = 0; | |
| // Returns where to write count new elements. This can invalidate earlier pointers into the array. | |
| T* push(std::size_t count) { | |
| if (storage.size() < size + count) storage.resize(numext::maxi(size + count, 2 * storage.size())); | |
| T* end = storage.data() + size; | |
| size += count; | |
| return end; | |
| } | |
| // Returns the last count elements. | |
| T* top(std::size_t count) { return storage.data() + (size - count); } | |
| void pop(std::size_t count) { size -= count; } | |
| void reserve(std::size_t count) { | |
| if (storage.size() < count) storage.resize(count); | |
| } | |
| void clear() { size = 0; } | |
| }; | |
| // An entry of the input matrix and where it's assembled in its front. value is the entry's index in the values of the | |
| // compressed matrix. row and col don't count delayed columns. | |
| struct Assembly { | |
| StorageIndex value; | |
| StorageIndex row; | |
| StorageIndex col; | |
| // Whether the permutation moved the entry to the other triangle. | |
| bool conjugate; | |
| }; | |
| // Where a front's factor is stored after factorize(). | |
| struct FactoredFront { | |
| StorageIndex numPivots; | |
| StorageIndex order; | |
| // Start of the front's rows in m_factorRows. | |
| std::size_t rows; | |
| // Start of the front's order x numPivots columns of L in m_L. Only the part below the diagonal is meaningful. | |
| std::size_t values; | |
| }; | |
| // The sizes are computed in std::size_t because Index can be narrower than the product. | |
| static std::size_t rectangleSize(Index rows, Index cols) { | |
| return static_cast<std::size_t>(rows) * static_cast<std::size_t>(cols); | |
| } | |
| // Entries in the lower triangle of an n x n matrix, including its diagonal. | |
| static std::size_t packedSize(Index n) { return static_cast<std::size_t>(n) * (static_cast<std::size_t>(n) + 1) / 2; } | |
| // Entries strictly below the diagonal in the first numPivots columns of an order x order matrix. | |
| static std::size_t factorSize(Index numPivots, Index order) { | |
| return rectangleSize(numPivots, order) - packedSize(numPivots); | |
| } | |
| // dst -= alpha * src, where the arrays don't overlap. | |
| static void subtractScaled(Scalar* EIGEN_RESTRICT dst, const Scalar* EIGEN_RESTRICT src, const Scalar& alpha, | |
| Index length) { | |
| if (length < kVectorizedMinLength) { | |
| for (Index i = 0; i < length; ++i) dst[i] -= src[i] * alpha; | |
| } else { | |
| VectorMap(dst, length).noalias() -= ConstVectorMap(src, length) * alpha; | |
| } | |
| } | |
| // dst -= alpha1 * src1 + alpha2 * src2, where dst doesn't overlap the others. | |
| static void subtractScaled(Scalar* EIGEN_RESTRICT dst, const Scalar* EIGEN_RESTRICT src1, const Scalar& alpha1, | |
| const Scalar* EIGEN_RESTRICT src2, const Scalar& alpha2, Index length) { | |
| if (length < kVectorizedMinLength) { | |
| for (Index i = 0; i < length; ++i) dst[i] -= src1[i] * alpha1 + src2[i] * alpha2; | |
| } else { | |
| VectorMap(dst, length).noalias() -= ConstVectorMap(src1, length) * alpha1 + ConstVectorMap(src2, length) * alpha2; | |
| } | |
| } | |
| // dst += src, where the arrays don't overlap. | |
| static void addTo(Scalar* EIGEN_RESTRICT dst, const Scalar* EIGEN_RESTRICT src, Index length) { | |
| if (length < kVectorizedMinLength) { | |
| for (Index i = 0; i < length; ++i) dst[i] += src[i]; | |
| } else { | |
| VectorMap(dst, length).noalias() += ConstVectorMap(src, length); | |
| } | |
| } | |
| // Returns the largest magnitude of a column segment, or zero if it's empty. | |
| static RealScalar largestMagnitude(const Scalar* column, Index length) { | |
| if (length >= kVectorizedMinLength) return ConstVectorMap(column, length).cwiseAbs().maxCoeff(); | |
| RealScalar result(0); | |
| for (Index i = 0; i < length; ++i) result = numext::maxi(result, RealScalar(numext::abs(column[i]))); | |
| return result; | |
| } | |
| // The rows of the order x order front being factored. | |
| StorageIndex* frontRows(Index order) { return m_factorRows.top(static_cast<std::size_t>(order)); } | |
| // The 2x2 block [d1 conj(d21); d21 d2] = scale [a conj(b); b c], where scale is its largest magnitude. det = a c - | |
| // |b|^2 is in [-2, 1]. | |
| struct ScaledBlock { | |
| RealScalar scale; | |
| RealScalar a; | |
| RealScalar c; | |
| RealScalar absB; | |
| RealScalar det; | |
| ScaledBlock(const RealScalar& d1, const RealScalar& d2, const RealScalar& absD21) | |
| : scale(numext::maxi(numext::maxi(RealScalar(numext::abs(d1)), RealScalar(numext::abs(d2))), absD21)), | |
| a(d1 / scale), | |
| c(d2 / scale), | |
| absB(absD21 / scale), | |
| det(a * c - absB * absB) {} | |
| }; | |
| // Calls function(row, col, position) on the structural entries of the UpLo_ triangle in storage order, where position | |
| // counts all of the matrix's entries before this one in storage order. That's the entry's index in the values of the | |
| // matrix once it's compressed. | |
| template <typename Function> | |
| static void visitTriangle(const MatrixType& matrix, Function&& function) { | |
| Index position = 0; | |
| const Index outerSize = matrix.outerSize(); | |
| for (Index outer = 0; outer < outerSize; ++outer) { | |
| for (typename MatrixType::InnerIterator it(matrix, outer); it; ++it, ++position) { | |
| const Index row = it.row(); | |
| const Index col = it.col(); | |
| if (UpLo_ == Lower ? row >= col : row <= col) function(row, col, position); | |
| } | |
| } | |
| } | |
| // Largest fraction of explicit zeros allowed in a merged front's L, including its diagonal. An explicit zero costs | |
| // more in a larger front, while a smaller one gains more from losing an extend-add and from gaining fully summed | |
| // columns. | |
| static double maxExplicitZeroFraction(Index pivots) { return pivots < 4 ? 0.3 : (pivots < 32 ? 0.1 : 0.02); } | |
| // Merges fronts into their parents if the result has few enough explicit zeros, then renumbers the columns so that | |
| // each merged front's are contiguous. frontParent and frontBelow hold each front's parent, or -1 for a root, and its | |
| // number of rows below its pivots. Updates columnFront, m_frontColumns, m_perm and m_invPerm, and sets newColumn to | |
| // each column's new index. | |
| void mergeRelaxedFronts(const std::vector<StorageIndex>& frontParent, const std::vector<StorageIndex>& frontBelow, | |
| std::vector<StorageIndex>& columnFront, std::vector<StorageIndex>& newColumn); | |
| // Records a factored front and returns where to write its order x numPivots columns of L. | |
| Scalar* appendFactor(Index s, Index numPivots, Index order); | |
| // Returns the largest off-diagonal magnitude of column j in the front's active part, which starts at row active, | |
| // leaving out row skip (or -1 for none). | |
| // | |
| // This, largestFullySummed() and largestMagnitude() skip NaN entries, so a pivot can pass its test against a column | |
| // holding a NaN. The update carries the NaN to the diagonal of a later pivot, and factorize() reports a non-finite | |
| // pivot as NumericalIssue. | |
| RealScalar frontColumnMax(Index order, Index active, Index j, Index skip) const; | |
| // Returns whether column j is exactly zero off its diagonal in the front's active part, which starts at row active. A | |
| // NaN entry counts as nonzero. | |
| bool frontColumnIsZero(Index order, Index active, Index j) const; | |
| // Returns the row r in [active, fullySummed) other than j with the largest magnitude in column j, or -1 if they're | |
| // all zero, and sets rest to frontColumnMax(order, active, j, r). | |
| Index largestFullySummed(Index order, Index active, Index fullySummed, Index j, RealScalar& rest) const; | |
| // These add a child's packed lower triangle to the order x order front, where map gives each of its childOrder rows' | |
| // row in the front. extendAdd() adds the rows that stay adjacent in the front as vectorized segments, if there are | |
| // enough of them. A call is too expensive for the short children of a tree of small fronts, so they scatter inline. | |
| EIGEN_ALWAYS_INLINE void scatterAdd(Index order, const Scalar* block, const StorageIndex* map, Index childOrder) { | |
| FrontMap front(m_front.data(), order, order); | |
| for (Index j = 0; j < childOrder; ++j) { | |
| Scalar* column = &front.coeffRef(0, map[j]); | |
| for (Index i = j; i < childOrder; ++i) column[map[i]] += *block++; | |
| } | |
| } | |
| void extendAdd(Index order, const Scalar* block, const StorageIndex* map, Index childOrder); | |
| // Eliminates pivots from the fully summed columns of m_front and returns how many. Pivots end up at the front's start | |
| // and delayed columns between them and the rows that aren't fully summed, with the front's rows permuted to match. | |
| Index factorFront(Index order, Index fullySummed, bool isRoot); | |
| // Factors a front with one fully summed column in a single pass, without updating the front in place and then copying | |
| // its results, or delays the column if it fails the 1x1 test. Returns false, leaving the front unchanged, if the | |
| // pivot is zero. | |
| EIGEN_ALWAYS_INLINE bool factorOnePivotFront(Index s, Index order, bool isRoot); | |
| // Records the factored front's fullySummed - numPivots delayed columns and pushes the packed lower triangle of its | |
| // trailing order - numPivots rows and columns onto m_stack, for its parent's extend-add to pop. The parent reads the | |
| // delayed rows from m_factorRows, after the front's pivots. | |
| void pushToParent(Index s, Index order, Index fullySummed, Index numPivots); | |
| // Swaps two rows and columns of the front. | |
| void swapFront(Index order, Index a, Index b); | |
| // These eliminate the pivot at column k from the columns before panelEnd. updateTrailing() applies it to the others. | |
| void eliminate1x1(Index order, Index k, Index panelEnd); | |
| void eliminate2x2(Index order, Index k, Index panelEnd); | |
| // Applies the last numPivots pivots to the columns from panelEnd on. | |
| void updateTrailing(Index order, Index firstPivot, Index numPivots, Index panelEnd); | |
| // The pivot tests bound |L| by 1/u, so a smaller u trades backward error for fill. | |
| RealScalar m_threshold = RealScalar(0.01); | |
| ComputationInfo m_info = InvalidInput; | |
| // Symbolic analysis | |
| // Each input row's row in elimination order, and its inverse. | |
| std::vector<StorageIndex> m_perm; | |
| std::vector<StorageIndex> m_invPerm; | |
| // First column of each front, with one extra element at the end. | |
| std::vector<StorageIndex> m_frontColumns; | |
| // Each front's parent, or -1 for a root. | |
| std::vector<StorageIndex> m_frontParent; | |
| // The number of rows below each front's pivots, as m_belowStart[s + 1] - m_belowStart[s]. | |
| std::vector<std::size_t> m_belowStart; | |
| // Each front's columns followed by the rows below its pivots, starting at m_belowStart[s] + m_frontColumns[s]. | |
| std::vector<StorageIndex> m_frontRowList; | |
| // Position in the parent front of each row below a front's pivots, from m_belowStart[s], not counting the parent's | |
| // delayed columns. | |
| std::vector<StorageIndex> m_belowToParent; | |
| // Each front's children, in increasing order. | |
| std::vector<std::size_t> m_childStart; | |
| std::vector<StorageIndex> m_children; | |
| // Where each input matrix entry is assembled. | |
| std::vector<std::size_t> m_assemblyStart; | |
| std::vector<Assembly> m_assembly; | |
| // Number of entries the input matrix stores, in both triangles. | |
| std::size_t m_numValues = 0; | |
| // What a factorization without delayed pivots stores in m_L, and its largest m_stack and front order. | |
| std::size_t m_symbolicFactorSize = 0; | |
| std::size_t m_symbolicStackSize = 0; | |
| Index m_symbolicFrontOrder = 0; | |
| // Numeric factorization | |
| // The input matrix's values in compressed order, if it isn't compressed. | |
| std::vector<Scalar> m_values; | |
| // The front being factored. | |
| std::vector<Scalar, aligned_allocator<Scalar>> m_front; | |
| // Rows of L in a 2x2 pivot. | |
| std::vector<Scalar, aligned_allocator<Scalar>> m_pivotScratch; | |
| // Maps a child's rows into its parent. | |
| std::vector<StorageIndex> m_childMap; | |
| // For each row of a child, the end of its run of rows that stay adjacent in the parent. | |
| std::vector<StorageIndex> m_childRunEnd; | |
| // Stack of contribution blocks. Each is a packed lower triangle. | |
| WorkStack<Scalar> m_stack; | |
| // Number of columns each front delayed to its parent. | |
| std::vector<StorageIndex> m_numDelayed; | |
| // Each front's pivot columns. | |
| WorkStack<Scalar> m_L; | |
| // Each front's rows after pivoting, in elimination order. The current front's are the last ones, permuted in place, | |
| // so a tree of small fronts doesn't copy them from a scratch array. | |
| WorkStack<StorageIndex> m_factorRows; | |
| std::vector<FactoredFront> m_factoredFronts; | |
| // D's 2x2 blocks, in pivot order. | |
| std::vector<ScaledBlock> m_blocks; | |
| RealVectorType m_D; | |
| VectorType m_subdiagonal; | |
| PermutationType m_P; | |
| PermutationType m_Pinv; | |
| // Each pivot's row in elimination order. | |
| std::vector<StorageIndex> m_pivots; | |
| Index m_LNonZeros = 0; | |
| Index m_numPivots = 0; | |
| Index m_numPositive = 0; | |
| Index m_numNegative = 0; | |
| Index m_numZero = 0; | |
| Index m_maxFrontOrder = 0; | |
| bool m_hasZeroPivot = false; | |
| }; | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::UpLo; | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::ColsAtCompileTime; | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::MaxColsAtCompileTime; | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::mergeRelaxedFronts(const std::vector<StorageIndex>& frontParent, | |
| const std::vector<StorageIndex>& frontBelow, | |
| std::vector<StorageIndex>& columnFront, | |
| std::vector<StorageIndex>& newColumn) { | |
| const auto toStorageIndex = [](auto value) { return internal::convert_index<StorageIndex>(value); }; | |
| constexpr StorageIndex none(-1); | |
| const Index size = static_cast<Index>(columnFront.size()); | |
| const Index numFronts = static_cast<Index>(m_frontColumns.size()) - 1; | |
| newColumn.resize(size); | |
| std::iota(newColumn.begin(), newColumn.end(), StorageIndex(0)); | |
| const auto storedEntries = [](Index pivots, Index below) { | |
| return factorSize(pivots, pivots + below) + static_cast<std::size_t>(pivots); | |
| }; | |
| // below(child) is a subset of columns(parent) U below(parent) (Liu, 1990), so a merged front keeps its parent's rows | |
| // below. Each front's descendants are final when it's visited, because the fronts are postordered. | |
| std::vector<StorageIndex> mergedInto(numFronts, none); | |
| std::vector<StorageIndex> numPivots(numFronts); | |
| // Entries of L in a front, including its diagonal and leaving out explicit zeros. | |
| std::vector<std::size_t> numEntries(numFronts); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| numPivots[s] = m_frontColumns[s + 1] - m_frontColumns[s]; | |
| numEntries[s] = storedEntries(numPivots[s], frontBelow[s]); | |
| } | |
| Index numMerged = 0; | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const StorageIndex p = frontParent[s]; | |
| if (p == none) continue; | |
| const Index pivots = numPivots[s] + numPivots[p]; | |
| const std::size_t stored = storedEntries(pivots, frontBelow[p]); | |
| const std::size_t entries = numEntries[s] + numEntries[p]; | |
| if (double(stored - entries) <= maxExplicitZeroFraction(pivots) * double(stored)) { | |
| mergedInto[s] = p; | |
| numPivots[p] = toStorageIndex(pivots); | |
| numEntries[p] = entries; | |
| ++numMerged; | |
| } | |
| } | |
| if (numMerged == 0) return; | |
| // Each original front's merged front, in the order of the fronts that weren't merged into a parent. | |
| std::vector<StorageIndex> merged(numFronts); | |
| const StorageIndex numMergedFronts = toStorageIndex(numFronts - numMerged); | |
| { | |
| StorageIndex next = numMergedFronts; | |
| for (Index s = numFronts - 1; s >= 0; --s) { | |
| merged[s] = mergedInto[s] == none ? --next : merged[mergedInto[s]]; | |
| } | |
| } | |
| // A merged child generally isn't its parent's last child, so the merged tree needs a new postorder to make each | |
| // front's columns contiguous and keep contribution blocks on a stack. Any postorder of a tree has the same fill. | |
| // Visiting children in increasing order keeps the fronts that weren't merged in their relative order. | |
| IndexVectorType rootedParent(numMergedFronts); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| if (mergedInto[s] == none) { | |
| rootedParent[merged[s]] = frontParent[s] == none ? numMergedFronts : merged[frontParent[s]]; | |
| } | |
| } | |
| IndexVectorType postorder; | |
| internal::treePostorder(numMergedFronts, rootedParent, postorder); | |
| std::vector<StorageIndex> firstColumn(numMergedFronts + 1, 0); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| if (mergedInto[s] == none) firstColumn[postorder[merged[s]] + 1] = numPivots[s]; | |
| } | |
| for (Index s = 0; s < numMergedFronts; ++s) firstColumn[s + 1] += firstColumn[s]; | |
| // A front's columns keep their relative order, so every entry stays in the same triangle. | |
| std::vector<StorageIndex> newColumnFront(size); | |
| { | |
| std::vector<StorageIndex> next(firstColumn.begin(), firstColumn.end() - 1); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const StorageIndex front = postorder[merged[s]]; | |
| const Index end = m_frontColumns[s + 1]; | |
| for (Index j = m_frontColumns[s]; j < end; ++j) { | |
| newColumn[j] = next[front]++; | |
| newColumnFront[newColumn[j]] = front; | |
| } | |
| } | |
| } | |
| columnFront.swap(newColumnFront); | |
| m_frontColumns.swap(firstColumn); | |
| for (Index i = 0; i < size; ++i) { | |
| m_perm[i] = newColumn[m_perm[i]]; | |
| m_invPerm[m_perm[i]] = toStorageIndex(i); | |
| } | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::analyzePattern(const MatrixType& matrix) { | |
| eigen_assert(matrix.rows() == matrix.cols() && "The matrix must be square."); | |
| const Index size = matrix.rows(); | |
| // Fill-reducing ordering. An empty permutation means the identity. | |
| PermutationMatrix<Dynamic, Dynamic, StorageIndex> Pinv; | |
| EIGEN_IF_CONSTEXPR ((!std::is_same<OrderingType, NaturalOrdering<StorageIndex>>::value)) { | |
| SparseMatrix<Scalar, ColMajor, StorageIndex> C; | |
| constexpr bool kUseAMDFastPath = std::is_same<OrderingType, AMDOrdering<StorageIndex>>::value; | |
| internal::simplicial_cholesky_amd_dispatch<kUseAMDFastPath>::template run<UpLo_, false, OrderingType>(matrix, C, | |
| Pinv); | |
| } | |
| const auto toStorageIndex = [](auto value) { return internal::convert_index<StorageIndex>(value); }; | |
| std::vector<StorageIndex> ordered(size); | |
| for (Index i = 0; i < size; ++i) ordered[Pinv.size() > 0 ? Index(Pinv.indices()(i)) : i] = toStorageIndex(i); | |
| // The upper triangle of the ordered matrix. | |
| FactorType upper; | |
| internal::permute_symm_to_symm<UpLo_, Upper, false>(matrix, upper, Pinv.size() > 0 ? ordered.data() : nullptr); | |
| // Each column's parent in the elimination tree, or -1 for a root. | |
| constexpr StorageIndex none(-1); | |
| std::vector<StorageIndex> parent(size); | |
| { | |
| std::vector<StorageIndex> ancestors(size); | |
| internal::simpl_chol_helper<Scalar, StorageIndex>::calc_etree(toStorageIndex(size), upper, parent.data(), | |
| ancestors.data()); | |
| } | |
| // A postorder doesn't change the fill and lets factorize() keep contribution blocks on a stack. | |
| IndexVectorType rootedParent(size); | |
| for (Index j = 0; j < size; ++j) rootedParent[j] = parent[j] == none ? toStorageIndex(size) : parent[j]; | |
| // Visiting children from largest to smallest column index places each leaf of an AMD-ordered KKT chain's tree right | |
| // before its parent, not O(N) rows away, so a front's rows stay close together in the solution vectors once those | |
| // vectors outgrow the cache. | |
| IndexVectorType postorder; | |
| internal::treePostorder(toStorageIndex(size), rootedParent, postorder, internal::PostorderChildren::Decreasing); | |
| m_perm.resize(size); | |
| m_invPerm.resize(size); | |
| for (Index i = 0; i < size; ++i) { | |
| m_perm[i] = postorder[ordered[i]]; | |
| m_invPerm[m_perm[i]] = toStorageIndex(i); | |
| } | |
| // Each column's number of rows below its diagonal in L, from the rows of the upper triangle (Gilbert, Ng and Peyton, | |
| // 1994). | |
| using SymbolicHelper = internal::simpl_chol_helper<Scalar, StorageIndex>; | |
| const StorageIndex n = toStorageIndex(size); | |
| std::vector<StorageIndex> rowStart(size + 1, 0); | |
| SymbolicHelper::calc_hadj_outer(n, upper, rowStart.data()); | |
| std::vector<StorageIndex> rowColumns(rowStart[size]); | |
| std::vector<StorageIndex> count(size); | |
| { | |
| std::vector<StorageIndex> work(size); | |
| IndexVectorType previousLeaf = IndexVectorType::Constant(size, none); | |
| SymbolicHelper::calc_hadj_inner(n, upper, rowStart.data(), rowColumns.data(), work.data()); | |
| IndexVectorType inPostorder(size); | |
| for (Index j = 0; j < size; ++j) inPostorder[postorder[j]] = toStorageIndex(j); | |
| SymbolicHelper::calc_colcount(n, rowStart.data(), rowColumns.data(), parent.data(), previousLeaf.data(), | |
| work.data(), inPostorder.data(), count.data(), /*doLDLT=*/true); | |
| } | |
| // Fundamental supernodes: column j joins column j - 1's front if it's j - 1's parent and only child, and | |
| // count(j - 1) = count(j) + 1. pattern(L_{j-1}) \ {j} is a subset of pattern(L_j), so the counts make them equal. | |
| // mergeRelaxedFronts() then relaxes these fronts. | |
| std::vector<StorageIndex> columnParent(size, none); | |
| std::vector<StorageIndex> columnBelow(size); | |
| std::vector<StorageIndex> numChildren(size, 0); | |
| for (Index j = 0; j < size; ++j) { | |
| columnBelow[postorder[j]] = count[j]; | |
| if (parent[j] != none) { | |
| columnParent[postorder[j]] = postorder[parent[j]]; | |
| ++numChildren[postorder[parent[j]]]; | |
| } | |
| } | |
| m_frontColumns.clear(); | |
| std::vector<StorageIndex> columnFront(size); | |
| for (Index j = 0; j < size; ++j) { | |
| const bool extends = | |
| j > 0 && columnParent[j - 1] == j && numChildren[j] == 1 && columnBelow[j - 1] == columnBelow[j] + 1; | |
| if (!extends) m_frontColumns.push_back(toStorageIndex(j)); | |
| columnFront[j] = toStorageIndex(m_frontColumns.size() - 1); | |
| } | |
| m_frontColumns.push_back(n); | |
| { | |
| const Index numFundamental = static_cast<Index>(m_frontColumns.size()) - 1; | |
| std::vector<StorageIndex> frontParent(numFundamental); | |
| std::vector<StorageIndex> frontBelow(numFundamental); | |
| for (Index s = 0; s < numFundamental; ++s) { | |
| const StorageIndex last = m_frontColumns[s + 1] - 1; | |
| frontParent[s] = columnParent[last] == none ? none : columnFront[columnParent[last]]; | |
| frontBelow[s] = columnBelow[last]; | |
| } | |
| std::vector<StorageIndex> newColumn; | |
| mergeRelaxedFronts(frontParent, frontBelow, columnFront, newColumn); | |
| for (Index j = 0; j < size; ++j) postorder[j] = newColumn[postorder[j]]; | |
| } | |
| const Index numFronts = static_cast<Index>(m_frontColumns.size()) - 1; | |
| // Each column of the ordered matrix in m_perm's numbering, and the reverse. | |
| const IndexVectorType& columnOf = postorder; | |
| std::vector<StorageIndex> orderedColumn(size); | |
| for (Index j = 0; j < size; ++j) orderedColumn[columnOf[j]] = toStorageIndex(j); | |
| // Each front's parent and children. A front's parent holds the parent of its last column. | |
| m_frontParent.assign(numFronts, none); | |
| m_childStart.assign(numFronts + 1, 0); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const StorageIndex last = orderedColumn[m_frontColumns[s + 1] - 1]; | |
| if (parent[last] != none) { | |
| m_frontParent[s] = columnFront[columnOf[parent[last]]]; | |
| ++m_childStart[m_frontParent[s] + 1]; | |
| } | |
| } | |
| for (Index s = 0; s < numFronts; ++s) m_childStart[s + 1] += m_childStart[s]; | |
| m_children.resize(m_childStart[numFronts]); | |
| { | |
| std::vector<std::size_t> next(m_childStart.begin(), m_childStart.end() - 1); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| if (m_frontParent[s] != none) m_children[next[m_frontParent[s]]++] = toStorageIndex(s); | |
| } | |
| } | |
| // Each front's columns, then its rows below them: pattern(L_last) for its last column, which is the rows past its | |
| // columns in its columns of A and in its children's rows below. | |
| m_belowStart.assign(numFronts + 1, 0); | |
| m_frontRowList.clear(); | |
| { | |
| std::size_t numRows = static_cast<std::size_t>(size); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| numRows += static_cast<std::size_t>(count[orderedColumn[m_frontColumns[s + 1] - 1]]); | |
| } | |
| m_frontRowList.reserve(numRows); | |
| } | |
| { | |
| std::vector<StorageIndex> mark(size, none); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const StorageIndex front = toStorageIndex(s); | |
| const StorageIndex end = m_frontColumns[s + 1]; | |
| for (StorageIndex j = m_frontColumns[s]; j < end; ++j) m_frontRowList.push_back(j); | |
| const std::size_t first = m_frontRowList.size(); | |
| const auto add = [&](StorageIndex row) { | |
| if (row >= end && mark[row] != front) { | |
| mark[row] = front; | |
| m_frontRowList.push_back(row); | |
| } | |
| }; | |
| for (StorageIndex j = m_frontColumns[s]; j < end; ++j) { | |
| const StorageIndex column = orderedColumn[j]; | |
| const StorageIndex rowEnd = rowStart[column + 1]; | |
| for (StorageIndex k = rowStart[column]; k < rowEnd; ++k) add(columnOf[rowColumns[k]]); | |
| } | |
| const std::size_t childEnd = m_childStart[s + 1]; | |
| for (std::size_t c = m_childStart[s]; c < childEnd; ++c) { | |
| const StorageIndex child = m_children[c]; | |
| const std::size_t childFirst = m_belowStart[child] + static_cast<std::size_t>(m_frontColumns[child + 1]); | |
| const std::size_t childLast = m_belowStart[child + 1] + static_cast<std::size_t>(m_frontColumns[child + 1]); | |
| for (std::size_t k = childFirst; k < childLast; ++k) add(m_frontRowList[k]); | |
| } | |
| m_belowStart[s + 1] = m_belowStart[s] + (m_frontRowList.size() - first); | |
| eigen_internal_assert(m_belowStart[s + 1] - m_belowStart[s] == | |
| static_cast<std::size_t>(count[orderedColumn[end - 1]])); | |
| } | |
| } | |
| // Sorts each front's rows below with a counting transpose: list each row's fronts, then write the rows back to their | |
| // fronts in increasing order. | |
| { | |
| const auto belowRows = [&](Index s) { | |
| return m_frontRowList.begin() + static_cast<std::ptrdiff_t>(m_belowStart[s] + m_frontColumns[s + 1]); | |
| }; | |
| std::vector<std::size_t> rowFrontStart(size + 1, 0); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const auto end = belowRows(s) + static_cast<std::ptrdiff_t>(m_belowStart[s + 1] - m_belowStart[s]); | |
| for (auto row = belowRows(s); row != end; ++row) { | |
| ++rowFrontStart[*row + 1]; | |
| } | |
| } | |
| for (Index i = 0; i < size; ++i) rowFrontStart[i + 1] += rowFrontStart[i]; | |
| std::vector<StorageIndex> rowFronts(rowFrontStart[size]); | |
| { | |
| std::vector<std::size_t> next(rowFrontStart.begin(), rowFrontStart.end() - 1); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const auto end = belowRows(s) + static_cast<std::ptrdiff_t>(m_belowStart[s + 1] - m_belowStart[s]); | |
| for (auto row = belowRows(s); row != end; ++row) { | |
| rowFronts[next[*row]++] = toStorageIndex(s); | |
| } | |
| } | |
| } | |
| std::vector<std::size_t> next(numFronts); | |
| for (Index s = 0; s < numFronts; ++s) next[s] = m_belowStart[s] + static_cast<std::size_t>(m_frontColumns[s + 1]); | |
| for (Index i = 0; i < size; ++i) { | |
| const std::size_t end = rowFrontStart[i + 1]; | |
| for (std::size_t k = rowFrontStart[i]; k < end; ++k) { | |
| m_frontRowList[next[rowFronts[k]]++] = toStorageIndex(i); | |
| } | |
| } | |
| } | |
| // Where each entry of the input matrix is assembled. The row is global until the loop over fronts below. | |
| m_assemblyStart.assign(numFronts + 1, 0); | |
| m_numValues = static_cast<std::size_t>(matrix.nonZeros()); | |
| visitTriangle(matrix, [&](Index row, Index col, Index) { | |
| ++m_assemblyStart[columnFront[numext::mini(m_perm[row], m_perm[col])] + 1]; | |
| }); | |
| for (Index s = 0; s < numFronts; ++s) m_assemblyStart[s + 1] += m_assemblyStart[s]; | |
| m_assembly.resize(m_assemblyStart[numFronts]); | |
| { | |
| std::vector<std::size_t> next(m_assemblyStart.begin(), m_assemblyStart.end() - 1); | |
| visitTriangle(matrix, [&](Index row, Index col, Index value) { | |
| const StorageIndex i = m_perm[row]; | |
| const StorageIndex j = m_perm[col]; | |
| const StorageIndex s = columnFront[numext::mini(i, j)]; | |
| m_assembly[next[s]++] = Assembly{toStorageIndex(value), numext::maxi(i, j), | |
| toStorageIndex(numext::mini(i, j) - m_frontColumns[s]), i < j}; | |
| }); | |
| } | |
| // The position of each row in front s, not counting delayed columns: row - first column for its columns, then the | |
| // rows below them in order. Each front's children and entries of A take their positions from it. | |
| m_belowToParent.resize(m_belowStart[numFronts]); | |
| { | |
| std::vector<StorageIndex> position(size); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const StorageIndex first = m_frontColumns[s]; | |
| const StorageIndex end = m_frontColumns[s + 1]; | |
| for (StorageIndex j = first; j < end; ++j) position[j] = j - first; | |
| const std::size_t rows = m_belowStart[s] + static_cast<std::size_t>(end); | |
| for (std::size_t k = 0; k < m_belowStart[s + 1] - m_belowStart[s]; ++k) { | |
| position[m_frontRowList[rows + k]] = toStorageIndex(Index(end - first) + Index(k)); | |
| } | |
| for (std::size_t c = m_childStart[s]; c < m_childStart[s + 1]; ++c) { | |
| const StorageIndex child = m_children[c]; | |
| for (std::size_t k = m_belowStart[child]; k < m_belowStart[child + 1]; ++k) { | |
| m_belowToParent[k] = position[m_frontRowList[k + static_cast<std::size_t>(m_frontColumns[child + 1])]]; | |
| } | |
| } | |
| for (std::size_t k = m_assemblyStart[s]; k < m_assemblyStart[s + 1]; ++k) { | |
| m_assembly[k].row = position[m_assembly[k].row]; | |
| } | |
| } | |
| } | |
| m_symbolicFactorSize = 0; | |
| m_symbolicStackSize = 0; | |
| m_symbolicFrontOrder = 0; | |
| { | |
| std::size_t stack = 0; | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const Index numColumns = m_frontColumns[s + 1] - m_frontColumns[s]; | |
| const Index numBelow = static_cast<Index>(m_belowStart[s + 1] - m_belowStart[s]); | |
| m_symbolicFactorSize += rectangleSize(numColumns + numBelow, numColumns); | |
| m_symbolicFrontOrder = numext::maxi(m_symbolicFrontOrder, numColumns + numBelow); | |
| for (std::size_t c = m_childStart[s]; c < m_childStart[s + 1]; ++c) { | |
| const StorageIndex child = m_children[c]; | |
| stack -= packedSize(static_cast<Index>(m_belowStart[child + 1] - m_belowStart[child])); | |
| } | |
| stack += packedSize(numBelow); | |
| m_symbolicStackSize = numext::maxi(m_symbolicStackSize, stack); | |
| } | |
| } | |
| m_numDelayed.resize(numFronts); | |
| m_factoredFronts.resize(numFronts); | |
| m_pivots.resize(size); | |
| m_D.resize(size); | |
| m_subdiagonal.resize(size); | |
| m_P.resize(size); | |
| m_Pinv.resize(size); | |
| m_info = InvalidInput; | |
| m_isInitialized = true; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorize(const MatrixType& matrix) { | |
| eigen_assert(m_isInitialized && "analyzePattern() must be called first."); | |
| eigen_assert(matrix.rows() == rows() && matrix.cols() == rows()); | |
| eigen_assert(static_cast<std::size_t>(matrix.nonZeros()) == m_numValues && | |
| "The matrix must have the analyzed sparsity pattern."); | |
| // A compressed matrix is read in place. | |
| const Scalar* values = matrix.valuePtr(); | |
| if (!matrix.isCompressed()) { | |
| m_values.resize(m_numValues); | |
| std::size_t value = 0; | |
| for (Index outer = 0; outer < matrix.outerSize(); ++outer) { | |
| for (typename MatrixType::InnerIterator it(matrix, outer); it; ++it) m_values[value++] = it.value(); | |
| } | |
| values = m_values.data(); | |
| } | |
| // Delayed pivots can still outgrow these. | |
| m_L.reserve(m_symbolicFactorSize); | |
| m_stack.reserve(m_symbolicStackSize); | |
| m_factorRows.reserve(m_frontRowList.size()); | |
| if (m_front.size() < rectangleSize(m_symbolicFrontOrder, m_symbolicFrontOrder)) { | |
| m_front.resize(rectangleSize(m_symbolicFrontOrder, m_symbolicFrontOrder)); | |
| } | |
| m_L.clear(); | |
| m_LNonZeros = 0; | |
| m_factorRows.clear(); | |
| m_stack.clear(); | |
| m_numPivots = 0; | |
| m_numPositive = 0; | |
| m_numNegative = 0; | |
| m_numZero = 0; | |
| m_maxFrontOrder = 0; | |
| m_hasZeroPivot = false; | |
| const Index numFronts = static_cast<Index>(m_frontColumns.size()) - 1; | |
| // None of these are reallocated during the factorization, but the calls below stop the compiler from proving it. | |
| const StorageIndex* const frontColumns = m_frontColumns.data(); | |
| const std::size_t* const belowStart = m_belowStart.data(); | |
| const std::size_t* const childStart = m_childStart.data(); | |
| const StorageIndex* const children = m_children.data(); | |
| const StorageIndex* const numDelayed = m_numDelayed.data(); | |
| const std::size_t* const assemblyStart = m_assemblyStart.data(); | |
| const Assembly* const assembly = m_assembly.data(); | |
| const StorageIndex* const frontRowList = m_frontRowList.data(); | |
| const StorageIndex* const belowToParent = m_belowToParent.data(); | |
| const StorageIndex* const frontParent = m_frontParent.data(); | |
| for (Index s = 0; s < numFronts; ++s) { | |
| const Index firstColumn = frontColumns[s]; | |
| const Index numColumns = frontColumns[s + 1] - firstColumn; | |
| const Index numBelow = static_cast<Index>(belowStart[s + 1] - belowStart[s]); | |
| Index delayedIn = 0; | |
| for (std::size_t c = childStart[s]; c < childStart[s + 1]; ++c) delayedIn += numDelayed[children[c]]; | |
| const Index fullySummed = delayedIn + numColumns; | |
| const Index order = fullySummed + numBelow; | |
| m_maxFrontOrder = numext::maxi(m_maxFrontOrder, order); | |
| const std::size_t frontSize = rectangleSize(order, order); | |
| if (m_front.size() < frontSize) m_front.resize(frontSize); | |
| StorageIndex* rows = m_factorRows.push(static_cast<std::size_t>(order)); | |
| FrontMap front(m_front.data(), order, order); | |
| // Only the lower triangle is read, but a single fill is cheaper than one per column for a small front. Filling the | |
| // whole of a larger one would also push the working set out of the L1 cache. | |
| if (order < kBlockedFrontMinOrder) { | |
| front.setZero(); | |
| } else { | |
| for (Index j = 0; j < order; ++j) front.col(j).tail(order - j).setZero(); | |
| } | |
| for (std::size_t k = assemblyStart[s]; k < assemblyStart[s + 1]; ++k) { | |
| const Assembly& entry = assembly[k]; | |
| const Scalar& value = values[entry.value]; | |
| front(entry.row + delayedIn, entry.col + delayedIn) += entry.conjugate ? Scalar(numext::conj(value)) : value; | |
| } | |
| // The delayed rows come first, and the children fill them in below. | |
| const StorageIndex* rowList = frontRowList + belowStart[s] + firstColumn; | |
| internal::smart_copy(rowList, rowList + numColumns + numBelow, rows + delayedIn); | |
| // Extend-add the children's contribution blocks. They're on a stack, so the last child's is on top. | |
| Index delayedSlot = delayedIn; | |
| const std::size_t childBegin = childStart[s]; | |
| for (std::size_t c = childStart[s + 1]; c > childBegin; --c) { | |
| const Index child = children[c - 1]; | |
| const Index delayed = numDelayed[child]; | |
| const Index childBelow = static_cast<Index>(belowStart[child + 1] - belowStart[child]); | |
| const Index childOrder = delayed + childBelow; | |
| delayedSlot -= delayed; | |
| // Without delayed columns on either side, the symbolic map is the map. | |
| const StorageIndex* childMap = belowToParent + belowStart[child]; | |
| if (delayedIn > 0) { | |
| if (m_childMap.size() < static_cast<std::size_t>(childOrder)) m_childMap.resize(childOrder); | |
| const FactoredFront& factored = m_factoredFronts[child]; | |
| const StorageIndex* delayedRows = m_factorRows.storage.data() + factored.rows + factored.numPivots; | |
| for (Index i = 0; i < delayed; ++i) { | |
| m_childMap[i] = internal::convert_index<StorageIndex>(delayedSlot + i); | |
| rows[delayedSlot + i] = delayedRows[i]; | |
| } | |
| for (Index i = 0; i < childBelow; ++i) { | |
| m_childMap[delayed + i] = internal::convert_index<StorageIndex>(delayedIn + childMap[i]); | |
| } | |
| childMap = m_childMap.data(); | |
| } | |
| // Delayed rows come before the rows below in both the child and the parent, and the rows below keep their | |
| // relative order. So the map is increasing and the lower triangle stays the lower triangle. | |
| const std::size_t blockSize = packedSize(childOrder); | |
| const Scalar* block = m_stack.top(blockSize); | |
| if (childOrder < kVectorizedMinLength) { | |
| scatterAdd(order, block, childMap, childOrder); | |
| } else { | |
| extendAdd(order, block, childMap, childOrder); | |
| } | |
| m_stack.pop(blockSize); | |
| } | |
| const bool isRoot = frontParent[s] == -1; | |
| if (fullySummed == 1 && factorOnePivotFront(s, order, isRoot)) continue; | |
| const Index numPivots = factorFront(order, fullySummed, isRoot); | |
| Scalar* factor = appendFactor(s, numPivots, order); | |
| internal::smart_copy(m_front.data(), m_front.data() + rectangleSize(order, numPivots), factor); | |
| pushToParent(s, order, fullySummed, numPivots); | |
| } | |
| // Roots can't delay, so every pivot, and with it every entry of m_D and m_subdiagonal, has been written. | |
| const Index size = rows(); | |
| eigen_internal_assert(m_numPivots == size); | |
| for (Index k = 0; k < size; ++k) { | |
| const StorageIndex row = m_invPerm[m_pivots[k]]; | |
| m_Pinv.indices()[k] = row; | |
| m_P.indices()[row] = internal::convert_index<StorageIndex>(k); | |
| } | |
| // Inertia from the signs of D (Sylvester's law). A 2x2 block with det < 0 has one eigenvalue of each sign; otherwise | |
| // both eigenvalues have the sign of its trace. | |
| bool finite = true; | |
| m_blocks.clear(); | |
| for (Index k = 0; k < size; ++k) { | |
| const RealScalar d1 = m_D[k]; | |
| const RealScalar sub = numext::abs(m_subdiagonal[k]); | |
| if (sub != RealScalar(0)) { | |
| const RealScalar d2 = m_D[k + 1]; | |
| m_blocks.emplace_back(d1, d2, sub); | |
| if (!(numext::isfinite)(d1) || !(numext::isfinite)(sub) || !(numext::isfinite)(d2)) { | |
| finite = false; | |
| } else if (m_blocks.back().det < RealScalar(0)) { | |
| ++m_numPositive; | |
| ++m_numNegative; | |
| } else if (d1 + d2 > RealScalar(0)) { | |
| m_numPositive += 2; | |
| } else { | |
| m_numNegative += 2; | |
| } | |
| ++k; | |
| } else if (!(numext::isfinite)(d1)) { | |
| finite = false; | |
| } else if (d1 > RealScalar(0)) { | |
| ++m_numPositive; | |
| } else if (d1 < RealScalar(0)) { | |
| ++m_numNegative; | |
| } else { | |
| ++m_numZero; | |
| } | |
| } | |
| m_info = finite && !m_hasZeroPivot ? Success : NumericalIssue; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::RealScalar | |
| MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::logAbsDeterminant() const { | |
| eigen_assert(m_isInitialized && "Decomposition is not initialized."); | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before logAbsDeterminant()."); | |
| RealScalar result(0); | |
| for (Index k = 0; k < rows(); ++k) { | |
| const RealScalar sub = numext::abs(m_subdiagonal[k]); | |
| if (sub != RealScalar(0)) { | |
| const ScaledBlock block(m_D[k], m_D[k + 1], sub); | |
| result += RealScalar(2) * numext::log(block.scale) + numext::log(numext::abs(block.det)); | |
| ++k; | |
| } else { | |
| result += numext::log(numext::abs(m_D[k])); | |
| } | |
| } | |
| return result; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::Scalar* | |
| MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::appendFactor(Index s, Index numPivots, Index order) { | |
| m_factoredFronts[s] = | |
| FactoredFront{internal::convert_index<StorageIndex>(numPivots), internal::convert_index<StorageIndex>(order), | |
| m_factorRows.size - order, m_L.size}; | |
| m_LNonZeros += static_cast<Index>(factorSize(numPivots, order)); | |
| return m_L.push(rectangleSize(order, numPivots)); | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::extendAdd(Index order, const Scalar* block, | |
| const StorageIndex* map, Index childOrder) { | |
| if (m_childRunEnd.size() < static_cast<std::size_t>(childOrder)) m_childRunEnd.resize(childOrder); | |
| Index numRuns = 1; | |
| Index runEnd = childOrder; | |
| m_childRunEnd[childOrder - 1] = internal::convert_index<StorageIndex>(runEnd); | |
| for (Index i = childOrder - 2; i >= 0; --i) { | |
| if (map[i + 1] != map[i] + 1) { | |
| runEnd = i + 1; | |
| ++numRuns; | |
| } | |
| m_childRunEnd[i] = internal::convert_index<StorageIndex>(runEnd); | |
| } | |
| if (childOrder < kExtendAddMinRunLength * numRuns) { | |
| scatterAdd(order, block, map, childOrder); | |
| return; | |
| } | |
| FrontMap front(m_front.data(), order, order); | |
| for (Index j = 0; j < childOrder; ++j) { | |
| Scalar* column = &front.coeffRef(0, map[j]); | |
| for (Index i = j; i < childOrder;) { | |
| const Index end = m_childRunEnd[i]; | |
| addTo(column + map[i], block, end - i); | |
| block += end - i; | |
| i = end; | |
| } | |
| } | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::RealScalar | |
| MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::frontColumnMax(Index order, Index active, Index j, Index skip) const { | |
| ConstFrontMap front(m_front.data(), order, order); | |
| RealScalar result(0); | |
| for (Index i = active; i < j; ++i) { | |
| if (i != skip) result = numext::maxi(result, RealScalar(numext::abs(front(j, i)))); | |
| } | |
| const Scalar* column = &front.coeffRef(0, j); | |
| const Index split = skip > j ? skip : order; | |
| result = numext::maxi(result, largestMagnitude(column + j + 1, split - j - 1)); | |
| if (order > split + 1) result = numext::maxi(result, largestMagnitude(column + split + 1, order - split - 1)); | |
| return result; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| bool MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::frontColumnIsZero(Index order, Index active, Index j) const { | |
| ConstFrontMap front(m_front.data(), order, order); | |
| return (front.row(j).segment(active, j - active).array() == Scalar(0)).all() && | |
| (front.col(j).tail(order - j - 1).array() == Scalar(0)).all(); | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| Index MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::largestFullySummed(Index order, Index active, Index fullySummed, | |
| Index j, RealScalar& rest) const { | |
| ConstFrontMap front(m_front.data(), order, order); | |
| Index r = -1; | |
| RealScalar largest(0); | |
| rest = RealScalar(0); | |
| const auto visit = [&](Index i, const RealScalar& magnitude) { | |
| if (magnitude > largest) { | |
| rest = largest; | |
| largest = magnitude; | |
| r = i; | |
| } else { | |
| rest = numext::maxi(rest, magnitude); | |
| } | |
| }; | |
| for (Index i = active; i < j; ++i) visit(i, numext::abs(front(j, i))); | |
| for (Index i = j + 1; i < fullySummed; ++i) visit(i, numext::abs(front(i, j))); | |
| rest = numext::maxi(rest, largestMagnitude(&front.coeffRef(0, j) + fullySummed, order - fullySummed)); | |
| return r; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| EIGEN_ALWAYS_INLINE bool MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorOnePivotFront(Index s, Index order, | |
| bool isRoot) { | |
| ConstFrontMap front(m_front.data(), order, order); | |
| const RealScalar d = numext::real(front(0, 0)); | |
| if (d == RealScalar(0)) return false; | |
| // The root has no parent to delay to, and has no rows below its only diagonal to bound. With one fully summed column, | |
| // there's no 2x2 pivot to try instead. | |
| if (!isRoot && !(numext::abs(d) >= m_threshold * frontColumnMax(order, 0, 0, -1))) { | |
| appendFactor(s, 0, order); | |
| pushToParent(s, order, 1, 0); | |
| return true; | |
| } | |
| m_D[m_numPivots] = d; | |
| m_subdiagonal[m_numPivots] = Scalar(0); | |
| m_pivots[m_numPivots] = frontRows(order)[0]; | |
| ++m_numPivots; | |
| m_numDelayed[s] = 0; | |
| const Index numBelow = order - 1; | |
| Scalar* L = appendFactor(s, 1, order); | |
| Scalar* contribution = m_stack.push(packedSize(numBelow)); | |
| const Scalar* u = &front.coeffRef(0, 0); | |
| for (Index j = 1; j < order; ++j) { | |
| const Index length = order - j; | |
| const Scalar lj = numext::conj(u[j]) / d; | |
| const Scalar* column = &front.coeffRef(j, j); | |
| if (length < kVectorizedMinLength) { | |
| for (Index i = 0; i < length; ++i) contribution[i] = column[i] - u[j + i] * lj; | |
| } else { | |
| VectorMap(contribution, length) = ConstVectorMap(column, length) - ConstVectorMap(u + j, length) * lj; | |
| } | |
| contribution += length; | |
| L[j] = numext::conj(lj); | |
| } | |
| return true; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::pushToParent(Index s, Index order, Index fullySummed, | |
| Index numPivots) { | |
| const Index numDelayed = fullySummed - numPivots; | |
| m_numDelayed[s] = internal::convert_index<StorageIndex>(numDelayed); | |
| ConstFrontMap front(m_front.data(), order, order); | |
| Scalar* contribution = m_stack.push(packedSize(order - numPivots)); | |
| if (order <= kSmallFrontMaxOrder) { | |
| const Index end = numext::mini(order, Index(kSmallFrontMaxOrder)); | |
| for (Index j = numPivots; j < end; ++j) { | |
| for (Index i = j; i < end; ++i) *contribution++ = front(i, j); | |
| } | |
| return; | |
| } | |
| for (Index j = numPivots; j < order; ++j) { | |
| internal::smart_copy(&front.coeffRef(j, j), &front.coeffRef(j, j) + (order - j), contribution); | |
| contribution += order - j; | |
| } | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::swapFront(Index order, Index a, Index b) { | |
| if (a == b) return; | |
| if (a > b) std::swap(a, b); | |
| FrontMap front(m_front.data(), order, order); | |
| internal::selfadjoint_swap_lower(front, a, b); | |
| std::swap(frontRows(order)[a], frontRows(order)[b]); | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::eliminate1x1(Index order, Index k, Index panelEnd) { | |
| FrontMap front(m_front.data(), order, order); | |
| const RealScalar d = numext::real(front(k, k)); | |
| m_D[m_numPivots] = d; | |
| m_subdiagonal[m_numPivots] = Scalar(0); | |
| m_pivots[m_numPivots] = frontRows(order)[k]; | |
| ++m_numPivots; | |
| if (d == RealScalar(0)) { | |
| // The pivot test only accepts a zero pivot if its column is zero, so L's column is already zero. | |
| m_hasZeroPivot = true; | |
| return; | |
| } | |
| // Column k becomes L's column as each quotient is computed. Later columns only read the entries below their own row, | |
| // which are still unscaled. | |
| if (order <= kSmallFrontMaxOrder) { | |
| // A front this small is its own panel. | |
| const Index end = numext::mini(order, Index(kSmallFrontMaxOrder)); | |
| for (Index j = k + 1; j < end; ++j) { | |
| const Scalar lj = numext::conj(front(j, k)) / d; | |
| for (Index i = j; i < end; ++i) front(i, j) -= front(i, k) * lj; | |
| front(j, k) = numext::conj(lj); | |
| } | |
| return; | |
| } | |
| for (Index j = k + 1; j < panelEnd; ++j) { | |
| const Scalar lj = numext::conj(front(j, k)) / d; | |
| subtractScaled(&front.coeffRef(j, j), &front.coeffRef(j, k), lj, order - j); | |
| front(j, k) = numext::conj(lj); | |
| } | |
| front.col(k).tail(order - panelEnd) = front.col(k).tail(order - panelEnd) / d; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::eliminate2x2(Index order, Index k, Index panelEnd) { | |
| FrontMap front(m_front.data(), order, order); | |
| const RealScalar d11 = numext::real(front(k, k)); | |
| const Scalar d21 = front(k + 1, k); | |
| const RealScalar d22 = numext::real(front(k + 1, k + 1)); | |
| m_D[m_numPivots] = d11; | |
| m_D[m_numPivots + 1] = d22; | |
| m_subdiagonal[m_numPivots] = d21; | |
| m_subdiagonal[m_numPivots + 1] = Scalar(0); | |
| m_pivots[m_numPivots] = frontRows(order)[k]; | |
| m_pivots[m_numPivots + 1] = frontRows(order)[k + 1]; | |
| m_numPivots += 2; | |
| // L = U D^-1, with D scaled by its largest entry to keep its determinant in range. | |
| const ScaledBlock block(d11, d22, numext::abs(d21)); | |
| const Scalar b = d21 / block.scale; | |
| const Scalar conjB = numext::conj(b); | |
| const Index numRows = order - k - 2; | |
| // numRows can be zero, where coeffRef() would be out of bounds. | |
| Scalar* u1 = front.data() + rectangleSize(order, k) + (k + 2); | |
| Scalar* u2 = u1 + order; | |
| if (order <= kSmallFrontMaxOrder) { | |
| // A front this small is its own panel. | |
| constexpr Index kMaxRows = kSmallFrontMaxOrder - 2; | |
| Scalar l1[kMaxRows], l2[kMaxRows]; | |
| const Index smallRows = numext::mini(numRows, kMaxRows); | |
| for (Index i = 0; i < smallRows; ++i) { | |
| l1[i] = ((u1[i] * block.c - u2[i] * b) / block.scale) / block.det; | |
| l2[i] = ((u2[i] * block.a - u1[i] * conjB) / block.scale) / block.det; | |
| } | |
| for (Index j = 0; j < smallRows; ++j) { | |
| const Scalar alpha1 = numext::conj(u1[j]); | |
| const Scalar alpha2 = numext::conj(u2[j]); | |
| Scalar* column = &front.coeffRef(k + 2, k + 2 + j); | |
| for (Index i = j; i < smallRows; ++i) column[i] -= l1[i] * alpha1 + l2[i] * alpha2; | |
| } | |
| for (Index i = 0; i < smallRows; ++i) { | |
| u1[i] = l1[i]; | |
| u2[i] = l2[i]; | |
| } | |
| front(k + 1, k) = Scalar(0); | |
| return; | |
| } | |
| if (m_pivotScratch.size() < rectangleSize(2, numRows)) m_pivotScratch.resize(rectangleSize(2, numRows)); | |
| Scalar* l1 = m_pivotScratch.data(); | |
| Scalar* l2 = l1 + numRows; | |
| if (numRows < kVectorizedMinLength) { | |
| for (Index i = 0; i < numRows; ++i) { | |
| l1[i] = ((u1[i] * block.c - u2[i] * b) / block.scale) / block.det; | |
| l2[i] = ((u2[i] * block.a - u1[i] * conjB) / block.scale) / block.det; | |
| } | |
| } else { | |
| const ConstVectorMap mapU1(u1, numRows); | |
| const ConstVectorMap mapU2(u2, numRows); | |
| VectorMap(l1, numRows) = ((mapU1 * block.c - mapU2 * b) / block.scale) / block.det; | |
| VectorMap(l2, numRows) = ((mapU2 * block.a - mapU1 * conjB) / block.scale) / block.det; | |
| } | |
| for (Index j = k + 2; j < panelEnd; ++j) { | |
| const Index offset = j - k - 2; | |
| subtractScaled(&front.coeffRef(j, j), l1 + offset, numext::conj(u1[offset]), l2 + offset, numext::conj(u2[offset]), | |
| numRows - offset); | |
| } | |
| front(k + 1, k) = Scalar(0); | |
| internal::smart_copy(l1, l1 + numRows, u1); | |
| internal::smart_copy(l2, l2 + numRows, u2); | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::updateTrailing(Index order, Index firstPivot, Index numPivots, | |
| Index panelEnd) { | |
| const Index trailing = order - panelEnd; | |
| if (trailing == 0 || numPivots == 0) return; | |
| FrontMap front(m_front.data(), order, order); | |
| if (m_pivotScratch.size() < rectangleSize(trailing, numPivots)) { | |
| m_pivotScratch.resize(rectangleSize(trailing, numPivots)); | |
| } | |
| FrontMap W(m_pivotScratch.data(), trailing, numPivots); | |
| const auto L21 = front.block(panelEnd, firstPivot, trailing, numPivots); | |
| // W = L21 D | |
| Index p = m_numPivots - numPivots; | |
| for (Index c = 0; c < numPivots; ++c, ++p) { | |
| if (m_subdiagonal[p] != Scalar(0)) { | |
| W.col(c) = L21.col(c) * m_D[p] + L21.col(c + 1) * m_subdiagonal[p]; | |
| W.col(c + 1) = L21.col(c) * numext::conj(m_subdiagonal[p]) + L21.col(c + 1) * m_D[p + 1]; | |
| ++c; | |
| ++p; | |
| } else { | |
| W.col(c) = L21.col(c) * m_D[p]; | |
| } | |
| } | |
| front.bottomRightCorner(trailing, trailing).template triangularView<Lower>() -= W * L21.adjoint(); | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| Index MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorFront(Index order, Index fullySummed, bool isRoot) { | |
| FrontMap front(m_front.data(), order, order); | |
| // Pivots [0, k) have been applied to the columns before panelEnd, and pivots [applied, k) have yet to be applied to | |
| // the others. Every pivot decision reads only current entries, so it's the one an unblocked factorization would make: | |
| // the panel is flushed before reading a column past its end. After a flush, applied == k and any column can be read. | |
| Index k = 0; | |
| Index applied = 0; | |
| Index panelEnd = order < kBlockedFrontMinOrder ? order : numext::mini(Index(kPanelWidth), fullySummed); | |
| const auto flush = [&] { | |
| updateTrailing(order, applied, k - applied, panelEnd); | |
| applied = k; | |
| panelEnd = numext::mini(k + kPanelWidth, fullySummed); | |
| }; | |
| // A sweep tests each active column once, continuing past accepted pivots, so a column that keeps failing costs one | |
| // test per sweep instead of one per pivot. Columns [next, tail) are untested in this sweep. The front has no | |
| // acceptable pivot once every active column has failed since the last pivot, because those tests all read the same | |
| // values. | |
| Index next = 0; | |
| Index tail = fullySummed; | |
| bool acceptedPivot = false; | |
| // Without moved columns, the columns from here to the end have failed since the last pivot. | |
| Index lastPivotEnd = 0; | |
| while (k < fullySummed) { | |
| if (k >= panelEnd) flush(); | |
| if (next >= tail) { | |
| next = k; | |
| if (acceptedPivot) { | |
| tail = tail == fullySummed ? lastPivotEnd : fullySummed; | |
| acceptedPivot = false; | |
| continue; | |
| } | |
| tail = fullySummed; | |
| if (!isRoot) break; | |
| if (applied < k) flush(); | |
| // The pivot tests guarantee a pivot at the root, so only rounding error or a non-finite entry gets here. Take the | |
| // largest diagonal instead of leaving the column unfactored. | |
| Index largest; | |
| front.diagonal().segment(k, fullySummed - k).real().cwiseAbs().template maxCoeff<PropagateNumbers>(&largest); | |
| largest += k; | |
| swapFront(order, k, largest); | |
| // A zero here means the active diagonal is zero and every column is nonzero. The largest finite entry would pass | |
| // the 2x2 test, so some entry's magnitude isn't finite, and the pivot is NaN. | |
| if (numext::real(front(k, k)) == RealScalar(0)) { | |
| RealScalar nan = NumTraits<RealScalar>::quiet_NaN(); | |
| EIGEN_FAST_MATH_CONSTANT_BARRIER(nan); | |
| front(k, k) = Scalar(nan); | |
| } | |
| eliminate1x1(order, k, panelEnd); | |
| ++k; | |
| next = k; | |
| continue; | |
| } | |
| if (next >= panelEnd) { | |
| flush(); | |
| // Move the columns that failed in [k, next) past the untested ones, which fills the panel with untested columns | |
| // and lets it accept pivots without a flush for each one. | |
| const Index numUntested = tail - next; | |
| const Index numMoved = numext::mini(next - k, numUntested); | |
| for (Index i = 0; i < numMoved; ++i) swapFront(order, k + i, tail - 1 - i); | |
| next = k; | |
| tail = k + numUntested; | |
| } | |
| const Index j = next; | |
| const RealScalar djj = numext::real(front(j, j)); | |
| const RealScalar absDjj = numext::abs(djj); | |
| // A zero pivot eliminates nothing, so it's accepted only if its column is exactly zero. | |
| if (djj != RealScalar(0) ? absDjj >= m_threshold * frontColumnMax(order, k, j, -1) | |
| : frontColumnIsZero(order, k, j)) { | |
| swapFront(order, k, j); | |
| eliminate1x1(order, k, panelEnd); | |
| ++k; | |
| next = j + 1; | |
| lastPivotEnd = next; | |
| acceptedPivot = true; | |
| continue; | |
| } | |
| // Try a 2x2 pivot with the largest fully summed off-diagonal in column j. | |
| RealScalar columnJ; | |
| const Index r = largestFullySummed(order, k, fullySummed, j, columnJ); | |
| if (r == -1) { | |
| ++next; | |
| continue; | |
| } | |
| if (r >= panelEnd && applied < k) flush(); | |
| // With D = scale [a b*; b c], |D^-1| = 1/(scale |det|) [|c| |b|; |b| |a|] where det = a c - |b|^2. | |
| // | |
| // |det| >= |b|^2 / 2 gives |a c| + |b|^2 <= 5 |det|, so det and the solves with D lose at most a few digits to | |
| // cancellation. For the pair holding a root front's largest off-diagonal, b = 1 and |a|, |c| < u <= 1/2 if neither | |
| // passes the 1x1 test, so |det| >= 1 - u^2 >= 3/4 and the root guarantee still holds. | |
| const RealScalar drr = numext::real(front(r, r)); | |
| const ScaledBlock block(djj, drr, numext::abs(r > j ? front(r, j) : front(j, r))); | |
| const RealScalar a = numext::abs(block.a); | |
| const RealScalar b = block.absB; | |
| const RealScalar c = numext::abs(block.c); | |
| const RealScalar absDet = numext::abs(block.det); | |
| const RealScalar bound = absDet * block.scale / m_threshold; | |
| const RealScalar columnR = frontColumnMax(order, k, r, j); | |
| if (block.det != RealScalar(0) && absDet >= b * b / RealScalar(2) && c * columnJ + b * columnR <= bound && | |
| b * columnJ + a * columnR <= bound) { | |
| swapFront(order, k, j); | |
| // Swapping k and j moved whatever was at k to j. | |
| swapFront(order, k + 1, r == k ? j : r); | |
| eliminate2x2(order, k, panelEnd); | |
| k += 2; | |
| next = numext::maxi(j + 1, k); | |
| lastPivotEnd = next; | |
| acceptedPivot = true; | |
| } else { | |
| ++next; | |
| } | |
| } | |
| flush(); | |
| return k; | |
| } | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::FactorType | |
| MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::matrixL() const { | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before reading L."); | |
| // A front's rows are in elimination order, and L's rows and columns are in pivot order. | |
| std::vector<StorageIndex> pivotOf(rows()); | |
| for (Index k = 0; k < rows(); ++k) pivotOf[m_pivots[k]] = internal::convert_index<StorageIndex>(k); | |
| std::vector<Triplet<Scalar, StorageIndex>> entries; | |
| entries.reserve(static_cast<std::size_t>(m_LNonZeros) + static_cast<std::size_t>(rows())); | |
| for (const FactoredFront& factored : m_factoredFronts) { | |
| const Index order = factored.order; | |
| const StorageIndex* rows = m_factorRows.storage.data() + factored.rows; | |
| const Index numPivots = factored.numPivots; | |
| ConstFrontMap L(m_L.storage.data() + factored.values, order, numPivots); | |
| for (Index j = 0; j < numPivots; ++j) { | |
| const StorageIndex col = pivotOf[rows[j]]; | |
| entries.emplace_back(col, col, Scalar(1)); | |
| for (Index i = j + 1; i < order; ++i) entries.emplace_back(pivotOf[rows[i]], col, L(i, j)); | |
| } | |
| } | |
| FactorType result(rows(), cols()); | |
| result.setFromTriplets(entries.begin(), entries.end()); | |
| return result; | |
| } | |
| #ifndef EIGEN_PARSED_BY_DOXYGEN | |
| template <typename MatrixType_, int UpLo_, typename Ordering_> | |
| template <typename Rhs, typename Dest> | |
| void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::_solve_impl(const MatrixBase<Rhs>& rhs, | |
| MatrixBase<Dest>& dest) const { | |
| eigen_assert(m_isInitialized && "Decomposition is not initialized."); | |
| eigen_assert(m_info != InvalidInput && "factorize() must be called before solve()."); | |
| eigen_assert(rhs.rows() == rows()); | |
| const typename internal::nested_eval<Rhs, Dynamic>::type actualRhs(rhs.derived()); | |
| const Index numRhs = rhs.cols(); | |
| FrontMatrix X(rows(), numRhs); | |
| for (Index col = 0; col < numRhs; ++col) { | |
| for (Index i = 0; i < rows(); ++i) X(m_perm[i], col) = actualRhs.coeff(i, col); | |
| } | |
| // Each front's rows of X, so a large factor applies as one dense product. | |
| FrontMatrix Y(m_maxFrontOrder, numRhs); | |
| const auto gather = [&](const StorageIndex* rows, Index count) { | |
| for (Index col = 0; col < numRhs; ++col) { | |
| for (Index i = 0; i < count; ++i) Y(i, col) = X(rows[i], col); | |
| } | |
| }; | |
| const auto scatter = [&](const StorageIndex* rows, Index count) { | |
| for (Index col = 0; col < numRhs; ++col) { | |
| for (Index i = 0; i < count; ++i) X(rows[i], col) = Y(i, col); | |
| } | |
| }; | |
| // L Y = B | |
| for (const FactoredFront& factored : m_factoredFronts) { | |
| const Index order = factored.order; | |
| const Index numPivots = factored.numPivots; | |
| const StorageIndex* rows = m_factorRows.storage.data() + factored.rows; | |
| ConstFrontMap L(m_L.storage.data() + factored.values, order, numPivots); | |
| if (order * numPivots < kDenseSolveMinSize) { | |
| for (Index col = 0; col < numRhs; ++col) { | |
| Scalar* x = X.col(col).data(); | |
| for (Index j = 0; j < numPivots; ++j) { | |
| const Scalar value = x[rows[j]]; | |
| const Scalar* column = &L.coeffRef(0, j); | |
| for (Index i = j + 1; i < order; ++i) x[rows[i]] -= column[i] * value; | |
| } | |
| } | |
| } else { | |
| const Index numBelow = order - numPivots; | |
| gather(rows, order); | |
| // One right-hand side takes the vector kernels, which don't pack L. | |
| if (numRhs == 1) { | |
| auto y = Y.col(0); | |
| L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(y.head(numPivots)); | |
| y.segment(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * y.head(numPivots); | |
| } else { | |
| L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(Y.topRows(numPivots)); | |
| Y.middleRows(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * Y.topRows(numPivots); | |
| } | |
| scatter(rows, order); | |
| } | |
| } | |
| // D Z = Y. A zero pivot gets a zero solution, the minimum norm solution for that block. | |
| for (Index col = 0; col < numRhs; ++col) { | |
| Scalar* x = X.col(col).data(); | |
| auto block = m_blocks.cbegin(); | |
| for (Index k = 0; k < rows(); ++k) { | |
| const Index row = m_pivots[k]; | |
| if (m_subdiagonal[k] != Scalar(0)) { | |
| const Index nextRow = m_pivots[k + 1]; | |
| const Scalar b = m_subdiagonal[k] / block->scale; | |
| const Scalar y1 = x[row]; | |
| const Scalar y2 = x[nextRow]; | |
| x[row] = ((y1 * block->c - y2 * numext::conj(b)) / block->scale) / block->det; | |
| x[nextRow] = ((y2 * block->a - y1 * b) / block->scale) / block->det; | |
| ++block; | |
| ++k; | |
| } else if (m_D[k] != RealScalar(0)) { | |
| x[row] /= m_D[k]; | |
| } else { | |
| x[row] = Scalar(0); | |
| } | |
| } | |
| } | |
| // L^* W = Z | |
| for (auto factored = m_factoredFronts.rbegin(); factored != m_factoredFronts.rend(); ++factored) { | |
| const Index order = factored->order; | |
| const Index numPivots = factored->numPivots; | |
| const StorageIndex* rows = m_factorRows.storage.data() + factored->rows; | |
| ConstFrontMap L(m_L.storage.data() + factored->values, order, numPivots); | |
| if (order * numPivots < kDenseSolveMinSize) { | |
| for (Index col = 0; col < numRhs; ++col) { | |
| Scalar* x = X.col(col).data(); | |
| for (Index j = numPivots - 1; j >= 0; --j) { | |
| Scalar value = x[rows[j]]; | |
| const Scalar* column = &L.coeffRef(0, j); | |
| for (Index i = order - 1; i > j; --i) value -= numext::conj(column[i]) * x[rows[i]]; | |
| x[rows[j]] = value; | |
| } | |
| } | |
| } else { | |
| const Index numBelow = order - numPivots; | |
| gather(rows, order); | |
| if (numRhs == 1) { | |
| auto y = Y.col(0); | |
| y.head(numPivots).noalias() -= L.bottomRows(numBelow).adjoint() * y.segment(numPivots, numBelow); | |
| L.topRows(numPivots).adjoint().template triangularView<UnitUpper>().solveInPlace(y.head(numPivots)); | |
| } else { | |
| Y.topRows(numPivots).noalias() -= L.bottomRows(numBelow).adjoint() * Y.middleRows(numPivots, numBelow); | |
| L.topRows(numPivots).adjoint().template triangularView<UnitUpper>().solveInPlace(Y.topRows(numPivots)); | |
| } | |
| scatter(rows, numPivots); | |
| } | |
| } | |
| for (Index col = 0; col < numRhs; ++col) { | |
| for (Index i = 0; i < rows(); ++i) dest.coeffRef(i, col) = X(m_perm[i], col); | |
| } | |
| } | |
| #endif // EIGEN_PARSED_BY_DOXYGEN | |
| } // end namespace Eigen | |
| #endif // EIGEN_MULTIFRONTAL_LDLT_H |