Limited-Memory LDLᵀ Factorization
A Port of LLDL to Julia. See https://github.com/optimizers/lldl.
Please cite this repository if you use LimitedLDLFactorizations.jl in your work: see CITATION.bib.
LimitedLDLFactorizations is a limited-memory LDLᵀ factorization for symmetric matrices. Given a symmetric matrix A, we search for a unit lower triangular L, a diagonal D and a diagonal ∆ such that LDLᵀ is an incomplete factorization of A+∆. The elements of the diagonal matrix ∆ have the form ±α, where α ≥ 0 is a shift.
It is possible to only supply the lower triangle of A and/or a prescribed permutation that attempts to diminish fill-in. AMD.jl and Metis.jl are recommended packages for computing fill-reducing orderings of sparse matrices.
Installing
julia> ]
pkg> add LimitedLDLFactorizationsBrief Description
The only functions exported are lldl, \, ldiv! and nnz.
Supply a dense array or sparse matrix to lldl.
Dense arrays will be converted to sparse.
The strict lower triangle and diagonal of sparse matrices will be extracted.
Optionally, supply
- a memory parameter to allow more fill in the L factor;
- a drop tolerance to discard small elements in the L factor;
- an initial shift to speed up the process in case the factorization does not exist without shift.
Using a memory parameter larger than or equal to the size of A will yield an exact factorization provided one exists with the permutation supplied. In particular, the full factorization exists for any symmetric permutation of a symmetric quasi-definite matrix.
lldl returns a factorization in the form of a LimitedLDLFactorization object.
The \ and ldiv! methods are implemented for objects of type LimitedLDLFactorization
More Examples
See examples/example.jl and tests/runtest.jl.
Complete Description
[1] C.-J. Lin and J. J. Moré. Incomplete Cholesky factorizations with limited
memory. SIAM Journal on Scientific Computing, 21(1):24--45, 1999.
DOI 10.1137/S1064827597327334.
[2] http://www.mcs.anl.gov/~more/icfs
[3] D. Orban. Limited-Memory LDLᵀ Factorization of Symmetric Quasi-Definite
Matrices with Application to Constrained Optimization. Numerical Algorithms
70(1):9--41, 2015. DOI 10.1007/s11075-014-9933-x.
[4] https://github.com/optimizers/lldl