LDLFactorizations: Factorization of Symmetric Matrices
A translation of Tim Davis's Concise LDLᵀ Factorization, part of SuiteSparse with several improvements.
Please cite this repository if you use LDLFactorizations.jl in your work: see CITATION.bib
.
This package is appropriate for matrices A that possess a factorization of the form LDLᵀ without pivoting, where L is unit lower triangular and D is diagonal (indefinite in general), including definite and quasidefinite matrices.
LDLFactorizations.jl should not be expected to be as fast, as robust or as accurate as factorization packages such as HSL.jl, MUMPS.jl or Pardiso.jl. Those are multifrontal and/or implement various forms of parallelism, and employ sophisticated pivot strategies.
The main advantages of LDLFactorizations.jl are that

it is very short and has a small footprint;

it is in pure Julia, and so
2.a. it does not require external compiled dependencies;
2.b. it will work with multiple input data types.
Whereas MUMPS.jl, HSL.jl and Pardiso.jl only work with single and double precision reals and complex data types, LDLFactorizations.jl accepts any numerical data type.
Installing
julia> ]
pkg> add LDLFactorizations
Usage
The only exported functions are ldl()
, \
and ldiv!
.
Calling ldl()
with a dense array converts it to a sparse matrix.
A permutation ordering can be supplied: ldl(A, p)
where p
is an Int
array representing a permutation of the integers between 1 and the order
of A
.
If no permutation is supplied, one is automatically computed using AMD.jl.
Only the upper triangle of A
is accessed.
ldl
returns a factorization in the form of a LDLFactorization
object.
The \
and ldiv!
methods are implemented for objects of type LDLFactorization
so that
solving a linear system is as easy as
LDLT = ldl(A) # LDLᵀ factorization of A
x = LDLT \ b # solves Ax = b
ldiv!(LDLT, b) # computes LDLT \ b inplace and overwriting b to store the result
y = similar(b)
ldiv!(y, LDLT, b) # computes LDLT \ b inplace and store the result in y
The factorization can of course be reused to solve for multiple righthand sides.
Factors can be accessed as LDLT.L
and LDLT.D
, and the permutation vector as LDLT.P
.
Because the L factor is unit lower triangular, its diagonal is not stored.
Thus the factors satisfy: PAPᵀ = (L + I) D (L + I)ᵀ.
References
Timothy A. Davis. 2005. Algorithm 849: A concise sparse Cholesky factorization package. ACM Trans. Math. Softw. 31, 4 (December 2005), 587591. DOI 10.1145/1114268.1114277.
Like the original LDL, this package is distributed under the LGPL.
Bug reports and discussions
If you think you found a bug, feel free to open an issue. Focused suggestions and requests can also be opened as issues. Before opening a pull request, start an issue or a discussion on the topic, please.
If you want to ask a question not suited for a bug report, feel free to start a discussion here. This forum is for general discussion about this repository and the JuliaSmoothOptimizers organization, so questions about any of our packages are welcome.