{{ message }}

# osqp / qdldl

A free LDL factorisation routine

Switch branches/tags
Nothing to show

## Files

Failed to load latest commit information.
Type
Name
Commit time

# 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/oxfordcontrol/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:

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`.

### 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
``````

``````# Link static library

``````

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

A free LDL factorisation routine