zeta1999 / qdldl

A free LDL factorisation routine

QDLDL

A free LDL factorisation routine for quasi-definite linear systems: Ax=b

Interfaces

You can find a Python interface at qdldl-python and a pure Julia implementation at QDLDL.jl.

Getting started

To start using QDLDL, first clone the repository

git clone https://github.com/osqp/qdldl.git

Build

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 examples/example.c
• 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.

Install/Uninstall

To install (uninstall) the libraries and headers you can simply run make install (make uninstall) after running the cmake command above.

Calling QDLDL

Main API

The QDLDL API consists of 5 functions documented in include/qdldl.h. For more details and a working example see examples/example.c.

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 L, D and Dinv = 1./D
• QDLDL_solve: solves the linear system LDL'x = b
• QDLDL_Lsolve: solves Lx = b
• QDLDL_Ltsolve: solves L'x = b

In the above function calls the matrices A and 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.)

The matrices D and 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)

The QDLDL_bool is internally defined as unsigned char.

Linking QDLDL

Basic Example

A basic example appears in examples/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. The current CMakeLists.txt file creates an object library called qdldlobject. 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.

Citing

If you find this code useful for your research, please cite the following paper available in this preprint

@article{osqp,
  author  = {Stellato, B. and Banjac, G. and Goulart, P. and Bemporad, A. and Boyd, S.},
  title   = {{OSQP}: an operator splitting solver for quadratic programs},
  journal = {Mathematical Programming Computation},
  year    = {2020},
  volume  = {12},
  number  = {4},
  pages   = {637--672},
  doi     = {10.1007/s12532-020-00179-2},
  url     = {https://doi.org/10.1007/s12532-020-00179-2},
}

The algorithm

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.

Credits

• Paul Goulart: main development
• Bartolomeo Stellato: code refactoring and testing
• Goran Banjac