Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ > Class Template Reference

#include <Eigen/src/SparseCholesky/MultifrontalLDLT.h>

Detailed Description

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
class Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >

Sparse multifrontal LDL^* factorization of a symmetric or Hermitian indefinite matrix.

This class computes \( P A P^T = L D L^* \), where \( P \) is a permutation, \( L \) is unit lower triangular and \( D \) 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 \( u \), a 1x1 pivot on column \( j \) is accepted if

\[ |a_{jj}| \ge u \max_{i \ne j} |a_{ij}| \]

and a 2x2 pivot \( D \) on columns \( j \) and \( r \) is accepted if

\[ |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 . \]

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 \( u \le 1/2 \) 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 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.
Template Parameters
MatrixType_the type of the sparse matrix A, it must be a SparseMatrix<>
UpLo_the triangular part that will be used for the factorization: Lower (default) or Upper. The other triangular part won't be read.
Ordering_The fill-reducing ordering method. See the OrderingMethods module for the list of built-in and external ordering methods.

This class follows the sparse solver concept .

See also
class SimplicialLDLT, class BunchKaufman, class AMDOrdering, class NaturalOrdering
+ Inheritance diagram for Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >:

Public Member Functions

RealScalar absDeterminant () const
 
void analyzePattern (const MatrixType &matrix)
 
MultifrontalLDLT & compute (const MatrixType &matrix)
 
Scalar determinant () const
 
void factorize (const MatrixType &matrix)
 
ComputationInfo info () const
 Reports whether the previous factorization was successful.
 
bool isNegative () const
 
bool isPositive () const
 
RealScalar logAbsDeterminant () const
 
FactorType matrixL () const
 
FactorType matrixU () const
 
 MultifrontalLDLT ()=default
 
 MultifrontalLDLT (const MatrixType &matrix)
 
Index nonZeros () const
 
Index numNegative () const
 
Index numPositive () const
 
Index numZero () const
 
const PermutationType & permutationP () const
 
const PermutationType & permutationPinv () const
 
const RealScalar & pivotThreshold () const
 
MultifrontalLDLT & setPivotThreshold (const RealScalar &threshold)
 
Scalar signDeterminant () const
 
const VectorType & subDiagonal () const
 
const RealVectorType & vectorD () const
 
- Public Member Functions inherited from Eigen::SparseSolverBase< Derived >
template<typename Rhs>
Solve< Derived, Rhs > solve (const MatrixBase< Rhs > &b) const
 
template<typename Rhs>
Solve< Derived, Rhs > solve (const SparseMatrixBase< Rhs > &b) const
 
 SparseSolverBase ()=default
 

Constructor & Destructor Documentation

◆ MultifrontalLDLT() [1/2]

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::MultifrontalLDLT ( )
default

Default constructor

◆ MultifrontalLDLT() [2/2]

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::MultifrontalLDLT ( const MatrixType & matrix)
inlineexplicit

Constructs the factorization of matrix.

Member Function Documentation

◆ absDeterminant()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
RealScalar Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::absDeterminant ( ) const
inline
Returns
the absolute value of the determinant of the matrix.
Warning
Like determinant(), this can overflow or underflow.
See also
determinant(), logAbsDeterminant()

◆ analyzePattern()

template<typename MatrixType_, int UpLo_, typename Ordering_>
void Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::analyzePattern ( const MatrixType & matrix)

Performs the symbolic analysis of the sparsity pattern of matrix.

See also
factorize(), compute()

◆ compute()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
MultifrontalLDLT & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::compute ( const MatrixType & matrix)
inline

Computes the symbolic analysis and the factorization of matrix.

Returns
a reference to *this.

◆ determinant()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Scalar Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::determinant ( ) const
inline
Returns
the determinant of the matrix, \( \exp(\log|\det A|) \) 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.
See also
absDeterminant(), logAbsDeterminant(), signDeterminant()

◆ factorize()

template<typename MatrixType_, int UpLo_, typename Ordering_>
void Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::factorize ( const MatrixType & matrix)

Performs the numeric factorization of matrix, which must have the sparsity pattern given to analyzePattern().

See also
analyzePattern(), compute()

◆ info()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
ComputationInfo Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::info ( ) const
inline

Reports whether the previous factorization was successful.

Returns
Success if every pivot was finite and nonzero, 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 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.

◆ isNegative()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
bool Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::isNegative ( ) const
inline
Returns
true if the matrix is negative semidefinite: every pivot is finite and no eigenvalue is positive.

◆ isPositive()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
bool Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::isPositive ( ) const
inline
Returns
true if the matrix is positive semidefinite: every pivot is finite and no eigenvalue is negative.

◆ logAbsDeterminant()

template<typename MatrixType_, int UpLo_, typename Ordering_>
MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::RealScalar Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::logAbsDeterminant ( ) const
Returns
the natural log of the absolute value of the determinant of the matrix,

\[ \log|\det A| = \sum_{1 \times 1} \log|d_k| + \sum_{2 \times 2} \left( 2 \log s_k + \log|\delta_k| \right), \]

where a 2x2 block of D is \( s_k \) times a block with largest magnitude 1 and determinant \( \delta_k \). It is \( -\infty \) if a pivot is zero, and not finite if a pivot is not finite.
See also
determinant(), signDeterminant()

◆ matrixL()

template<typename MatrixType_, int UpLo_, typename Ordering_>
MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::FactorType Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::matrixL ( ) const
Returns
the unit lower triangular factor \( L \) 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. \( L_{k+1,k} = 0 \) where pivots k and k+1 form a 2x2 block of D.
See also
matrixU(), vectorD(), subDiagonal(), permutationP()

◆ matrixU()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
FactorType Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::matrixU ( ) const
inline
Returns
the unit upper triangular factor \( U = L^* \) of the previous factorization. Like matrixL(), it is assembled on each call.
See also
matrixL()

◆ nonZeros()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Index Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::nonZeros ( ) const
inline
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.

◆ numNegative()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Index Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::numNegative ( ) const
inline
Returns
the number of negative eigenvalues.
See also
numPositive()

◆ numPositive()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Index Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::numPositive ( ) const
inline
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 NumericalIssue otherwise.

See also
numNegative(), numZero()

◆ numZero()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Index Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::numZero ( ) const
inline
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.
See also
numPositive()

◆ permutationP()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
const PermutationType & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::permutationP ( ) const
inline
Returns
the permutation \( P \) 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().
See also
permutationPinv()

◆ permutationPinv()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
const PermutationType & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::permutationPinv ( ) const
inline
Returns
the inverse of the permutation \( P \). Entry k of its indices() is the row of pivot k in the matrix given to factorize().
See also
permutationP()

◆ pivotThreshold()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
const RealScalar & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::pivotThreshold ( ) const
inline
Returns
the pivot threshold.
See also
setPivotThreshold()

◆ setPivotThreshold()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
MultifrontalLDLT & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::setPivotThreshold ( const RealScalar & threshold)
inline

Sets the threshold \( u \) 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 *this.

◆ signDeterminant()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
Scalar Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::signDeterminant ( ) const
inline
Returns
the sign of the determinant of the matrix: 1, -1, or 0 if a pivot is zero or not finite. It is \( (-1)^{n_-} \) for the inertia numNegative() = \( n_- \), so it doesn't overflow.
See also
determinant(), logAbsDeterminant(), numNegative()

◆ subDiagonal()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
const VectorType & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::subDiagonal ( ) const
inline
Returns
the subdiagonal of D, in pivot order. Entry k is nonzero if and only if pivots k and k+1 form a 2x2 block.

◆ vectorD()

template<typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
const RealVectorType & Eigen::MultifrontalLDLT< MatrixType_, UpLo_, Ordering_ >::vectorD ( ) const
inline
Returns
the diagonal of D, in pivot order.

The documentation for this class was generated from the following file: