LLDL is a modification of Lin and Moré's limited-memory Cholesky factorization code-named ICFS for symmetric positive definite matrices. LLDL implements a similar limited-memory scheme for symmetric indefinite matrices that possess a LDLT factorization, i.e., with D diagonal. Symmetric quasi-definite matrices fall into this category.
LLDL is applicable to symmetric indefinite matrices that are not quasi definite, or more generally do not admit a LDLT factorization. In this case, it computes an incomplete LDLT factorization of a nearby matrix.
The main idea is that if L and D are the exact factors of A, the preconditioned matrix (L |D| LT)-1 A has only two eigenvalues: +1 and -1. The hope is that incomplete factors will strike a good balance between computational cost and eigenvalue clustering.
|D|-1/2 L-1 A L-T |D|-1/2 x = |D|-1/2 L-1 b.
Just do it ;)
You can use non-default compilers and compiler flags by passing options to the
install script. For instance
CC=clang FC=ifort CFLAGS='-g' FFLAGS='-FI' ./install
Here is the complete list:
$ ./install --help install [--help] [--skip-matlab-check] The following environment variables may be set to influence the behavior of the install procedure: CC C compiler executable FC Fortran compiler executable CFLAGS C compiler flags FFLAGS Fortran compiler flags MATLABDIR Path to Matlab's bin and extern subdirs
You can specify the location of Matlab's
extern subdirectories using the
The original Matlab interface has been fixed and modernized. The Mathworks only support version 4.3 gfortran on OSX and Linux. On Linux,
gcc-4.3 should be found in your package manager. On OSX, I recommend using Homebrew. Once Homebrew is installed,
gcc-4.3, including the Fortran compiler, may be installed using
brew tap homebrew/versions brew install gcc43 --enable-fortran --enable-profiled-build
The compiler executables installed by the above commands are those used by default in LLDL's
install script. If you know that your compilers will produce valid MEX files (it is the case for
gfortran-4.2 on OSX 10.6.8), then:
Here is an example Matlab session:
n = 6; m = 4; E = rand(m,n); A = [(n+m+1)*eye(n) E' ; E -(n+m+1)*eye(m)]; Adiag = full(diag(A)); lA = sparse(tril(A,-1)); p=1; [L, D, shift] = lldl(lA, Adiag, p); L = L + speye(size(L)); % Diagonal was left out of L.
In practice it is more programmatically convenient to use the incomplete factors L and D as implicitly defining the preconditioner by bundling them into an abstract SPOT operator:
LLDL = opLLDL(A, p); x = LLDL * y; % Solves L |D| L' x = y;
brew install gcc brew tap staticfloat/julia brew tap homebrew/versions brew install julia --HEAD # Add --64bit if desired.
Here is an example Julia session:
n = 10; m = 6; E = sprand(m, n, .2); p = 1; A = [(n+m+1)*speye(n) E' ; E -(n+m+1)*speye(m)]; (L, d, shift) = lldl(K, p); # Returns L as a matrix, not including unit diagonal (LLDL, shift) = lldl_op(K, p); # Returns a linear operator x = LLDL * y; # Solves L |D| L' x = y;
lldl_test.jl for another example.
Trouble / Questions / Bugs
The test problems in the
tprobs folder and the preconditioned CG implementation are relics of ICFS. The main driver is not applicable, except if the coefficient matrix is definite.
To Do List
This is a list of improvements that could be added to LLDL to improve its efficiency, particularly with Matlab.
- Drop-off threshold.
- Implicit permutation: instead of having to explicity apply a reordering, the user supplies a permutation vector. The incomplete factorization proceeds in the order given by this permutation vector.
- D. Orban. Limited-Memory LDLT Factorization of Symmetric Quasi-Definite Matrices with Application to Constrained Optimization. Cahier du GERAD G-2013-87. GERAD, Montreal, Canada.
- C.-J. Lin and J. J. Moré. Incomplete Cholesky factorizations with limited memory. SIAM Journal on Scientific Computing, 21(1):24--45, 1999.
The original ICFS README is in