QDLDL Factorization

0.1.9.post1 · active · verified Tue Apr 14

QDLDL is a Python wrapper for the QDLDL C library, providing a high-performance LDL factorization routine primarily for sparse matrices. It's designed for use in optimization and numerical methods, particularly for solving symmetric indefinite systems like those arising in KKT matrices. The current version is 0.1.9.post1, with updates released periodically to support newer Python versions, architectures, and upstream C library improvements.

Warnings

gotcha Older versions of `qdldl` (pre-0.1.7.post4) may not be compatible with NumPy 2.0 due to breaking changes in NumPy's API, potentially leading to build failures or runtime errors.
Fix: Upgrade `qdldl` to `0.1.7.post4` or newer: `pip install --upgrade qdldl`.
gotcha QDLDL is specifically optimized for sparse matrices and expects input matrices to be in the Compressed Sparse Column (CSC) format for optimal performance and correctness.
Fix: Ensure input matrices are in CSC format. If starting from another sparse format (e.g., CSR), convert using `matrix.tocsc()`.
gotcha Compatibility with newer Python versions is added incrementally. For example, version `0.1.9` added support for Python 3.14. Using an older `qdldl` with a very new Python interpreter, or vice-versa, might lead to installation issues or unexpected behavior.
Fix: Consult the `qdldl` release notes on GitHub for specific Python version compatibility. Ensure your Python environment is supported by the installed `qdldl` version, or upgrade `qdldl`.
gotcha The underlying C library of QDLDL uses `double` precision floating-point numbers. Users should be aware of potential floating-point inaccuracies inherent in numerical computations, especially when dealing with ill-conditioned matrices.
Fix: Consider the numerical stability of your problem and input data. For ill-conditioned systems, preconditioning or alternative solvers may be necessary.

Install

pip install qdldl Install stable version

Imports

qdldl
```
import qdldl
```
The library is typically imported directly as 'qdldl'.

Quickstart

This quickstart demonstrates how to factorize a sparse symmetric indefinite matrix (e.g., a KKT matrix) using `qdldl.qdldl` and then solve a linear system with the obtained factors using `qdldl.solve`. It uses `scipy.sparse.csc_matrix` for efficient sparse matrix representation.

import qdldl
import numpy as np
from scipy.sparse import csc_matrix

# Construct a sparse symmetric indefinite matrix, typically a KKT matrix.
# K = [ P  A.T ]
#     [ A   0  ]

# Example components:
P_data = np.array([2.0, 1.0, 1.0, 3.0])
P_row_ind = np.array([0, 0, 1, 1])
P_col_ind = np.array([0, 1, 0, 1])
P = csc_matrix((P_data, (P_row_ind, P_col_ind)), shape=(2, 2))

A_constr_data = np.array([1.0, 1.0, 1.0])
A_constr_row_ind = np.array([0, 1, 1])
A_constr_col_ind = np.array([0, 0, 1])
A_constr = csc_matrix((A_constr_data, (A_constr_row_ind, A_constr_col_ind)), shape=(2, 2))

n_P = P.shape[0]
n_A = A_constr.shape[0]
n = n_P + n_A

# Build the full KKT matrix
KKT = csc_matrix(
    (n, n),
    dtype=P.dtype
)
KKT[:n_P, :n_P] = P
KKT[:n_P, n_P:] = A_constr.T
KKT[n_P:, :n_P] = A_constr

# The 'd' argument for qdldl.qdldl is a user-defined initial diagonal for pivoting.
# A common choice is a vector of ones.
d = np.ones(n)

# Perform LDL factorization
# L_factor is a csc_matrix (lower triangular factor),
# D_diag is a numpy array (diagonal of D),
# P_vec is a numpy array (permutation vector).
L_factor, D_diag, P_vec = qdldl.qdldl(KKT, d)

# Solve a system KKT @ x = b
b = np.array([10.0, 20.0, 5.0, 8.0]) # Example right-hand side

# Use the qdldl.solve function to get the solution x
x = qdldl.solve(L_factor, D_diag, P_vec, b)

print("Input KKT matrix (dense representation for display):\n", KKT.toarray())
print("Right-hand side b:\n", b)
print("Solution x:\n", x)

# Verify the solution
print("KKT @ x:\n", KKT @ x)
print("Error (KKT @ x - b):\n", KKT @ x - b)
assert np.allclose(KKT @ x, b, atol=1e-9)
print("Solution verified.")

view raw JSON →