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