Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
LDLT.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2011 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2009 Keir Mierle <mierle@gmail.com>
6// Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com>
7// Copyright (C) 2011 Timothy E. Holy <tim.holy@gmail.com >
8//
9// This Source Code Form is subject to the terms of the Mozilla
10// Public License v. 2.0. If a copy of the MPL was not distributed
11// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
12// SPDX-License-Identifier: MPL-2.0
13
14#ifndef EIGEN_LDLT_H
15#define EIGEN_LDLT_H
16
17// IWYU pragma: private
18#include "./InternalHeaderCheck.h"
19
20namespace Eigen {
21
22namespace internal {
23template <typename MatrixType_, int UpLo_>
24struct traits<LDLT<MatrixType_, UpLo_> > : traits<MatrixType_> {
25 using XprKind = MatrixXpr;
26 using StorageKind = SolverStorage;
27 using StorageIndex = int;
28 enum { Flags = 0 };
29};
30
31template <typename MatrixType, int UpLo>
32struct LDLT_Traits;
33
34// PositiveSemiDef means positive semi-definite and non-zero; same for NegativeSemiDef
35enum SignMatrix { PositiveSemiDef, NegativeSemiDef, ZeroSign, Indefinite };
36
37// Panel width of the blocked factorization (defined below); declared here for the size constructor.
38template <typename MatrixType>
39inline Index ldlt_blocksize(Index size);
40} // namespace internal
41
74template <typename MatrixType_, int UpLo_>
75class LDLT : public SolverBase<LDLT<MatrixType_, UpLo_> > {
76 public:
77 using MatrixType = MatrixType_;
78 using Base = SolverBase<LDLT>;
79 friend class SolverBase<LDLT>;
80
81 EIGEN_GENERIC_PUBLIC_INTERFACE(LDLT)
82 enum {
83 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
84 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime,
85 UpLo = UpLo_
86 };
88
91
92 using Traits = internal::LDLT_Traits<MatrixType, UpLo>;
93
100 : m_matrix(),
101 m_l1_norm(0),
102 m_transpositions(),
103 m_sign(internal::ZeroSign),
104 m_isInitialized(false),
105 m_info(InvalidInput) {}
106
117 explicit LDLT(Index size)
118 : m_matrix(size, size),
119 m_l1_norm(0),
120 m_transpositions(size),
121 m_temporary(size),
122 // The shape compute() gives the panel workspace, so that it does not reallocate it for this size.
123 m_workspace(size, internal::ldlt_blocksize<MatrixType>(size)),
124 m_sign(internal::ZeroSign),
125 m_isInitialized(false),
126 m_info(InvalidInput) {}
127
134 template <typename InputType>
135 explicit LDLT(const EigenBase<InputType>& matrix)
136 : m_matrix(matrix.rows(), matrix.cols()),
137 m_l1_norm(0),
138 m_transpositions(matrix.rows()),
139 m_temporary(matrix.rows()),
140 m_sign(internal::ZeroSign),
141 m_isInitialized(false),
142 m_info(InvalidInput) {
143 compute(matrix.derived());
144 }
145
153 template <typename InputType>
154 explicit LDLT(EigenBase<InputType>& matrix)
155 : m_matrix(matrix.derived()),
156 m_l1_norm(0),
157 m_transpositions(matrix.rows()),
158 m_temporary(matrix.rows()),
159 m_sign(internal::ZeroSign),
160 m_isInitialized(false),
161 m_info(InvalidInput) {
162 compute(matrix.derived());
163 }
164
168 void setZero() { m_isInitialized = false; }
169
171 inline typename Traits::MatrixU matrixU() const {
172 eigen_assert(m_isInitialized && "LDLT is not initialized.");
173 return Traits::getU(m_matrix);
174 }
175
177 inline typename Traits::MatrixL matrixL() const {
178 eigen_assert(m_isInitialized && "LDLT is not initialized.");
179 return Traits::getL(m_matrix);
180 }
181
184 inline const TranspositionType& transpositionsP() const {
185 eigen_assert(m_isInitialized && "LDLT is not initialized.");
186 return m_transpositions;
187 }
188
191 eigen_assert(m_isInitialized && "LDLT is not initialized.");
192 return m_matrix.diagonal();
193 }
194
196 inline bool isPositive() const {
197 eigen_assert(m_isInitialized && "LDLT is not initialized.");
198 return m_sign == internal::PositiveSemiDef || m_sign == internal::ZeroSign;
199 }
200
202 inline bool isNegative(void) const {
203 eigen_assert(m_isInitialized && "LDLT is not initialized.");
204 return m_sign == internal::NegativeSemiDef || m_sign == internal::ZeroSign;
205 }
206
207#ifdef EIGEN_PARSED_BY_DOXYGEN
223 template <typename Rhs>
224 inline Solve<LDLT, Rhs> solve(const MatrixBase<Rhs>& b) const;
225#endif
226
227 template <typename Derived>
228 bool solveInPlace(MatrixBase<Derived>& bAndX) const;
229
230 template <typename InputType>
231 LDLT& compute(const EigenBase<InputType>& matrix);
232
236 RealScalar rcond() const {
237 eigen_assert(m_isInitialized && "LDLT is not initialized.");
238 return internal::rcond_estimate_helper(m_l1_norm, *this);
239 }
240
241 template <typename Derived>
242 LDLT& rankUpdate(const MatrixBase<Derived>& w, const RealScalar& alpha = 1);
243
259 Scalar determinant() const;
260
274 RealScalar absDeterminant() const;
275
289 RealScalar logAbsDeterminant() const;
290
301 Scalar signDeterminant() const;
302
307 inline const MatrixType& matrixLDLT() const {
308 eigen_assert(m_isInitialized && "LDLT is not initialized.");
309 return m_matrix;
310 }
311
312 MatrixType reconstructedMatrix() const;
313
320 const LDLT& adjoint() const { return *this; }
321
322 EIGEN_DEVICE_FUNC constexpr Index rows() const noexcept { return m_matrix.rows(); }
323 EIGEN_DEVICE_FUNC constexpr Index cols() const noexcept { return m_matrix.cols(); }
324
325 /** \brief Reports whether previous computation was successful.
326 *
327 * \returns \c Success if computation was successful,
328 * \c NumericalIssue if the factorization failed: a pivot is not finite, or is zero above a
329 * non-zero column. In exact arithmetic only an indefinite matrix has the latter, but rounding
330 * errors can give it to a singular semidefinite matrix too.
331 */
333 eigen_assert(m_isInitialized && "LDLT is not initialized.");
334 return m_info;
335 }
336
337#ifndef EIGEN_PARSED_BY_DOXYGEN
338 template <typename RhsType, typename DstType>
339 void _solve_impl(const RhsType& rhs, DstType& dst) const;
340
341 template <bool Conjugate, typename RhsType, typename DstType>
342 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const;
343#endif
344
345 protected:
346 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
347
348
354 MatrixType m_matrix;
355 RealScalar m_l1_norm;
356 TranspositionType m_transpositions;
357 TmpMatrixType m_temporary;
358 // L21 D for the trailing update of the blocked factorization; it stays empty below the blocking threshold.
360 internal::SignMatrix m_sign;
361 bool m_isInitialized;
362 ComputationInfo m_info;
363};
364
365namespace internal {
366
367/** \internal Panel width of the blocked factorization of a \a size x \a size matrix, or 0 where a single
368 * unblocked panel covers the whole matrix: up to three panel widths, below which the level-3 update does not pay
369 * off, and for fixed-size or bounded matrices, which must not allocate the panel workspace.
370 *
371 * The panel's level-2 updates run at a rate R, and the trailing update at P / (1 + kappa / nb), kappa being the
372 * 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
373 * 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
374 * products, and grows once the trailing matrix outgrows the last-level cache. c = 3, with nb rounded to a multiple
375 * of 16 and clamped to [32, 128], the range the measured optimum spans, loses about 2% to the best width on average.
376 * Can be overridden (mainly for testing the panel logic at small sizes) by defining EIGEN_LDLT_BLOCKSIZE. */
377template <typename MatrixType>
378inline Index ldlt_blocksize(Index size) {
379 if (int(MatrixType::MaxRowsAtCompileTime) != Dynamic || int(MatrixType::MaxColsAtCompileTime) != Dynamic) return 0;
380#ifdef EIGEN_LDLT_BLOCKSIZE
381 const Index nb = Index(EIGEN_LDLT_BLOCKSIZE);
382#else
383 constexpr Index kMinBlockSize = 32;
384 // Three of the narrowest panels are not blocked either, so small matrices skip the square root.
385 if (size <= 3 * kMinBlockSize) return 0;
386 const Index unclamped = 16 * Index(numext::round(numext::sqrt(3.0 * double(size)) / 16));
387 const Index nb = numext::mini(numext::maxi(unclamped, kMinBlockSize), Index(128));
388#endif
389 return nb > 0 && size > 3 * nb ? nb : 0;
390}
391
392template <int UpLo>
393struct ldlt_inplace;
394
395template <>
396struct ldlt_inplace<Lower> {
397 // Settles the cases that leave nothing to factor, and returns whether it did: an empty or 1x1 matrix, and a
398 // diagonal that is entirely zero, which offers no pivot and leaves the matrix either zero or indefinite. Otherwise
399 // it copies the diagonal into temp, where factor_panel() expects it.
400 template <typename MatrixType, typename TranspositionType, typename Workspace>
401 static bool factor_trivial(const MatrixType& mat, TranspositionType& transpositions, Workspace& temp,
402 SignMatrix& sign, bool& ret) {
403 using Scalar = typename MatrixType::Scalar;
404 using RealScalar = typename MatrixType::RealScalar;
405 const Index size = mat.rows();
406
407 if (size <= 1) {
408 transpositions.setIdentity();
409 if (size == 0)
410 sign = ZeroSign;
411 else if (numext::real(mat.coeff(0, 0)) > static_cast<RealScalar>(0))
412 sign = PositiveSemiDef;
413 else if (numext::real(mat.coeff(0, 0)) < static_cast<RealScalar>(0))
414 sign = NegativeSemiDef;
415 else
416 sign = ZeroSign;
417 ret = size == 0 || (numext::isfinite)(numext::real(mat.coeff(0, 0)));
418 return true;
419 }
420
421 temp = mat.diagonal().real().template cast<Scalar>();
422 if ((temp.array() == Scalar(0)).all()) {
423 transpositions.setIdentity();
424 sign = ZeroSign;
425 ret = true;
426 for (Index j = 0; ret && j < size; ++j) ret = (mat.col(j).tail(size - j - 1).array() == Scalar(0)).all();
427 return true;
428 }
429 return false;
430 }
431
432 // Factors columns [k0, k0 + kb) left-looking, column k pivoting on max |diag(S_k)|, S_k = A22 - L21 D L21^*
433 // (complete diagonal pivoting). Invariant: mat(k0:n, k0:n) holds S_k0 off its diagonal and temp(k:n) holds
434 // diag(S_k). The caller interchanges the rows of the columns before k0. PivotOnLargestValue pivots on max diag(S_k)
435 // instead, as LAPACK's xPSTRF does: on a semidefinite matrix it takes every positive pivot before a negative one at
436 // the rounding level of S_k, where max |diag(S_k)| can pick the negative one first.
437 template <bool PivotOnLargestValue = false, typename MatrixType, typename TranspositionType, typename Workspace>
438 static bool factor_panel(MatrixType& mat, Index k0, Index kb, TranspositionType& transpositions, Workspace& temp,
439 SignMatrix& sign) {
440 using Scalar = typename MatrixType::Scalar;
441 using RealScalar = typename MatrixType::RealScalar;
442 using IndexType = typename TranspositionType::StorageIndex;
443 const Index size = mat.rows();
444 bool ret = true;
445
446 for (Index k = k0; k < k0 + kb; ++k) {
447 Index index_of_biggest_in_corner;
448 EIGEN_IF_CONSTEXPR (PivotOnLargestValue) {
449 // NaNs are skipped, as xPSTRF's MAXLOC skips them; an all-NaN tail still yields a NaN pivot.
450 temp.tail(size - k).real().template maxCoeff<PropagateNumbers>(&index_of_biggest_in_corner);
451 } else {
452 temp.tail(size - k).real().cwiseAbs().maxCoeff(&index_of_biggest_in_corner);
453 }
454 index_of_biggest_in_corner += k;
455
456 transpositions.coeffRef(k) = IndexType(index_of_biggest_in_corner);
457 if (k != index_of_biggest_in_corner) {
458 auto trailing = mat.bottomRightCorner(size - k0, size - k0);
459 selfadjoint_swap_lower(trailing, k - k0, index_of_biggest_in_corner - k0);
460 numext::swap(temp.coeffRef(k), temp.coeffRef(index_of_biggest_in_corner));
461 }
462
463 // partition the matrix:
464 // A00 | - | -
465 // lu = A10 | A11 | -
466 // A20 | A21 | A22
467 // where A10 and A20 span the panel columns [k0, k); those before k0 are already applied to A21. The
468 // product's operand D A10^* takes temp(k0:k), whose diagonal entries of S have all been used as pivots.
469 Index rs = size - k - 1;
470 Index done = k - k0;
471 auto A21 = mat.block(k + 1, k, rs, fix<1>);
472
473 if (done > 0 && rs > 0) {
474 auto A10 = mat.block(k, k0, fix<1>, done);
475 auto A20 = mat.block(k + 1, k0, rs, done);
476 temp.segment(k0, done) = mat.diagonal().real().segment(k0, done).asDiagonal() * A10.adjoint();
477 A21.noalias() -= A20 * temp.segment(k0, done);
478 }
479
480 // In some previous versions of Eigen (e.g., 3.2.1), the scaling was omitted if the pivot
481 // was smaller than the cutoff value. However, since LDLT is not rank-revealing
482 // we should only make sure that we do not introduce INF or NaN values.
483 // Remark that LAPACK also uses 0 as the cutoff value.
484 RealScalar realAkk = numext::real(temp.coeff(k));
485 mat.coeffRef(k, k) = Scalar(realAkk);
486 bool pivot_is_valid = (numext::abs(realAkk) > RealScalar(0));
487 if (!(numext::isfinite)(realAkk)) ret = false;
488
489 // A zero pivot is the largest remaining, so the rest of D is zero too, and its column must be zero as well.
490 if ((rs > 0) && pivot_is_valid) {
491 A21 /= realAkk;
492 // diag(S_{k+1}) = diag(S_k) - conj(L21) .* (D_k L21), where the next pivot is searched for. Squaring L21
493 // first would underflow for |L21| < sqrt(min) on a graded matrix, where D_k |L21|^2 is representable.
494 temp.tail(rs).real() -= A21.conjugate().cwiseProduct(realAkk * A21).real();
495 } else if (rs > 0) {
496 ret = ret && (A21.array() == Scalar(0)).all();
497 }
498
499 if (sign == PositiveSemiDef) {
500 if (realAkk < static_cast<RealScalar>(0)) sign = Indefinite;
501 } else if (sign == NegativeSemiDef) {
502 if (realAkk > static_cast<RealScalar>(0)) sign = Indefinite;
503 } else if (sign == ZeroSign) {
504 if (realAkk > static_cast<RealScalar>(0))
505 sign = PositiveSemiDef;
506 else if (realAkk < static_cast<RealScalar>(0))
507 sign = NegativeSemiDef;
508 }
509 }
510
511 return ret;
512 }
513
514 template <typename MatrixType, typename TranspositionType, typename Workspace>
515 static bool unblocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, SignMatrix& sign) {
516 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
517 bool ret = true;
518 if (factor_trivial(mat, transpositions, temp, sign, ret)) return ret;
519 return factor_panel(mat, 0, mat.rows(), transpositions, temp, sign);
520 }
521
522 // Blocked (level-3) variant, with the panel/trailing-update structure of LAPACK's xPSTRF: each panel is factored
523 // by factor_panel(), then a single product applies it to the trailing Schur complement, A22 -= L21 D L21^*.
524 template <typename MatrixType, typename TranspositionType, typename Workspace, typename BlockWorkspace>
525 static bool blocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp, BlockWorkspace& workspace,
526 SignMatrix& sign) {
527 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
528 const Index size = mat.rows();
529 const Index nb = ldlt_blocksize<MatrixType>(size);
530 if (nb == 0) return unblocked(mat, transpositions, temp, sign);
531 bool ret = true;
532 if (factor_trivial(mat, transpositions, temp, sign, ret)) return ret;
533
534 workspace.resize(size, nb);
535 for (Index k0 = 0; k0 < size; k0 += nb) {
536 const Index kb = numext::mini(nb, size - k0);
537 const Index k1 = k0 + kb;
538 if (!factor_panel(mat, k0, kb, transpositions, temp, sign)) ret = false;
539
540 // The panel's interchanges, applied to the rows of the columns before it. Column-major storage takes them a
541 // column at a time, where a row swap would stride through memory.
542 EIGEN_IF_CONSTEXPR (MatrixType::IsRowMajor) {
543 for (Index k = k0; k < k1; ++k) {
544 const Index p = transpositions.coeff(k);
545 if (p != k) mat.row(k).head(k0).swap(mat.row(p).head(k0));
546 }
547 } else {
548 for (Index c = 0; c < k0; ++c) {
549 for (Index k = k0; k < k1; ++k) {
550 const Index p = transpositions.coeff(k);
551 if (p != k) numext::swap(mat.coeffRef(k, c), mat.coeffRef(p, c));
552 }
553 }
554 }
555
556 const Index rs = size - k1;
557 if (rs > 0) {
558 auto L21 = mat.block(k1, k0, rs, kb);
559 auto W = workspace.topLeftCorner(rs, kb);
560 W.noalias() = L21 * mat.diagonal().real().segment(k0, kb).asDiagonal();
561 mat.block(k1, k1, rs, rs).template triangularView<Lower>() -= L21 * W.adjoint();
562 }
563 }
564 return ret;
565 }
566
567 // Reference for the algorithm: Davis and Hager, "Multiple Rank
568 // Modifications of a Sparse Cholesky Factorization" (Algorithm 1)
569 // Trivial rearrangements of their computations (Timothy E. Holy)
570 // allow their algorithm to work for rank-1 updates even if the
571 // original matrix is not of full rank.
572 // Here only rank-1 updates are implemented, to reduce the
573 // requirement for intermediate storage and improve accuracy
574 template <typename MatrixType, typename WDerived>
575 static bool updateInPlace(MatrixType& mat, MatrixBase<WDerived>& w,
576 const typename MatrixType::RealScalar& sigma = 1) {
577 using Scalar = typename MatrixType::Scalar;
578 using RealScalar = typename MatrixType::RealScalar;
579
580 const Index size = mat.rows();
581 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
582 EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_ROWS(w, mat);
583
584 RealScalar alpha = 1;
585
586 // Apply the update
587 for (Index j = 0; j < size; j++) {
588 // Check for termination due to an original decomposition of low-rank
589 if (!(numext::isfinite)(alpha)) break;
590
591 // Update the diagonal terms
592 RealScalar dj = numext::real(mat.coeff(j, j));
593 Scalar wj = w.coeff(j);
594 RealScalar swj2 = sigma * numext::abs2(wj);
595 RealScalar gamma = dj * alpha + swj2;
596
597 // A zero contribution leaves both quantities unchanged, but spelling that out as an addition of swj2/alpha and
598 // swj2/dj evaluates 0/0 when alpha or the pivot is zero. The resulting NaN reaches the termination test above
599 // on the next iteration, which reads it as a low-rank signal and abandons the remainder of the update. Skip the
600 // no-op instead. A zero pivot with a nonzero contribution still yields an infinite alpha, so genuine low-rank
601 // termination is unaffected.
602 if (!numext::is_exactly_zero(swj2)) {
603 mat.coeffRef(j, j) += swj2 / alpha;
604 alpha += swj2 / dj;
605 }
606
607 // Update the terms of L
608 Index rs = size - j - 1;
609 w.tail(rs) -= wj * mat.col(j).tail(rs);
610 if (!numext::is_exactly_zero(gamma)) mat.col(j).tail(rs) += (sigma * numext::conj(wj) / gamma) * w.tail(rs);
611 }
612 return true;
613 }
614
615 template <typename MatrixType, typename TranspositionType, typename Workspace, typename WType>
616 static bool update(MatrixType& mat, const TranspositionType& transpositions, Workspace& tmp, const WType& w,
617 const typename MatrixType::RealScalar& sigma = 1) {
618 // Apply the permutation to the input w
619 tmp = transpositions * w;
620
621 return ldlt_inplace<Lower>::updateInPlace(mat, tmp, sigma);
622 }
623};
624
625template <>
626struct ldlt_inplace<Upper> {
627 template <typename MatrixType, typename TranspositionType, typename Workspace>
628 static EIGEN_STRONG_INLINE bool unblocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp,
629 SignMatrix& sign) {
630 Transpose<MatrixType> matt(mat);
631 return ldlt_inplace<Lower>::unblocked(matt, transpositions, temp, sign);
632 }
633
634 template <typename MatrixType, typename TranspositionType, typename Workspace, typename BlockWorkspace>
635 static EIGEN_STRONG_INLINE bool blocked(MatrixType& mat, TranspositionType& transpositions, Workspace& temp,
636 BlockWorkspace& workspace, SignMatrix& sign) {
637 Transpose<MatrixType> matt(mat);
638 return ldlt_inplace<Lower>::blocked(matt, transpositions, temp, workspace, sign);
639 }
640
641 template <typename MatrixType, typename TranspositionType, typename Workspace, typename WType>
642 static EIGEN_STRONG_INLINE bool update(MatrixType& mat, TranspositionType& transpositions, Workspace& tmp, WType& w,
643 const typename MatrixType::RealScalar& sigma = 1) {
644 Transpose<MatrixType> matt(mat);
645 return ldlt_inplace<Lower>::update(matt, transpositions, tmp, w.conjugate(), sigma);
646 }
647};
648
649template <typename MatrixType>
650struct LDLT_Traits<MatrixType, Lower> {
651 using MatrixL = const TriangularView<const MatrixType, UnitLower>;
652 using MatrixU = const TriangularView<const typename MatrixType::AdjointReturnType, UnitUpper>;
653 static inline MatrixL getL(const MatrixType& m) { return MatrixL(m); }
654 static inline MatrixU getU(const MatrixType& m) { return MatrixU(m.adjoint()); }
655};
656
657template <typename MatrixType>
658struct LDLT_Traits<MatrixType, Upper> {
659 using MatrixL = const TriangularView<const typename MatrixType::AdjointReturnType, UnitLower>;
660 using MatrixU = const TriangularView<const MatrixType, UnitUpper>;
661 static inline MatrixL getL(const MatrixType& m) { return MatrixL(m.adjoint()); }
662 static inline MatrixU getU(const MatrixType& m) { return MatrixU(m); }
663};
664
665} // end namespace internal
666
669template <typename MatrixType, int UpLo_>
670template <typename InputType>
671LDLT<MatrixType, UpLo_>& LDLT<MatrixType, UpLo_>::compute(const EigenBase<InputType>& a) {
672 EIGEN_INTERNAL_ASSERT_SQUARE(a);
673 const Index size = a.rows();
674
675 m_matrix = a.derived();
676
677 // Compute matrix L1 norm = max abs column sum over the implicit self-adjoint matrix.
678 m_l1_norm = m_matrix.template selfadjointView<UpLo_>().l1Norm();
679
680 m_transpositions.resize(size);
681 m_isInitialized = false;
682 m_temporary.resize(size);
683 m_sign = internal::ZeroSign;
684
685 m_info = internal::ldlt_inplace<UpLo>::blocked(m_matrix, m_transpositions, m_temporary, m_workspace, m_sign)
686 ? Success
688
689 m_isInitialized = true;
690 return *this;
691}
692
712template <typename MatrixType, int UpLo_>
713template <typename Derived>
714LDLT<MatrixType, UpLo_>& LDLT<MatrixType, UpLo_>::rankUpdate(
715 const MatrixBase<Derived>& w, const typename LDLT<MatrixType, UpLo_>::RealScalar& sigma) {
716 using IndexType = typename TranspositionType::StorageIndex;
717 const Index size = w.rows();
718 if (m_isInitialized) {
719 EIGEN_INTERNAL_ASSERT_SAME_ROWS(m_matrix, w);
720 } else {
721 m_matrix.resize(size, size);
722 m_matrix.setZero();
723 m_transpositions.resize(size);
724 for (Index i = 0; i < size; i++) m_transpositions.coeffRef(i) = IndexType(i);
725 m_temporary.resize(size);
726 m_sign = sigma >= 0 ? internal::PositiveSemiDef : internal::NegativeSemiDef;
727 m_isInitialized = true;
728 // Assigned here rather than after the branch: updating an existing factorization keeps the status it already has.
729 m_info = Success;
730 }
731
732 internal::ldlt_inplace<UpLo>::update(m_matrix, m_transpositions, m_temporary, w, sigma);
733
734 return *this;
735}
736
737// A = P^T L D L^* P with L unit lower triangular and D real diagonal, so det(A) = prod(D_ii).
738
739template <typename MatrixType_, int UpLo_>
740typename LDLT<MatrixType_, UpLo_>::Scalar LDLT<MatrixType_, UpLo_>::determinant() const {
741 eigen_assert(m_isInitialized && "LDLT is not initialized.");
742 eigen_assert(m_info == Success && "LDLT failed because of a zero pivot.");
743 return Scalar(internal::scaled_prod(vectorD().real()).value());
744}
745
746template <typename MatrixType_, int UpLo_>
748 eigen_assert(m_isInitialized && "LDLT is not initialized.");
749 eigen_assert(m_info == Success && "LDLT failed because of a zero pivot.");
750 return internal::scaled_prod(vectorD().real()).abs();
751}
752
753template <typename MatrixType_, int UpLo_>
755 eigen_assert(m_isInitialized && "LDLT is not initialized.");
756 eigen_assert(m_info == Success && "LDLT failed because of a zero pivot.");
757 return internal::log_abs_prod(vectorD().real());
758}
759
760template <typename MatrixType_, int UpLo_>
761typename LDLT<MatrixType_, UpLo_>::Scalar LDLT<MatrixType_, UpLo_>::signDeterminant() const {
762 eigen_assert(m_isInitialized && "LDLT is not initialized.");
763 eigen_assert(m_info == Success && "LDLT failed because of a zero pivot.");
764 return Scalar(vectorD().real().array().sign().prod());
765}
766
767#ifndef EIGEN_PARSED_BY_DOXYGEN
768template <typename MatrixType_, int UpLo_>
769template <typename RhsType, typename DstType>
770void LDLT<MatrixType_, UpLo_>::_solve_impl(const RhsType& rhs, DstType& dst) const {
771 _solve_impl_transposed<true>(rhs, dst);
772}
773
774template <typename MatrixType_, int UpLo_>
775template <bool Conjugate, typename RhsType, typename DstType>
776void LDLT<MatrixType_, UpLo_>::_solve_impl_transposed(const RhsType& rhs, DstType& dst) const {
777 // dst = P b
778 dst = m_transpositions * rhs;
779
780 // dst = L^-1 (P b)
781 // dst = L^-*T (P b)
782 matrixL().template conjugateIf<!Conjugate>().solveInPlace(dst);
783
784 // dst = D^-* (L^-1 P b)
785 // dst = D^-1 (L^-*T P b)
786 // more precisely, use pseudo-inverse of D (see bug 241)
787 const typename Diagonal<const MatrixType>::RealReturnType vecD(vectorD());
788 // In some previous versions, tolerance was set to the max of 1/highest (or rather numeric_limits::min())
789 // and the maximal diagonal entry * epsilon as motivated by LAPACK's xGELSS:
790 // RealScalar tolerance = numext::maxi(vecD.array().abs().maxCoeff() * NumTraits<RealScalar>::epsilon(),RealScalar(1)
791 // / NumTraits<RealScalar>::highest()); However, LDLT is not rank revealing, and so adjusting the tolerance wrt to the
792 // highest diagonal element is not well justified and leads to numerical issues in some cases. Moreover, Lapack's
793 // xSYTRS routines use 0 for the tolerance. Using numeric_limits::min() gives us more robustness to denormals.
794 RealScalar tolerance = (std::numeric_limits<RealScalar>::min)();
795 for (Index i = 0; i < vecD.size(); ++i) {
796 if (numext::abs(vecD(i)) > tolerance)
797 dst.row(i) /= vecD(i);
798 else
799 dst.row(i).setZero();
800 }
801
802 // dst = L^-* (D^-* L^-1 P b)
803 // dst = L^-T (D^-1 L^-*T P b)
804 matrixL().transpose().template conjugateIf<Conjugate>().solveInPlace(dst);
805
806 // dst = P^T (L^-* D^-* L^-1 P b) = A^-1 b
807 // dst = P^-T (L^-T D^-1 L^-*T P b) = A^-1 b
808 dst = m_transpositions.transpose() * dst;
809}
810#endif
811
825template <typename MatrixType, int UpLo_>
826template <typename Derived>
827bool LDLT<MatrixType, UpLo_>::solveInPlace(MatrixBase<Derived>& bAndX) const {
828 eigen_assert(m_isInitialized && "LDLT is not initialized.");
829 EIGEN_INTERNAL_ASSERT_SAME_ROWS(m_matrix, bAndX);
830
831 bAndX = this->solve(bAndX);
832
833 return true;
834}
835
839template <typename MatrixType, int UpLo_>
841 eigen_assert(m_isInitialized && "LDLT is not initialized.");
842 MatrixType res = matrixU();
843 res = vectorD().real().asDiagonal() * res;
844 res = matrixL() * res;
845 // P^T (L D L^*) P; the stored pivots cannot alias the new result.
846 auto lower_triangle = res.template selfadjointView<Lower>();
847 for (Index k = m_matrix.rows() - 1; k >= 0; --k) lower_triangle.applyTransposition(k, m_transpositions.coeff(k));
848 res.template triangularView<StrictlyUpper>() = res.adjoint();
849
850 return res;
851}
852
857template <typename MatrixType, unsigned int UpLo>
862
867template <typename Derived>
871
872} // end namespace Eigen
873
874#endif // EIGEN_LDLT_H
Expression of a diagonal/subdiagonal/superdiagonal in a matrix.
Definition Diagonal.h:78
Robust Cholesky decomposition of a matrix with pivoting.
Definition LDLT.h:75
const TranspositionType & transpositionsP() const
Definition LDLT.h:184
Solve< LDLT, Rhs > solve(const MatrixBase< Rhs > &b) const
Traits::MatrixL matrixL() const
Definition LDLT.h:177
Diagonal< const MatrixType > vectorD() const
Definition LDLT.h:190
Scalar determinant() const
Definition LDLT.h:740
void setZero()
Definition LDLT.h:168
const MatrixType & matrixLDLT() const
Definition LDLT.h:307
RealScalar rcond() const
Definition LDLT.h:236
bool isNegative(void) const
Definition LDLT.h:202
LDLT()
Default Constructor.
Definition LDLT.h:99
bool isPositive() const
Definition LDLT.h:196
Scalar signDeterminant() const
Definition LDLT.h:761
LDLT(const EigenBase< InputType > &matrix)
Constructor with decomposition.
Definition LDLT.h:135
RealScalar absDeterminant() const
Definition LDLT.h:747
LDLT(Index size)
Default Constructor with memory preallocation.
Definition LDLT.h:117
LDLT(EigenBase< InputType > &matrix)
Constructs a LDLT factorization from a given matrix.
Definition LDLT.h:154
MatrixType reconstructedMatrix() const
Definition LDLT.h:840
ComputationInfo info() const
Reports whether previous computation was successful.
Definition LDLT.h:332
const LDLT & adjoint() const
Definition LDLT.h:320
Traits::MatrixU matrixU() const
Definition LDLT.h:171
RealScalar logAbsDeterminant() const
Definition LDLT.h:754
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
LDLT< PlainObject > ldlt() const
Definition LDLT.h:868
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Permutation matrix.
Definition PermutationMatrix.h:346
LDLT< PlainObject, UpLo > ldlt() const
Definition LDLT.h:858
Pseudo expression representing a solving operation.
Definition Solve.h:63
constexpr LDLT< MatrixType_, UpLo_ > & derived()
Represents a sequence of transpositions (row/column interchange)
Definition Transpositions.h:144
static const auto fix()
ComputationInfo
Definition Constants.h:455
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ NumericalIssue
Definition Constants.h:459
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index size() const noexcept
Definition EigenBase.h:65