osqp/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 control which libraries and executables are built using the following cmake options:

• QDLDL_BUILD_STATIC_LIB (default on) - Build the static library version of QDLDL.
• QDLDL_BUILD_SHARED_LIB (default on) - Build the shared library version of QDLDL.
• QDLDL_BUILD_DEMO_EXE (default on) - Build the qdldl_example demo executable (requires the static library).

You can include an addition option -QDLDL_UNITTESTS=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:

• QDLDL_FLOAT (default false): uses float numbers instead of doubles
• QDLDL_LONG (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

qdldl's Issues

Windows: fatal error C1083: Cannot open include file: 'qdldl_types.h'

@WCHIHO is reporting the following build error on Windows (Microsoft Visual Studio Community 2018 using Python environment including MSBuild) when installing via pip install qpsolvers, which depends on qdldl. The build seems to fail at qdldl:

" running build_ext
-- Selecting Windows SDK version to target Windows 10.0.19043.
CMake Error at CMakeLists.txt:4 (project):
Failed to run MSBuild command:

  MSBuild.exe

to get the value of VCTargetsPath:

  The system cannot find the file specified. 

cl : Command line warning D9002 : ignoring unknown option '-std=c++11'
qdldl.cpp
c\qdldl/include/qdldl.h(5): fatal error C1083: Cannot open include file: 'qdldl_types.h': No such file or directory
error: command 'C:\Program Files\Microsoft Visual "

More details at qpsolvers/qpsolvers@8016a01#commitcomment-60090952

This looks similar to this SO question but it should have been fixed with the pip wheels. 🤔

Any insight as to what is causing this build failure?

Compile error with Windows ninja build

The OSQP library and related QDLDL library are renaming the static library target to have the same name as the shared target. This is fine on Linux, since shared and static libraries have different extensions. On Windows, static libraries have a .lib extension, while shared libraries have a .dll extension, but also produce a .lib file that contains linking information. (Linux and OSX don't have this second linker file. They just use the .so or .dylib file.) Renaming to have the same name between static and shared results in a name conflict. Before this error was being silently ignored.

This is a cross-post of an issue on the tesseract_planning repository which has more information provided by the author of the issue.

Implicit permutation

Hello,

Are there any plans to implement support for a permutation in QDLDL? It's often beneficial to precompute a sparsity-promoting ordering (e.g. with AMD or METIS) but it's costly to permute the matrix explicitly, especially when solving a sequence of systems. However, it should be possible to take the permutation into account while factorizing.

Thanks.

Minor compilation warnings

The following variables are unused:

https://github.com/oxfordcontrol/qdldl/blob/4d9bf78e9efb5b84b9cf394c617afee2f04f3ab1/tests/test_rank_deficient.h#L11
https://github.com/oxfordcontrol/qdldl/blob/4d9bf78e9efb5b84b9cf394c617afee2f04f3ab1/tests/test_sym_structure.h#L11
https://github.com/oxfordcontrol/qdldl/blob/4d9bf78e9efb5b84b9cf394c617afee2f04f3ab1/tests/test_tril_structure.h#L11

etree counting error for very large matrices

If QDLDL is compiled without long integer types, then it is possible for the elimination tree calculation to return a negative or otherwise incorrect non-zero count due to integer overflow when the matrix being factored is very large.

The etree function should be modified to ensure that the Lnz count is monotonically increasing and non-negative in etree to protect against overflow.

This problem manifests itself in particular on QPLIB 9008.

Release v0.1.3

Hello everyone. It looks like there was a 0.1.3 release, but https://github.com/oxfordcontrol/qdldl/releases doesn't show it. I think that's because it was created using a branch https://github.com/oxfordcontrol/qdldl/tree/release-0.1.3 instead of a tag https://github.com/oxfordcontrol/qdldl/tags.

I'm able to work around it by using pin to b145d78 on master, but I thought I'd post in case you'd want to tidy it up.

[openSUSE linux] libqdldl.a does not contain a non-empty .text section. The archive was not created with -ffat-lto-objects option.

Hello,
I'm trying to package qdldl to openSUSE Linux.

When I am trying to compile it, RPMLINT warn me about the error as seen below.

E: lto-no-text-in-archive (Badness: 10000) /usr/lib64/libqdldl.a
 This archive does not contain a non-empty .text section.  
The archive was not created with -ffat-lto-objects option.

I don't really understand this error myself, but some documentation here.
https://en.opensuse.org/openSUSE:LTO#LTO_enablement_in_openSUSE:Factory

The documentation suggest adding %global _lto_cflags %{?_lto_cflags} -ffat-lto-objects but openSUSE maintainer suggest that it should be fix upstream.
Here is some more documentation on LTO
https://gcc.gnu.org/onlinedocs/gccint/LTO-Overview.html

Here is a openSUSE package building log: https://build.opensuse.org/package/live_build_log/home:andythe_great/qdldl/openSUSE_Tumbleweed/x86_64

Thanks.

Cannot install by py for python 3.10

once run the code

pip install cvxpy

get the error, the error note is too mess so do not display them.

Noticed that, with a python 3.9 environment can successful instll, but python 3.10 cannot

interop issues with QDLDL_bool and C++

I know I'm responsible for suggesting this, but I realized there's a design issue with

// Use bool for logical type if available
#if __STDC_VERSION__ >= 199901L
typedef _Bool QDLDL_bool;
#else
typedef int   QDLDL_bool;
#endif

in qdldl_types.h. If you include qdldl.h from C++, the second case will be hit regardless of how qdldl was compiled. I think the logic behind this compiler check is flawed, because it's impossible to know at header include time which C compiler was used for qdlql. I did a bit of searching and it seems like there's no good solution for an interoperable boolean type between C and C++. Fortunately QDLDL_bool does very little in the header, it's just used for allocating a work vector. It would be safe to move this C99 check into the source file and use another type in the header. I also tried

typedef char QDLDL_bool;

and this seems to work fine and accomplish the goal of a 1-byte type that can store 0/1 values.

compile error issue

-- Configuring done
-- Generating done
-- Build files have been written to: /home/ugv/software/osqp-eigen-master/build
ugv@ugv-ThinkPad-S2:~/software/osqp-eigen-master/build$ make -j8
Scanning dependencies of target OsqpEigen
[ 25%] Building CXX object CMakeFiles/OsqpEigen.dir/src/Solver.cpp.o
[ 50%] Building CXX object CMakeFiles/OsqpEigen.dir/src/Settings.cpp.o
[ 75%] Building CXX object CMakeFiles/OsqpEigen.dir/src/Data.cpp.o
/home/ugv/software/osqp-eigen-master/src/Solver.cpp: In constructor ‘OsqpEigen::Solver::Solver()’:
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:16:18: error: ‘make_unique’ is not a member of ‘std’
m_settings = std::make_uniqueOsqpEigen::Settings();
^
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:16:54: error: expected primary-expression before ‘>’ token
m_settings = std::make_uniqueOsqpEigen::Settings();
^
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:16:56: error: expected primary-expression before ‘)’ token
m_settings = std::make_uniqueOsqpEigen::Settings();
^
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:17:14: error: ‘make_unique’ is not a member of ‘std’
m_data = std::make_uniqueOsqpEigen::Data();
^
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:17:46: error: expected primary-expression before ‘>’ token
m_data = std::make_uniqueOsqpEigen::Data();
^
/home/ugv/software/osqp-eigen-master/src/Solver.cpp:17:48: error: expected primary-expression before ‘)’ token
m_data = std::make_uniqueOsqpEigen::Data();
^
make[2]: *** [CMakeFiles/OsqpEigen.dir/src/Solver.cpp.o] Error 1
make[1]: *** [CMakeFiles/OsqpEigen.dir/all] Error 2
make: *** [all] Error 2

[openSUSE] How to move file from /usr/lib/ to /usr/lib64?

Hello,
I'm trying to package qdldl to openSUSE Linux.
I found a files that went into /usr/lib as shown below.
I think that if I build for 64-bit, it should go to /usr/lib64.
Are there cmake flag I can add to make it go to /usr/lib64?

Thanks.

/usr/lib/cmake/qdldl/qdldl-config.cmake
/usr/lib/cmake/qdldl/qdldl-targets-relwithdebinfo.cmake
/usr/lib/cmake/qdldl/qdldl-targets.cmake

Compile error on raspberrypi

Hi,

I am trying to install a python package, which depends on osqp, which in turn depends on qdldl. However, I can not get it to compile in my Docker container on Raspberry Pi.
I get the following error:

      arm-linux-gnueabihf-gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O2 -Wall -g -fstack-protector-strong -Wformat -Werror=format-security -g -fwrapv -O2 -g -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -Ic -Ic/qdldl/include -I/usr/local/lib/python3.8/dist-packages/pybind11/include -I/usr/local/lib/python3.8/dist-packages/pybind11/include -I/usr/include/python3.8 -c cpp/wrapper.cpp -o build/temp.linux-armv7l-3.8/cpp/wrapper.o -O3 -std=c++11
      arm-linux-gnueabihf-gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O2 -Wall -g -fstack-protector-strong -Wformat -Werror=format-security -g -fwrapv -O2 -g -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -Ic -Ic/qdldl/include -I/usr/local/lib/python3.8/dist-packages/pybind11/include -I/usr/local/lib/python3.8/dist-packages/pybind11/include -I/usr/include/python3.8 -c cpp/qdldl.cpp -o build/temp.linux-armv7l-3.8/cpp/qdldl.o -O3 -std=c++11
      cpp/qdldl.cpp: In constructor ‘qdldl::Solver::Solver(QDLDL_int, QDLDL_int*, QDLDL_int*, QDLDL_float*)’:
      cpp/qdldl.cpp:34:41: error: cannot convert ‘QDLDL_int*’ {aka ‘int*’} to ‘const long long int*’
         34 |  QDLDL_int amd_status = amd_l_order(nx, Ap, Ai, P, NULL, NULL);
            |                                         ^~
            |                                         |
            |                                         QDLDL_int* {aka int*}
      In file included from cpp/qdldl.hpp:3,
                       from cpp/qdldl.cpp:1:
      c/amd/include/amd.h:63:28: note:   initializing argument 2 of ‘long long int amd_l_order(long long int, const long long int*, const long long int*, long long int*, c_float*, c_float*)’
         63 |     const SuiteSparse_long Ap [ ],
            |     ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
      error: command 'arm-linux-gnueabihf-gcc' failed with exit status 1

I suspect this is related to Raspberry Pi's ARM architecutre, because on my local 64bit Ubuntu machine I experience no problem. To reproduce, my Dockerfile is as follows:

FROM ubuntu:20.10
ARG DEBIAN_FRONTEND=noninteractive

# Install binary packages so that not all pip packages have to be rebuilt.
RUN apt update -qq && \
        apt install -y -qq \
        python3-pip \
        python3-dev \
        python3-setuptools \
        python3-wheel \
        python3-numpy \
        python3-scipy \
	python3-cvxopt \
	python3-joblib

# Instal libraries for compiling from source.
RUN apt update -qq && \
        apt install -y -qq \
        libblas3 \
        liblapack3 \
        liblapack-dev \
        libblas-dev \
        gfortran \
        libatlas-base-dev \
        cmake \
        g++

RUN pip3 install osqp

Any thoughts how to resolve this?

Thanks,

Hylke

custom number types

If I understand the readme correctly (https://github.com/oxfordcontrol/qdldl#including-the-header), there's a bit of a design issue with the custom number types.

At the point when a user redefines these types when including the header, the library has already been compiled using some fixed set of integer types. Using different definitions at include time will just result in linking errors or crashes when compiler finds functions with unexpected argument types. The choice of number types needs to be a compile-time option, e.g., controlled by a config file or cmake config.

Another option is to automatically compile all reasonable combinations of integer/float types and expose them as, e.g., QDLDL_solve_float64_int64. This requires a bit more work but it would allow users to compile a binary that provides multiple precision options at runtime.

Missing documentation and for how to run the tests

The README doesn't describe how to run the unit tests (I had to look at the travis script). And then the tests unexpectedly don't build with cmake -DUNITTESTS=ON .., only with cmake -DUNITTESTS=ON -DCOVERAGE=ON ...

library output names

The name libqdldlstatic is a bit unusual. Why not output both libqdldl.(dynamic library extension) and libqdldl.(static library extension)? E.g., on linux libqdldl.so and libqdldl.a.

[Windows] Error in cmake

When I run cmake, I get the following error, which is apparently related to the version of visual studio and MS build tools. I installed several versions of these tools (2015, 2017, and the latest one - 2022), but the problem persists. What tools exactly do I need to build qdldl?

PS D:\git\qdldl\build> cmake ..
-- Building for: Visual Studio 17 2022
-- Selecting Windows SDK version 10.0.19041.0 to target Windows 10.0.19043.
CMake Error at CMakeLists.txt:10 (project):
  Failed to run MSBuild command:

    C:/Program Files (x86)/Microsoft Visual Studio/2022/BuildTools/MSBuild/Current/Bin/amd64/MSBuild.exe

  to get the value of VCTargetsPath:

    Microsoft (R) Build Engine version 17.0.0+c9eb9dd64 for .NET Framework
    Copyright (C) Microsoft Corporation. All rights reserved.

    Build started 31/01/2022 11:55:54.
    Project "D:\git\qdldl\build\CMakeFiles\3.22.2\VCTargetsPath.vcxproj" on node 1 (default targets).
    C:\Program Files (x86)\Microsoft Visual Studio\2017\BuildTools\Common7\IDE\VC\VCTargets\Microsoft.Cpp.Platform.targets(67,5): error MSB8020: The build tools for v143 (Platform Toolset = 'v143') cannot be found. To build using the v143 build tools, please install v143 build tools.  Alternatively, you may upgrade to the current Visual Studio tools by selecting the Project menu or right-click the solution, and then selecting "Retarget solution". [D:\git\qdldl\build\CMakeFiles\3.22.2\VCTargetsPath.vcxproj]
    Done Building Project "D:\git\qdldl\build\CMakeFiles\3.22.2\VCTargetsPath.vcxproj" (default targets) -- FAILED.

    Build FAILED.

    "D:\git\qdldl\build\CMakeFiles\3.22.2\VCTargetsPath.vcxproj" (default target) (1) ->
    (PlatformPrepareForBuild target) ->
      C:\Program Files (x86)\Microsoft Visual Studio\2017\BuildTools\Common7\IDE\VC\VCTargets\Microsoft.Cpp.Platform.targets(67,5): error MSB8020: The build tools for v143 (Platform Toolset = 'v143') cannot be found. To build using the v143 build tools, please install v143 build tools.  Alternatively, you may upgrade to the current Visual Studio tools by selecting the Project menu or right-click the solution, and then selecting "Retarget solution". [D:\git\qdldl\build\CMakeFiles\3.22.2\VCTargetsPath.vcxproj]

        0 Warning(s)
        1 Error(s)

    Time Elapsed 00:00:00.28


  Exit code: 1



-- Configuring incomplete, errors occurred!

I have Windows 10 and Python 3.10.2 (latest version).