| // This file is part of Eigen, a lightweight C++ template library | |
| // for linear algebra. | |
| // | |
| // Copyright (C) 2008-2011 Gael Guennebaud <gael.guennebaud@inria.fr> | |
| // Copyright (C) 2009 Keir Mierle <mierle@gmail.com> | |
| // Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com> | |
| // Copyright (C) 2011 Timothy E. Holy <tim.holy@gmail.com > | |
| // | |
| // 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-License-Identifier: MPL-2.0 | |
| #ifndef EIGEN_LDLT_H | |
| #define EIGEN_LDLT_H | |
| // IWYU pragma: private | |
| #include "./InternalHeaderCheck.h" | |
| namespace Eigen { | |
| namespace internal { | |
| template <typename MatrixType_, int UpLo_> | |
| struct traits<LDLT<MatrixType_, UpLo_> > : traits<MatrixType_> { | |
| using XprKind = MatrixXpr; | |
| using StorageKind = SolverStorage; | |
| using StorageIndex = int; | |
| enum { Flags = 0 }; | |
| }; | |
| template <typename MatrixType, int UpLo> | |
| struct LDLT_Traits; | |
| // PositiveSemiDef means positive semi-definite and non-zero; same for NegativeSemiDef | |
| enum SignMatrix { PositiveSemiDef, NegativeSemiDef, ZeroSign, Indefinite }; | |
| // Panel width of the blocked factorization (defined below); declared here for the size constructor. | |
| template <typename MatrixType> | |
| inline Index ldlt_blocksize(Index size); | |
| } // namespace internal | |
| /** \ingroup Cholesky_Module | |
| * | |
| * \class LDLT | |
| * | |
| * \brief Robust Cholesky decomposition of a matrix with pivoting | |
| * | |
| * \tparam MatrixType_ the type of the matrix of which to compute the LDL^T Cholesky decomposition | |
| * \tparam UpLo_ the triangular part that will be used for the decomposition: Lower (default) or Upper. | |
| * The other triangular part won't be read. | |
| * | |
| * Perform a robust Cholesky decomposition of a positive semidefinite or negative semidefinite | |
| * matrix \f$ A \f$ such that \f$ A = P^TLDL^*P \f$, where P is a permutation matrix, L | |
| * is lower triangular with a unit diagonal and D is a diagonal matrix. | |
| * | |
| * Each step pivots on the diagonal entry of largest magnitude of the remaining Schur complement | |
| * (complete diagonal pivoting, as in LAPACK's xPSTRF), so that for a semidefinite matrix of rank r | |
| * the n - r entries of D that vanish in exact arithmetic come last, at the level of rounding errors | |
| * and of either sign. Avoiding the square root on D also stabilizes the computation. | |
| * | |
| * LDLT does not determine a numerical rank, though. Also, do not use a Cholesky decomposition to | |
| * determine whether a system of equations has a solution. | |
| * | |
| * This class supports the \link InplaceDecomposition inplace decomposition \endlink mechanism. | |
| * | |
| * D is purely diagonal, so this class is not backward stable on indefinite matrices: it can report | |
| * \c Success for a factorization with a large backward error. If isPositive() and isNegative() both | |
| * return false, D has pivots of both signs: unless that comes from the rounding-level pivots of a | |
| * singular semidefinite matrix, the matrix is indefinite, and BunchKaufman, which produces a | |
| * block-diagonal D, should be used instead. | |
| * | |
| * \sa MatrixBase::ldlt(), SelfAdjointView::ldlt(), class LLT, class BunchKaufman | |
| */ | |
| template <typename MatrixType_, int UpLo_> | |
| class LDLT : public SolverBase<LDLT<MatrixType_, UpLo_> > { | |
| public: | |
| using MatrixType = MatrixType_; | |
| using Base = SolverBase<LDLT>; | |
| friend class SolverBase<LDLT>; | |
| EIGEN_GENERIC_PUBLIC_INTERFACE(LDLT) | |
| enum { | |
| MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, | |
| MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, | |
| UpLo = UpLo_ | |
| }; | |
| using TmpMatrixType = Matrix<Scalar, RowsAtCompileTime, 1, 0, MaxRowsAtCompileTime, 1>; | |
| using TranspositionType = Transpositions<RowsAtCompileTime, MaxRowsAtCompileTime>; | |
| using PermutationType = PermutationMatrix<RowsAtCompileTime, MaxRowsAtCompileTime>; | |
| using Traits = internal::LDLT_Traits<MatrixType, UpLo>; | |
| /** \brief Default Constructor. | |
| * | |
| * The default constructor is useful in cases in which the user intends to | |
| * perform decompositions via LDLT::compute(const MatrixType&). | |
| */ | |
| LDLT() | |
| : m_matrix(), | |
| m_l1_norm(0), | |
| m_transpositions(), | |
| m_sign(internal::ZeroSign), | |
| m_isInitialized(false), | |
| m_info(InvalidInput) {} | |
| /** \brief Default Constructor with memory preallocation | |
| * | |
| * Like the default constructor but with preallocation of the internal data | |
| * according to the specified problem \a size. | |
| * | |
| * Above 96 rows, compute() factors a dynamic-size matrix in blocks, and the matrix products of the blocked | |
| * factorization can allocate their packing buffers, as those of LLT and PartialPivLU do. Fixed-size and bounded | |
| * matrices are factored unblocked and allocate nothing. | |
| * \sa LDLT() | |
| */ | |
| explicit LDLT(Index size) | |
| : m_matrix(size, size), | |
| m_l1_norm(0), | |
| m_transpositions(size), | |
| m_temporary(size), | |
| // The shape compute() gives the panel workspace, so that it does not reallocate it for this size. | |
| m_workspace(size, internal::ldlt_blocksize<MatrixType>(size)), | |
| m_sign(internal::ZeroSign), | |
| m_isInitialized(false), | |
| m_info(InvalidInput) {} | |
| /** \brief Constructor with decomposition | |
| * | |
| * This calculates the decomposition for the input \a matrix. | |
| * | |
| * \sa LDLT(Index size) | |
| */ | |
| template <typename InputType> | |
| explicit LDLT(const EigenBase<InputType>& matrix) | |
| : m_matrix(matrix.rows(), matrix.cols()), | |
| m_l1_norm(0), | |
| m_transpositions(matrix.rows()), | |
| m_temporary(matrix.rows()), | |
| m_sign(internal::ZeroSign), | |
| m_isInitialized(false), | |
| m_info(InvalidInput) { | |
| compute(matrix.derived()); | |
| } | |
| /** \brief Constructs a LDLT factorization from a given matrix | |
| * | |
| * This overloaded constructor is provided for \link InplaceDecomposition inplace decomposition \endlink when \c | |
| * MatrixType is a Eigen::Ref. | |
| * | |
| * \sa LDLT(const EigenBase&) | |
| */ | |
| template <typename InputType> | |
| explicit LDLT(EigenBase<InputType>& matrix) | |
| : m_matrix(matrix.derived()), | |
| m_l1_norm(0), | |
| m_transpositions(matrix.rows()), | |
| m_temporary(matrix.rows()), | |
| m_sign(internal::ZeroSign), | |
| m_isInitialized(false), | |
| m_info(InvalidInput) { | |
| compute(matrix.derived()); | |
| } | |
| /** Clear any existing decomposition | |
| * \sa rankUpdate(w,sigma) | |
| */ | |
| void setZero() { m_isInitialized = false; } | |
| /** \returns a view of the upper triangular matrix U */ | |
| inline typename Traits::MatrixU matrixU() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return Traits::getU(m_matrix); | |
| } | |
| /** \returns a view of the lower triangular matrix L */ | |
| inline typename Traits::MatrixL matrixL() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return Traits::getL(m_matrix); | |
| } | |
| /** \returns the permutation matrix P as a transposition sequence. | |
| */ | |
| inline const TranspositionType& transpositionsP() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_transpositions; | |
| } | |
| /** \returns the coefficients of the diagonal matrix D */ | |
| inline Diagonal<const MatrixType> vectorD() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_matrix.diagonal(); | |
| } | |
| /** \returns true if the matrix is positive (semidefinite) */ | |
| inline bool isPositive() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_sign == internal::PositiveSemiDef || m_sign == internal::ZeroSign; | |
| } | |
| /** \returns true if the matrix is negative (semidefinite) */ | |
| inline bool isNegative(void) const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_sign == internal::NegativeSemiDef || m_sign == internal::ZeroSign; | |
| } | |
| #ifdef EIGEN_PARSED_BY_DOXYGEN | |
| /** \returns a solution x of \f$ A x = b \f$ using the current decomposition of A. | |
| * | |
| * This function also supports in-place solves using the syntax <tt>x = decompositionObject.solve(x)</tt> . | |
| * | |
| * \note_about_checking_solutions | |
| * | |
| * More precisely, this method solves \f$ A x = b \f$ using the decomposition \f$ A = P^T L D L^* P \f$ | |
| * by solving the systems \f$ P^T y_1 = b \f$, \f$ L y_2 = y_1 \f$, \f$ D y_3 = y_2 \f$, | |
| * \f$ L^* y_4 = y_3 \f$ and \f$ P x = y_4 \f$ in succession. If the matrix \f$ A \f$ is singular, then | |
| * \f$ D \f$ will also be singular (all the other matrices are invertible). In that case, the | |
| * least-square solution of \f$ D y_3 = y_2 \f$ is computed. This does not mean that this function | |
| * computes the least-square solution of \f$ A x = b \f$ if \f$ A \f$ is singular. | |
| * | |
| * \sa MatrixBase::ldlt(), SelfAdjointView::ldlt() | |
| */ | |
| template <typename Rhs> | |
| inline Solve<LDLT, Rhs> solve(const MatrixBase<Rhs>& b) const; | |
| #endif | |
| template <typename Derived> | |
| bool solveInPlace(MatrixBase<Derived>& bAndX) const; | |
| template <typename InputType> | |
| LDLT& compute(const EigenBase<InputType>& matrix); | |
| /** \returns an estimate of the reciprocal condition number of the matrix of | |
| * which \c *this is the LDLT decomposition. | |
| */ | |
| RealScalar rcond() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return internal::rcond_estimate_helper(m_l1_norm, *this); | |
| } | |
| template <typename Derived> | |
| LDLT& rankUpdate(const MatrixBase<Derived>& w, const RealScalar& alpha = 1); | |
| /** \returns the determinant of the matrix of which *this is the Cholesky decomposition. | |
| * | |
| * It has only linear complexity (that is, O(n) where n is the dimension of the square matrix) | |
| * as the Cholesky decomposition has already been computed. | |
| * | |
| * \warning a determinant can be very big or small, so for matrices | |
| * of large enough dimension, there is a risk of overflow/underflow. | |
| * One way to work around that is to use logAbsDeterminant() and signDeterminant() instead. | |
| * Also, do not rely on the determinant being exactly zero for testing | |
| * singularity or rank-deficiency. | |
| * | |
| * \pre info() returns \c Success. A failed factorization does not represent the input matrix. | |
| * | |
| * \sa absDeterminant(), logAbsDeterminant(), signDeterminant(), MatrixBase::determinant() | |
| */ | |
| Scalar determinant() const; | |
| /** \returns the absolute value of the determinant of the matrix of which *this is the Cholesky decomposition. | |
| * | |
| * It has only linear complexity (that is, O(n) where n is the dimension of the square matrix) | |
| * as the Cholesky decomposition has already been computed. | |
| * | |
| * \warning a determinant can be very big or small, so for matrices | |
| * of large enough dimension, there is a risk of overflow/underflow. | |
| * One way to work around that is to use logAbsDeterminant() instead. | |
| * | |
| * \pre info() returns \c Success. A failed factorization does not represent the input matrix. | |
| * | |
| * \sa determinant(), logAbsDeterminant(), signDeterminant(), MatrixBase::determinant() | |
| */ | |
| RealScalar absDeterminant() const; | |
| /** \returns the natural log of the absolute value of the determinant of the matrix of which *this is the Cholesky | |
| * decomposition. | |
| * | |
| * It has only linear complexity (that is, O(n) where n is the dimension of the square matrix) | |
| * as the Cholesky decomposition has already been computed. | |
| * | |
| * \note This method is useful to work around the risk of overflow/underflow that's inherent | |
| * to determinant computation. | |
| * | |
| * \pre info() returns \c Success. A failed factorization does not represent the input matrix. | |
| * | |
| * \sa determinant(), absDeterminant(), signDeterminant(), MatrixBase::determinant() | |
| */ | |
| RealScalar logAbsDeterminant() const; | |
| /** \returns the sign of the determinant of the matrix of which *this is the Cholesky decomposition, | |
| * that is, \c 1, \c -1, or \c 0 if the matrix is singular. | |
| * | |
| * It has only linear complexity (that is, O(n) where n is the dimension of the square matrix) | |
| * as the Cholesky decomposition has already been computed. | |
| * | |
| * \pre info() returns \c Success. A failed factorization does not represent the input matrix. | |
| * | |
| * \sa determinant(), absDeterminant(), logAbsDeterminant(), MatrixBase::determinant() | |
| */ | |
| Scalar signDeterminant() const; | |
| /** \returns the internal LDLT decomposition matrix | |
| * | |
| * TODO: document the storage layout. | |
| */ | |
| inline const MatrixType& matrixLDLT() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_matrix; | |
| } | |
| MatrixType reconstructedMatrix() const; | |
| /** \returns the adjoint of \c *this, that is, a const reference to the decomposition itself as the underlying matrix | |
| * is self-adjoint. | |
| * | |
| * This method is provided for compatibility with other matrix decompositions, thus enabling generic code such as: | |
| * \code x = decomposition.adjoint().solve(b) \endcode | |
| */ | |
| const LDLT& adjoint() const { return *this; } | |
| EIGEN_DEVICE_FUNC constexpr Index rows() const noexcept { return m_matrix.rows(); } | |
| EIGEN_DEVICE_FUNC constexpr Index cols() const noexcept { return m_matrix.cols(); } | |
| /** \brief Reports whether previous computation was successful. | |
| * | |
| * \returns \c Success if computation was successful, | |
| * \c NumericalIssue if the factorization failed: a pivot is not finite, or is zero above a | |
| * non-zero column. In exact arithmetic only an indefinite matrix has the latter, but rounding | |
| * errors can give it to a singular semidefinite matrix too. | |
| */ | |
| ComputationInfo info() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| return m_info; | |
| } | |
| #ifndef EIGEN_PARSED_BY_DOXYGEN | |
| template <typename RhsType, typename DstType> | |
| void _solve_impl(const RhsType& rhs, DstType& dst) const; | |
| template <bool Conjugate, typename RhsType, typename DstType> | |
| void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const; | |
| #endif | |
| protected: | |
| EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar) | |
| /** \internal | |
| * Used to compute and store the Cholesky decomposition A = L D L^* = U^* D U. | |
| * The strict upper part is used during the decomposition, the strict lower | |
| * part correspond to the coefficients of L (its diagonal is equal to 1 and | |
| * is not stored), and the diagonal entries correspond to D. | |
| */ | |
| MatrixType m_matrix; | |
| RealScalar m_l1_norm; | |
| TranspositionType m_transpositions; | |
| TmpMatrixType m_temporary; | |
| // L21 D for the trailing update of the blocked factorization; it stays empty below the blocking threshold. | |
| Matrix<Scalar, Dynamic, Dynamic> m_workspace; | |
| internal::SignMatrix m_sign; | |
| bool m_isInitialized; | |
| ComputationInfo m_info; | |
| }; | |
| namespace internal { | |
| /** \internal Panel width of the blocked factorization of a \a size x \a size matrix, or 0 where a single | |
| * unblocked panel covers the whole matrix: up to three panel widths, below which the level-3 update does not pay | |
| * off, and for fixed-size or bounded matrices, which must not allocate the panel workspace. | |
| * | |
| * The panel's level-2 updates run at a rate R, and the trailing update at P / (1 + kappa / nb), kappa being the | |
| * fixed cost of a pass in steps of its depth. Then T(nb) = n^3 / (3 P) (1 + kappa / nb) + n^2 nb / (2 R) is least at | |
| * nb = sqrt(c n), c = 2 kappa R / (3 P). Measured c ranges from about 0.7 to 4 with AVX2, AVX-512, NEON and SME | |
| * products, and grows once the trailing matrix outgrows the last-level cache. c = 3, with nb rounded to a multiple | |
| * of 16 and clamped to [32, 128], the range the measured optimum spans, loses about 2% to the best width on average. | |
| * Can be overridden (mainly for testing the panel logic at small sizes) by defining EIGEN_LDLT_BLOCKSIZE. */ | |
| template <typename MatrixType> | |
| inline Index ldlt_blocksize(Index size) { | |
| if (int(MatrixType::MaxRowsAtCompileTime) != Dynamic || int(MatrixType::MaxColsAtCompileTime) != Dynamic) return 0; | |
| #ifdef EIGEN_LDLT_BLOCKSIZE | |
| const Index nb = Index(EIGEN_LDLT_BLOCKSIZE); | |
| #else | |
| constexpr Index kMinBlockSize = 32; | |
| // Three of the narrowest panels are not blocked either, so small matrices skip the square root. | |
| if (size <= 3 * kMinBlockSize) return 0; | |
| const Index unclamped = 16 * Index(numext::round(numext::sqrt(3.0 * double(size)) / 16)); | |
| const Index nb = numext::mini(numext::maxi(unclamped, kMinBlockSize), Index(128)); | |
| #endif | |
| return nb > 0 && size > 3 * nb ? nb : 0; | |
| } | |
| template <int UpLo> | |
| struct ldlt_inplace; | |
| template <> | |
| struct ldlt_inplace<Lower> { | |
| // Settles the cases that leave nothing to factor, and returns whether it did: an empty or 1x1 matrix, and a | |
| // diagonal that is entirely zero, which offers no pivot and leaves the matrix either zero or indefinite. Otherwise | |
| // it copies the diagonal into temp, where factor_panel() expects it. | |
| template <typename MatrixType, typename TranspositionType, typename Workspace> | |
| static bool factor_trivial(const MatrixType& mat, TranspositionType& transpositions, Workspace& temp, | |
| SignMatrix& sign, bool& ret) { | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| const Index size = mat.rows(); | |
| if (size <= 1) { | |
| transpositions.setIdentity(); | |
| if (size == 0) | |
| sign = ZeroSign; | |
| else if (numext::real(mat.coeff(0, 0)) > static_cast<RealScalar>(0)) | |
| sign = PositiveSemiDef; | |
| else if (numext::real(mat.coeff(0, 0)) < static_cast<RealScalar>(0)) | |
| sign = NegativeSemiDef; | |
| else | |
| sign = ZeroSign; | |
| ret = size == 0 || (numext::isfinite)(numext::real(mat.coeff(0, 0))); | |
| return true; | |
| } | |
| temp = mat.diagonal().real().template cast<Scalar>(); | |
| if ((temp.array() == Scalar(0)).all()) { | |
| transpositions.setIdentity(); | |
| sign = ZeroSign; | |
| ret = true; | |
| for (Index j = 0; ret && j < size; ++j) ret = (mat.col(j).tail(size - j - 1).array() == Scalar(0)).all(); | |
| return true; | |
| } | |
| return false; | |
| } | |
| // Factors columns [k0, k0 + kb) left-looking, column k pivoting on max |diag(S_k)|, S_k = A22 - L21 D L21^* | |
| // (complete diagonal pivoting, as in LAPACK's xPSTF2). Invariant: mat(k0:n, k0:n) holds S_k0 off its diagonal and | |
| // temp(k:n) holds diag(S_k). The caller interchanges the rows of the columns before k0. | |
| template <typename MatrixType, typename TranspositionType, typename Workspace> | |
| static bool factor_panel(MatrixType& mat, Index k0, Index kb, TranspositionType& transpositions, Workspace& temp, | |
| SignMatrix& sign) { | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| using IndexType = typename TranspositionType::StorageIndex; | |
| const Index size = mat.rows(); | |
| bool ret = true; | |
| for (Index k = k0; k < k0 + kb; ++k) { | |
| // Find largest diagonal element | |
| Index index_of_biggest_in_corner; | |
| temp.tail(size - k).real().cwiseAbs().maxCoeff(&index_of_biggest_in_corner); | |
| index_of_biggest_in_corner += k; | |
| transpositions.coeffRef(k) = IndexType(index_of_biggest_in_corner); | |
| if (k != index_of_biggest_in_corner) { | |
| auto trailing = mat.bottomRightCorner(size - k0, size - k0); | |
| selfadjoint_swap_lower(trailing, k - k0, index_of_biggest_in_corner - k0); | |
| numext::swap(temp.coeffRef(k), temp.coeffRef(index_of_biggest_in_corner)); | |
| } | |
| // partition the matrix: | |
| // A00 | - | - | |
| // lu = A10 | A11 | - | |
| // A20 | A21 | A22 | |
| // where A10 and A20 span the panel columns [k0, k); those before k0 are already applied to A21. The | |
| // product's operand D A10^* takes temp(k0:k), whose diagonal entries of S have all been used as pivots. | |
| Index rs = size - k - 1; | |
| Index done = k - k0; | |
| auto A21 = mat.block(k + 1, k, rs, fix<1>); | |
| if (done > 0 && rs > 0) { | |
| auto A10 = mat.block(k, k0, fix<1>, done); | |
| auto A20 = mat.block(k + 1, k0, rs, done); | |
| temp.segment(k0, done) = mat.diagonal().real().segment(k0, done).asDiagonal() * A10.adjoint(); | |
| A21.noalias() -= A20 * temp.segment(k0, done); | |
| } | |
| // In some previous versions of Eigen (e.g., 3.2.1), the scaling was omitted if the pivot | |
| // was smaller than the cutoff value. However, since LDLT is not rank-revealing | |
| // we should only make sure that we do not introduce INF or NaN values. | |
| // Remark that LAPACK also uses 0 as the cutoff value. | |
| RealScalar realAkk = numext::real(temp.coeff(k)); | |
| mat.coeffRef(k, k) = Scalar(realAkk); | |
| bool pivot_is_valid = (numext::abs(realAkk) > RealScalar(0)); | |
| if (!(numext::isfinite)(realAkk)) ret = false; | |
| // A zero pivot is the largest remaining, so the rest of D is zero too, and its column must be zero as well. | |
| if ((rs > 0) && pivot_is_valid) { | |
| A21 /= realAkk; | |
| // diag(S_{k+1}) = diag(S_k) - conj(L21) .* (D_k L21), where the next pivot is searched for. Squaring L21 | |
| // first would underflow for |L21| < sqrt(min) on a graded matrix, where D_k |L21|^2 is representable. | |
| temp.tail(rs).real() -= A21.conjugate().cwiseProduct(realAkk * A21).real(); | |
| } else if (rs > 0) { | |
| ret = ret && (A21.array() == Scalar(0)).all(); | |
| } | |
| if (sign == PositiveSemiDef) { | |
| if (realAkk < static_cast<RealScalar>(0)) sign = Indefinite; | |
| } else if (sign == NegativeSemiDef) { | |
| if (realAkk > static_cast<RealScalar>(0)) sign = Indefinite; | |
| } else if (sign == ZeroSign) { | |
| if (realAkk > static_cast<RealScalar>(0)) | |
| sign = PositiveSemiDef; | |
| else if (realAkk < static_cast<RealScalar>(0)) | |
| sign = NegativeSemiDef; | |
| } | |
| } | |
| return ret; | |
| } | |
| template <typename MatrixType, typename TranspositionType, typename Workspace> | |
| static bool unblocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, SignMatrix& sign) { | |
| EIGEN_INTERNAL_ASSERT_SQUARE(mat); | |
| bool ret = true; | |
| if (factor_trivial(mat, transpositions, temp, sign, ret)) return ret; | |
| return factor_panel(mat, 0, mat.rows(), transpositions, temp, sign); | |
| } | |
| // Blocked (level-3) variant, with the panel/trailing-update structure of LAPACK's xPSTRF: each panel is factored | |
| // by factor_panel(), then a single product applies it to the trailing Schur complement, A22 -= L21 D L21^*. | |
| template <typename MatrixType, typename TranspositionType, typename Workspace, typename BlockWorkspace> | |
| static bool blocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, BlockWorkspace& workspace, | |
| SignMatrix& sign) { | |
| EIGEN_INTERNAL_ASSERT_SQUARE(mat); | |
| const Index size = mat.rows(); | |
| const Index nb = ldlt_blocksize<MatrixType>(size); | |
| if (nb == 0) return unblocked(mat, transpositions, temp, sign); | |
| bool ret = true; | |
| if (factor_trivial(mat, transpositions, temp, sign, ret)) return ret; | |
| workspace.resize(size, nb); | |
| for (Index k0 = 0; k0 < size; k0 += nb) { | |
| const Index kb = numext::mini(nb, size - k0); | |
| const Index k1 = k0 + kb; | |
| if (!factor_panel(mat, k0, kb, transpositions, temp, sign)) ret = false; | |
| // The panel's interchanges, applied to the rows of the columns before it. Column-major storage takes them a | |
| // column at a time, where a row swap would stride through memory. | |
| EIGEN_IF_CONSTEXPR (MatrixType::IsRowMajor) { | |
| for (Index k = k0; k < k1; ++k) { | |
| const Index p = transpositions.coeff(k); | |
| if (p != k) mat.row(k).head(k0).swap(mat.row(p).head(k0)); | |
| } | |
| } else { | |
| for (Index c = 0; c < k0; ++c) { | |
| for (Index k = k0; k < k1; ++k) { | |
| const Index p = transpositions.coeff(k); | |
| if (p != k) numext::swap(mat.coeffRef(k, c), mat.coeffRef(p, c)); | |
| } | |
| } | |
| } | |
| const Index rs = size - k1; | |
| if (rs > 0) { | |
| auto L21 = mat.block(k1, k0, rs, kb); | |
| auto W = workspace.topLeftCorner(rs, kb); | |
| W.noalias() = L21 * mat.diagonal().real().segment(k0, kb).asDiagonal(); | |
| mat.block(k1, k1, rs, rs).template triangularView<Lower>() -= L21 * W.adjoint(); | |
| } | |
| } | |
| return ret; | |
| } | |
| // Reference for the algorithm: Davis and Hager, "Multiple Rank | |
| // Modifications of a Sparse Cholesky Factorization" (Algorithm 1) | |
| // Trivial rearrangements of their computations (Timothy E. Holy) | |
| // allow their algorithm to work for rank-1 updates even if the | |
| // original matrix is not of full rank. | |
| // Here only rank-1 updates are implemented, to reduce the | |
| // requirement for intermediate storage and improve accuracy | |
| template <typename MatrixType, typename WDerived> | |
| static bool updateInPlace(MatrixType& mat, MatrixBase<WDerived>& w, | |
| const typename MatrixType::RealScalar& sigma = 1) { | |
| using numext::isfinite; | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| const Index size = mat.rows(); | |
| EIGEN_INTERNAL_ASSERT_SQUARE(mat); | |
| EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_ROWS(w, mat); | |
| RealScalar alpha = 1; | |
| // Apply the update | |
| for (Index j = 0; j < size; j++) { | |
| // Check for termination due to an original decomposition of low-rank | |
| if (!(isfinite)(alpha)) break; | |
| // Update the diagonal terms | |
| RealScalar dj = numext::real(mat.coeff(j, j)); | |
| Scalar wj = w.coeff(j); | |
| RealScalar swj2 = sigma * numext::abs2(wj); | |
| RealScalar gamma = dj * alpha + swj2; | |
| // A zero contribution leaves both quantities unchanged, but spelling that out as an addition of swj2/alpha and | |
| // swj2/dj evaluates 0/0 when alpha or the pivot is zero. The resulting NaN reaches the termination test above | |
| // on the next iteration, which reads it as a low-rank signal and abandons the remainder of the update. Skip the | |
| // no-op instead. A zero pivot with a nonzero contribution still yields an infinite alpha, so genuine low-rank | |
| // termination is unaffected. | |
| if (!numext::is_exactly_zero(swj2)) { | |
| mat.coeffRef(j, j) += swj2 / alpha; | |
| alpha += swj2 / dj; | |
| } | |
| // Update the terms of L | |
| Index rs = size - j - 1; | |
| w.tail(rs) -= wj * mat.col(j).tail(rs); | |
| if (!numext::is_exactly_zero(gamma)) mat.col(j).tail(rs) += (sigma * numext::conj(wj) / gamma) * w.tail(rs); | |
| } | |
| return true; | |
| } | |
| template <typename MatrixType, typename TranspositionType, typename Workspace, typename WType> | |
| static bool update(MatrixType& mat, const TranspositionType& transpositions, Workspace& tmp, const WType& w, | |
| const typename MatrixType::RealScalar& sigma = 1) { | |
| // Apply the permutation to the input w | |
| tmp = transpositions * w; | |
| return ldlt_inplace<Lower>::updateInPlace(mat, tmp, sigma); | |
| } | |
| }; | |
| template <> | |
| struct ldlt_inplace<Upper> { | |
| template <typename MatrixType, typename TranspositionType, typename Workspace> | |
| static EIGEN_STRONG_INLINE bool unblocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, | |
| SignMatrix& sign) { | |
| Transpose<MatrixType> matt(mat); | |
| return ldlt_inplace<Lower>::unblocked(matt, transpositions, temp, sign); | |
| } | |
| template <typename MatrixType, typename TranspositionType, typename Workspace, typename BlockWorkspace> | |
| static EIGEN_STRONG_INLINE bool blocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, | |
| BlockWorkspace& workspace, SignMatrix& sign) { | |
| Transpose<MatrixType> matt(mat); | |
| return ldlt_inplace<Lower>::blocked(matt, transpositions, temp, workspace, sign); | |
| } | |
| template <typename MatrixType, typename TranspositionType, typename Workspace, typename WType> | |
| static EIGEN_STRONG_INLINE bool update(MatrixType& mat, TranspositionType& transpositions, Workspace& tmp, WType& w, | |
| const typename MatrixType::RealScalar& sigma = 1) { | |
| Transpose<MatrixType> matt(mat); | |
| return ldlt_inplace<Lower>::update(matt, transpositions, tmp, w.conjugate(), sigma); | |
| } | |
| }; | |
| template <typename MatrixType> | |
| struct LDLT_Traits<MatrixType, Lower> { | |
| using MatrixL = const TriangularView<const MatrixType, UnitLower>; | |
| using MatrixU = const TriangularView<const typename MatrixType::AdjointReturnType, UnitUpper>; | |
| static inline MatrixL getL(const MatrixType& m) { return MatrixL(m); } | |
| static inline MatrixU getU(const MatrixType& m) { return MatrixU(m.adjoint()); } | |
| }; | |
| template <typename MatrixType> | |
| struct LDLT_Traits<MatrixType, Upper> { | |
| using MatrixL = const TriangularView<const typename MatrixType::AdjointReturnType, UnitLower>; | |
| using MatrixU = const TriangularView<const MatrixType, UnitUpper>; | |
| static inline MatrixL getL(const MatrixType& m) { return MatrixL(m.adjoint()); } | |
| static inline MatrixU getU(const MatrixType& m) { return MatrixU(m); } | |
| }; | |
| } // end namespace internal | |
| /** Compute / recompute the LDLT decomposition A = L D L^* = U^* D U of \a matrix | |
| */ | |
| template <typename MatrixType, int UpLo_> | |
| template <typename InputType> | |
| LDLT<MatrixType, UpLo_>& LDLT<MatrixType, UpLo_>::compute(const EigenBase<InputType>& a) { | |
| EIGEN_INTERNAL_ASSERT_SQUARE(a); | |
| const Index size = a.rows(); | |
| m_matrix = a.derived(); | |
| // Compute matrix L1 norm = max abs column sum over the implicit self-adjoint matrix. | |
| m_l1_norm = m_matrix.template selfadjointView<UpLo_>().l1Norm(); | |
| m_transpositions.resize(size); | |
| m_isInitialized = false; | |
| m_temporary.resize(size); | |
| m_sign = internal::ZeroSign; | |
| m_info = internal::ldlt_inplace<UpLo>::blocked(m_matrix, m_transpositions, m_temporary, m_workspace, m_sign) | |
| ? Success | |
| : NumericalIssue; | |
| m_isInitialized = true; | |
| return *this; | |
| } | |
| /** Update the LDLT decomposition: given a decomposition of \f$ A = P^TLDL^*P \f$, efficiently compute the | |
| * decomposition of \f$ A + \sigma w w^* \f$. | |
| * | |
| * If \c *this holds no factorization yet, A is taken to be zero and the decomposition is built from scratch; info() | |
| * then reports \c Success. An update applied to an existing factorization leaves info() unchanged, so a | |
| * \c NumericalIssue already reported for that factorization stands until compute() replaces it or setZero() discards | |
| * it. LLT::rankUpdate() differs on both counts: it requires an existing factorization and re-reports the status on | |
| * every call. | |
| * | |
| * \note rcond(), isPositive() and isNegative() are not maintained across rank updates. rcond() keeps using the L1 | |
| * norm recorded by the last compute(), which is zero when there was none, and the definiteness flags are assigned | |
| * only where this function builds a factorization from scratch, from the sign of \a sigma alone. | |
| * | |
| * \param w a vector to be incorporated into the decomposition. | |
| * \param sigma a scalar, +1 for updates and -1 for "downdates," which correspond to removing previously-added column | |
| * vectors. Optional; default value is +1. | |
| * | |
| * \sa setZero() | |
| */ | |
| template <typename MatrixType, int UpLo_> | |
| template <typename Derived> | |
| LDLT<MatrixType, UpLo_>& LDLT<MatrixType, UpLo_>::rankUpdate( | |
| const MatrixBase<Derived>& w, const typename LDLT<MatrixType, UpLo_>::RealScalar& sigma) { | |
| using IndexType = typename TranspositionType::StorageIndex; | |
| const Index size = w.rows(); | |
| if (m_isInitialized) { | |
| EIGEN_INTERNAL_ASSERT_SAME_ROWS(m_matrix, w); | |
| } else { | |
| m_matrix.resize(size, size); | |
| m_matrix.setZero(); | |
| m_transpositions.resize(size); | |
| for (Index i = 0; i < size; i++) m_transpositions.coeffRef(i) = IndexType(i); | |
| m_temporary.resize(size); | |
| m_sign = sigma >= 0 ? internal::PositiveSemiDef : internal::NegativeSemiDef; | |
| m_isInitialized = true; | |
| // Assigned here rather than after the branch: updating an existing factorization keeps the status it already has. | |
| m_info = Success; | |
| } | |
| internal::ldlt_inplace<UpLo>::update(m_matrix, m_transpositions, m_temporary, w, sigma); | |
| return *this; | |
| } | |
| // A = P^T L D L^* P with L unit lower triangular and D real diagonal, so det(A) = prod(D_ii). | |
| template <typename MatrixType_, int UpLo_> | |
| typename LDLT<MatrixType_, UpLo_>::Scalar LDLT<MatrixType_, UpLo_>::determinant() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| eigen_assert(m_info == Success && "LDLT failed because of a zero pivot."); | |
| return Scalar(vectorD().real().prod()); | |
| } | |
| template <typename MatrixType_, int UpLo_> | |
| typename LDLT<MatrixType_, UpLo_>::RealScalar LDLT<MatrixType_, UpLo_>::absDeterminant() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| eigen_assert(m_info == Success && "LDLT failed because of a zero pivot."); | |
| return numext::abs(vectorD().real().prod()); | |
| } | |
| template <typename MatrixType_, int UpLo_> | |
| typename LDLT<MatrixType_, UpLo_>::RealScalar LDLT<MatrixType_, UpLo_>::logAbsDeterminant() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| eigen_assert(m_info == Success && "LDLT failed because of a zero pivot."); | |
| return vectorD().real().cwiseAbs().array().log().sum(); | |
| } | |
| template <typename MatrixType_, int UpLo_> | |
| typename LDLT<MatrixType_, UpLo_>::Scalar LDLT<MatrixType_, UpLo_>::signDeterminant() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| eigen_assert(m_info == Success && "LDLT failed because of a zero pivot."); | |
| return Scalar(vectorD().real().array().sign().prod()); | |
| } | |
| #ifndef EIGEN_PARSED_BY_DOXYGEN | |
| template <typename MatrixType_, int UpLo_> | |
| template <typename RhsType, typename DstType> | |
| void LDLT<MatrixType_, UpLo_>::_solve_impl(const RhsType& rhs, DstType& dst) const { | |
| _solve_impl_transposed<true>(rhs, dst); | |
| } | |
| template <typename MatrixType_, int UpLo_> | |
| template <bool Conjugate, typename RhsType, typename DstType> | |
| void LDLT<MatrixType_, UpLo_>::_solve_impl_transposed(const RhsType& rhs, DstType& dst) const { | |
| // dst = P b | |
| dst = m_transpositions * rhs; | |
| // dst = L^-1 (P b) | |
| // dst = L^-*T (P b) | |
| matrixL().template conjugateIf<!Conjugate>().solveInPlace(dst); | |
| // dst = D^-* (L^-1 P b) | |
| // dst = D^-1 (L^-*T P b) | |
| // more precisely, use pseudo-inverse of D (see bug 241) | |
| using std::abs; | |
| const typename Diagonal<const MatrixType>::RealReturnType vecD(vectorD()); | |
| // In some previous versions, tolerance was set to the max of 1/highest (or rather numeric_limits::min()) | |
| // and the maximal diagonal entry * epsilon as motivated by LAPACK's xGELSS: | |
| // RealScalar tolerance = numext::maxi(vecD.array().abs().maxCoeff() * NumTraits<RealScalar>::epsilon(),RealScalar(1) | |
| // / NumTraits<RealScalar>::highest()); However, LDLT is not rank revealing, and so adjusting the tolerance wrt to the | |
| // highest diagonal element is not well justified and leads to numerical issues in some cases. Moreover, Lapack's | |
| // xSYTRS routines use 0 for the tolerance. Using numeric_limits::min() gives us more robustness to denormals. | |
| RealScalar tolerance = (std::numeric_limits<RealScalar>::min)(); | |
| for (Index i = 0; i < vecD.size(); ++i) { | |
| if (abs(vecD(i)) > tolerance) | |
| dst.row(i) /= vecD(i); | |
| else | |
| dst.row(i).setZero(); | |
| } | |
| // dst = L^-* (D^-* L^-1 P b) | |
| // dst = L^-T (D^-1 L^-*T P b) | |
| matrixL().transpose().template conjugateIf<Conjugate>().solveInPlace(dst); | |
| // dst = P^T (L^-* D^-* L^-1 P b) = A^-1 b | |
| // dst = P^-T (L^-T D^-1 L^-*T P b) = A^-1 b | |
| dst = m_transpositions.transpose() * dst; | |
| } | |
| #endif | |
| /** \internal use x = ldlt_object.solve(x); | |
| * | |
| * This is the \em in-place version of solve(). | |
| * | |
| * \param bAndX represents both the right-hand side matrix b and result x. | |
| * | |
| * \returns true always! If you need to check for existence of solutions, use another decomposition like LU, QR, or SVD. | |
| * | |
| * This version avoids a copy when the right hand side matrix b is not | |
| * needed anymore. | |
| * | |
| * \sa LDLT::solve(), MatrixBase::ldlt() | |
| */ | |
| template <typename MatrixType, int UpLo_> | |
| template <typename Derived> | |
| bool LDLT<MatrixType, UpLo_>::solveInPlace(MatrixBase<Derived>& bAndX) const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| EIGEN_INTERNAL_ASSERT_SAME_ROWS(m_matrix, bAndX); | |
| bAndX = this->solve(bAndX); | |
| return true; | |
| } | |
| /** \returns the matrix represented by the decomposition, | |
| * i.e., it returns the product: P^T L D L^* P. | |
| * This function is provided for debug purpose. */ | |
| template <typename MatrixType, int UpLo_> | |
| MatrixType LDLT<MatrixType, UpLo_>::reconstructedMatrix() const { | |
| eigen_assert(m_isInitialized && "LDLT is not initialized."); | |
| MatrixType res = matrixU(); | |
| res = vectorD().real().asDiagonal() * res; | |
| res = matrixL() * res; | |
| // P^T (L D L^*) P; the stored pivots cannot alias the new result. | |
| auto lower_triangle = res.template selfadjointView<Lower>(); | |
| for (Index k = m_matrix.rows() - 1; k >= 0; --k) lower_triangle.applyTransposition(k, m_transpositions.coeff(k)); | |
| res.template triangularView<StrictlyUpper>() = res.adjoint(); | |
| return res; | |
| } | |
| /** \cholesky_module | |
| * \returns the Cholesky decomposition with full pivoting without square root of \c *this | |
| * \sa MatrixBase::ldlt() | |
| */ | |
| template <typename MatrixType, unsigned int UpLo> | |
| inline LDLT<typename SelfAdjointView<MatrixType, UpLo>::PlainObject, UpLo> SelfAdjointView<MatrixType, UpLo>::ldlt() | |
| const { | |
| return LDLT<PlainObject, UpLo>(m_matrix); | |
| } | |
| /** \cholesky_module | |
| * \returns the Cholesky decomposition with full pivoting without square root of \c *this | |
| * \sa SelfAdjointView::ldlt() | |
| */ | |
| template <typename Derived> | |
| inline LDLT<typename MatrixBase<Derived>::PlainObject> MatrixBase<Derived>::ldlt() const { | |
| return LDLT<PlainObject>(derived()); | |
| } | |
| } // end namespace Eigen | |
| #endif // EIGEN_LDLT_H |