A free LDL factorisation routine for quasi-definite linear systems:
To start using QDLDL, first clone the repository
git clone https://github.com/oxfordcontrol/qdldl.git
To build QDLDL, you need to install cmake and run
mkdir build cd build cmake .. cmake --build .
This will generate an
out/ folder with contents:
qdldl_example: a code example from
libqdldl: a static and a dynamic versions of the library.
You can include an addition option
-DUNITTESTS=ON when calling
cmake, which will result in an additional executable
qdldl_tester being built in the
out/ folder to test QDLDL on a variety of problems, including those with rank deficient or otherwise ill-formatted inputs.
N.B. All files will have file extensions appropriate to your operating system.
To install (uninstall) the libraries and headers you can simply run
make install (
make uninstall) after running the
cmake command above.
N.B. There is no memory allocation performed in these routines. The user is assumed to have the working vectors already allocated.
Here is a brief summary.
QDLDL_etree: compute the elimination tree for the quasidefinite matrix factorization
A = LDL'
QDLDL_factor: return the factors
Dinv = 1./D
QDLDL_solve: solves the linear system
LDL'x = b
Lx = b
L'x = b
In the above function calls the matrices
L are stored in compressed sparse column (CSC) format. The matrix
A is assumed to be symmetric and only the upper triangular portion of A should be passed to the API. The factor
L is lower triangular with implicit ones on the diagonal (i.e. the diagonal of L is not stored as part of the CSC formatted data.)
Dinv are both diagonal matrices, with the diagonal values stored in an array.
The matrix input
A should be quasidefinite. The API provides some (non-comprehensive) error checking to protect against non-quasidefinite or non-upper triangular inputs.
Custom types for integer, floats and booleans
QDLDL uses its own internal types for integers, floats and booleans (
QDLDL_int, QDLDL_float, QDLDL_bool. They can be specified using the cmake options:
DFLOAT(default false): uses float numbers instead of doubles
DLONG(default true): uses long integers for indexing (for large matrices)
QDLDL_bool is internally defined as
A basic example appears in
examples/c/example.c and is compiled using cmake and the
CMakeLists.txt file in the root folder.
Including in a cmake project
You can include QDLDL in a cmake project
foo by adding the subdirectory as
# Add project add_subdirectory(qdldl)
QDLDL can be linked using a static or dynamic linker
# Link static library target_link_libraries (foo qdldlstatic) # Link shared library target_link_libraries (foo qdldl)
for dynamic linking the shared library should be available in your path.
There is also the option to include QDLDL as an object library in your project.
CMakeLists.txt file creates an object library called
This can be added to your project by adding it after your sources.
For example, when creating a library
foo you can add
add_library(foo foo.c foo.h $<TARGET_OBJECTS:qdldlobject>)
for more details see the cmake documentation.
The algorithm is an independent implementation of the elimination tree and factorisation procedures outlined in
T. A Davis. Algorithm 849: a concise sparse cholesky factorization package. ACM Trans. Math. Softw., 31(4):587–591, 2005.