◆ Rust · sparse linear algebra

The factorizations an optimization solver cannot do without.

A dynamic LU for simplex bases with Forrest–Tomlin updates and hypersparse solves, our own AMD and COLAMD, scaling, and a regularized, refined KKT solver for interior-point methods. Pure Rust, written as a book, deterministic to the bit.

CI crates.io docs.rs MSRV 1.90 License MIT or Apache-2.0 No unsafe DOI

Three entry points, one layer

Not a general linear algebra library: no products, QR, SVD or eigenvalues. What is here is what a simplex method and an interior-point method need and the general libraries do not offer.

▤

The basis of a simplex method

A dynamic LU with threshold Markowitz pivoting (Suhl & Suhl), Forrest–Tomlin updates when one column changes, hypersparse FTRAN/BTRAN (Gilbert–Peierls reach, a density policy per call). The basis is never formed: it is a list of references into [A | ±I]. A reusable pivot sequence replays the last factorization on new values.

⇅

Fill-reducing orderings

Our own Amd (Amestoy, Davis & Duff) and Colamd (Davis, Gilbert, Larimore & Ng) on one approximate-minimum-degree engine over a quotient graph, behind the Ordering trait on a value-free Pattern. The elimination-tree postorder puts the heaviest child last, so supernodes merge.

◩

KKT systems of an interior-point method

KktSolver in the CHOLMOD shape: analyze once, factorize many, solve. Regularization (shifts in the equilibrated matrix, pivot bumping, inertia check) and GMRES refinement are the trait's provided methods, shared by every backend. The recommended backend is our own SupernodalLdl (relaxed supernodes, dense-kernel blocks, exact bump counts, no dependency); FaerLdl remains as the alternative and the oracle.

CscMatrix<T>CsrMatrix<T>SparseVec<T>Triplets<T>PatternBlockPartitionLu<T, U>ForrestTomlinSymbolicLuAmdColamdScalingKktSolverRegularizationRefinementSupernodalLdlFaerLdlDenseKernel

Every container and factorization is generic in the scalar T: Real (f64 by default; double-double and quad-double are planned in a sibling crate). Without the default faer feature the crate has no dependency at all; that is how the Xingó solver builds it.

Measured, not guessed

Each number below comes from the decision log of the solver this crate was built for, with the harness that produced it. The oracles (SuiteSparse, SuperLU/scipy, faer) are development dependencies only.

Fill of our AMD against SuiteSparse's

nnz(L) of the Cholesky factor, ours over SuiteSparse's, on the 93 Netlib normal equations A Aᵀ and Harwell–Boeing matrices. The acceptance line is 1.05.

ours / SuiteSparse1.05 acceptance
1.05 0.90 1.00 1.10 AMD, mean 0.999 AMD, worst 1.029 COLAMD, mean 1.000 COLAMD, worst 1.009

331 comparisons, none above 1.05. Factorization time of faer with our ordering: 0.98× faer's own AMD (geometric mean, ten largest Netlib); ordering time about 1.15× faer's since the engine moved to one garbage-collected workspace.

KKT systems at three stages of an interior-point method

93 Netlib LPs × normal equations and augmented system × a diagonal D at the start (10±0.5), the middle (10±4) and the end (10±8..10) of the method: 558 systems, default regularization and refinement, with either backend (FaerLdl and our SupernodalLdl give the same counts).

PropertySystems
Factorized with the expected inertia, no pivot bumped558 / 558
Residual against the unregularized K ≤ 10−10 after refinement558 / 558
Largest such residual9.4 × 10−11
Refinement steps, median / maximum2 / 10
Non-finite factors or solutions reported silently0
Stored factor of SupernodalLdl equal to faer's on the supernodal systems, smaller on the simplicial ones (same ordering)84 / 84 · 474 / 474
Factorization time of SupernodalLdl with faer's kernels, over FaerLdl (ten largest, geometric mean)1.02×
… with the dependency-free NaiveDense kernels, after the blocked loops of 0.31.37× (was 3.3×)
Unregularized augmented systems (Regularization::none(), Bunch–Kaufman + delayed pivots): nonsingular ones factorized with the expected inertia and residual ≤ 10−1049 / 49

Why it matters: a shift δ chosen in absolute units fails 32 of these systems at the end of the method; chosen in the equilibrated matrix it is relative to each row and fails none. The refinement removes the shifts' bias.

≡

Bit for bit

The LU is the one inside the Xingó simplex. Every change to this crate is accepted only if the solver's results on MIPLIB and Netlib instances are identical, key by key, outside timings.

⟳

Refactorization that reuses the pivots

A recorded pivot sequence replayed on new values: 1.8–2.3× faster on sparse bases, 1.2–1.5× on dense ones (it saves the analysis, not the arithmetic). Fallback to a fresh factorization when a pivot fails the threshold.

∅

No allocation in the loop

A second solve on the same factor and a refinement with a reused RefineWorkspace allocate nothing, measured with a counting allocator over 186 systems.

Written as a book

Every module is a chapter: purpose, notation, the algorithm in numbered steps, invariants, references. The crate documentation is the text, and Chapter 5 of the solver's book includes these sources verbatim.

§

Invariants that run

Each invariant of a chapter is a debug_assert! or a check_invariants(); property-based tests (proptest) replay them on random inputs, including the agreement between two constructions of the same object.

🧾

Deterministic

Same input, same options, same result, bit for bit: no hashing, no threads, no allocation-order dependence in the numerical paths. The faer backend runs sequentially for the same reason.

📄

Read, not copied

HiGHS, SuiteSparse (AMD, COLAMD, CHOLMOD) and faer were studied as references and oracles; the code is written from the papers: Suhl & Suhl, Forrest & Tomlin, Gilbert & Peierls, Amestoy–Davis–Duff, Altman & Gondzio, Arioli–Duff–Gratton–Pralet, Liu.

⚠️

Errors, not panics, on data

Malformed containers, singular bases, wrong inertia and non-finite factors come back as errors carrying what the caller needs to recover. Panics are reserved for contract violations such as a vector of the wrong length.

🦀

No unsafe, no C

unsafe_code is denied in the crate. The only dependency, faer (MIT), is pure Rust and optional; nothing GPL or LGPL is used or linked, and there is no C binding to build.

🔁

Analyze once, factorize many

The symbolic phase of the KKT solver and the pivot sequence of the LU are computed once per pattern and reused while only the values change, which is every iteration of either method.

Install & run

Rust 1.90 or later. The README's examples are compiled as doc-tests, so they cannot drift from the API; changes between versions are in the changelog.

$ cargo add xingo-sparse                        # with faer's kernels
$ cargo add xingo-sparse --no-default-features  # no dependency
// a simplex basis: factorize, solve, exchange one column
use xingo_sparse::{Col, ColumnRef, Lu, LuFactor,
    Row, Sign, SparseVec};

let mut heading = vec![ColumnRef::Structural(Col(0)),
                       ColumnRef::Logical(Row(1), Sign::Plus)];
// Forrest–Tomlin is the default update
let mut lu = Lu::<f64>::default();
lu.factorize(&(heading.as_slice(), &a))?;

let mut x = SparseVec::from_dense(&[4.0, 5.0]);
lu.ftran(&mut x);                 // x = B⁻¹ b

lu.ftran_for_update(&mut alpha);  // the entering column
// Updated, or RefactorNeeded
lu.update(1, alpha.get(1))?;
// an ordering and the fill it yields
use xingo_sparse::{Amd, Natural, Ordering, OrderingTarget};

let s = a.pattern();                   // values dropped
let p = Amd::default()
    .order(&s, OrderingTarget::Symmetric)?;
let nnz_l = s.cholesky_nnz(&p)?;       // Liu's row subtrees

// the same, in the natural order, for comparison
let q = Natural.order(&s, OrderingTarget::Symmetric)?;
assert!(nnz_l <= s.cholesky_nnz(&q)?);

Three complete programs ship with the crate: cargo run --example basis_lu, ordering and kkt_ipm_step. Each ends in a check of its own result.

Known limitations of 0.3

Each one is measured and recorded, with the measurement, in the solver's decision log. They are the next releases' work, not surprises.

SupernodalLdl factorizes an unregularized augmented system with Bunch–Kaufman 1×1/2×2 pivots inside each supernode and delayed pivots (MA57's scheme). On raw Netlib most such systems are singular to working precision (dependent and empty rows): of the 279, 49 are nonsingular and all 49 factorize with the expected inertia and a residual ≤ 10−10; the rest get an explicit error. Delays pile up where the system is singular anyway (up to 15 352 in one end-of-method system); use the regularized path there.
The default regularization (ρ = 10−6, δ = 10−8 in the equilibrated matrix) was calibrated on Netlib, 558 systems plus 3 × 558 with other random diagonals; one of those extra systems reached 1.6 × 10−10 with the default refinement. A running interior-point method will review ρ, δ.
Our AMD takes about 1.15× the time of faer's with the same fill.
FaerLdl's count of bumped pivots is exact for simplicial factors; for supernodal ones, negative-sign bumps are counted by value and may be overcounted (faer counts the positive ones only). SupernodalLdl counts both signs exactly.
The LU declares singular a column whose entries are all at or below the absolute pivot tolerance (10−10) without scaling; sherman3 needs Scaling first. Refactorization speeds up dense factors less than 1.5×.
Bartels–Golub updates are specified in the crate's contract and scheduled next. Nested dissection was measured against METIS (external tool, 40 KKT systems: our AMD's fill is 0.97× on average, 1.63× at worst) and not adopted.

Authorship, credits and disclaimer

Who wrote this, whose work it stands on, and what it does not claim.

✍️

Authorship

xingo-sparse is written and maintained by André Leite as the linear algebra layer of the Xingó solver, developed at StrategicProjects. To cite it, use the Zenodo DOI or the repository's CITATION.cff.

🙏

Credits

The algorithms are those of their authors, implemented here from the published papers: Suhl & Suhl (LU for simplex bases), Forrest & Tomlin (basis updates), Gilbert & Peierls and Hall & McKinnon (hypersparse solves), Amestoy, Davis & Duff (AMD), Davis, Gilbert, Larimore & Ng (COLAMD), Liu (elimination trees), Bunch & Kaufman and Duff & Reid (symmetric indefinite pivoting, delayed pivots, MA57), Altman & Gondzio and Arioli, Duff, Gratton & Pralet (regularization and refinement). HiGHS, SuiteSparse (AMD, COLAMD, CHOLMOD) and faer were studied as references and used as oracles in the tests; faer (MIT) is also the optional dense-kernel dependency. Each chapter of the sources lists its references.

⚖️

Disclaimer

This is an independent project. It is not affiliated with, maintained by or endorsed by the HiGHS, SuiteSparse, HSL or faer authors, and includes no code from them (faer is linked only through the optional faer feature). All names and trademarks belong to their owners. The software is provided "as is", without warranty of any kind, under the terms of the MIT and Apache-2.0 licenses.