xingo-statla
Website: https://strategicprojects.github.io/xingo-statla/ (overview, measured accuracy, limitations, API reference).
Updatable and matrix-free linear algebra for statistics, in pure Rust:
a thin QR and a Cholesky factor that are updated when a row, a column
or a rank-1 term arrives or leaves instead of being recomputed; the
randomized SVD of Halko, Martinsson & Tropp and a truncated SVD by
Golub–Kahan–Lanczos bidiagonalization; and ARPACK-style eigsh/eigs by
Krylov–Schur restarted Lanczos/Arnoldi, with shift-invert over sparse
factorizations — all over a small linear-operator trait, so the matrix can
be a dense block, a sparse matrix or a closure. It belongs to
Xingó, a linear and
mixed-integer programming solver, but depends on nothing in it except its
sparse linear algebra crate
xingo-sparse (pure Rust).
Statistical computing keeps asking questions that a dense library answers only by starting from scratch:
- A row arrived (or left); what is the new least-squares fit? —
Qr::insert_row/delete_rowinO(mn)instead of a refactorization inO(mn²)(sequential and windowed regression, recursive least squares, leave-one-out). - A covariance or information matrix changed by
± x xᵀ; what is its new Cholesky factor? —Cholesky::update/downdateinO(n²), and a downdate that would leave the matrix indefinite is refused before the factor is touched. - What are the leading
ksingular triplets of a matrix I can only multiply by? —rsvd(randomized, reproducible bit for bit from a seed) andsvds(deterministic, accurate toε σ₁on every value). - What are
keigenvalues at one end of the spectrum, or nearestσ, of a large sparse or implicit operator? —eigsh/eigswith ARPACK'swhichvocabulary, andeigsh_near/eigs_nearby shift-invert, with the count of eigenvalues belowσfrom the inertia of the symmetric factorization.
Every algorithm needs only + − · /, sqrt, abs and the order of the
scalar, so the whole crate is generic in the Real trait of xingo-sparse:
f64 by default, and the double-double of
xingo-extprec (about 32
digits) without one line of extra code.
It is not a dense LAPACK (see faer
for that: the dense eigensolvers here are small internal routines for the
projected problems), has no complex scalar type (eigs returns complex
eigenvalues as pairs of reals), and solves standard eigenproblems only, not
generalized ones (see "Scope" below).
Four entry points
1. Qr and Cholesky with updates — the thin Q is kept explicitly
and the five updates of Hammarling & Lucas (insert or delete a row or a
column, rank-1 A + u vᵀ) keep it orthonormal by Givens rotations and
DGKS reorthogonalization; the Cholesky update and downdate are LINPACK's
dchud/dchdd. A failed operation leaves the factor bit for bit as it
was.
use ;
// y = 1 + 2 s, observed at s = 0, 1, 2, 3; the columns are (1, s),
// stored column-major.
let x = ;
let mut qr = factor?;
// The window moves: the oldest observation leaves, s = 4 arrives.
qr.delete_row?;
qr.insert_row?;
let y = ; // at s = 1, 2, 3, 4
let mut beta = ;
let residual = qr.solve_least_squares?;
assert!;
assert!;
assert!; // ‖QᵀQ − I‖ ≤ 16 m u
# Ok::
use ;
// A = [4 2 0; 2 5 1; 0 1 3], symmetric positive definite.
let a = ;
let mut chol = factor?;
let before = chol.upper.to_block.data;
// A + x xᵀ, then back: the factor returns to within a few ulps.
let x = ;
chol.update?;
let info = chol.downdate?;
assert!; // 1 − ‖R⁻ᵀx‖², the distance to indefiniteness
for in before.iter.zip
// A − 10 x xᵀ is indefinite: refused, and the factor is untouched.
let snapshot = chol.upper.to_block.data;
let big = x.map;
assert!;
assert_eq!;
# Ok::
2. rsvd and svds — the randomized SVD (Gaussian or Rademacher
sketch, oversampling p = 10, q = 2 power iterations, re-orthonormalized
at every half step) has the expected error of Halko, Martinsson & Tropp,
and its random numbers come from the crate's own xoshiro256++, so a seed
gives the same bits on every platform. svds is a thick-restart
Golub–Kahan–Lanczos bidiagonalization with full reorthogonalization on both
sides: every returned value is within (τ + 8·ncv·u)·σ₁ of a singular
value.
use ;
use DenseBlock;
// A 60 × 40 matrix with singular values 5, 4, 3, 2, 1 and the rest zero.
let mut a = zeros;
for in .into_iter.enumerate
let t = svds?;
for in t.s.iter.zip
// Exactly rank 5: the randomized SVD recovers it to rounding.
let r = rsvd?;
assert!;
// Same seed, same bits.
let again = rsvd?;
assert_eq!;
# Ok::
3. eigsh and eigs — one Krylov–Schur engine (Stewart 2001) for the
symmetric and the general problem, with ARPACK's which (LM SM LA SA BE
and LM SM LR SR LI SI), its convergence test ‖r‖ ≤ tol·max(ε^{2/3}, |θ|), scipy's defaults, locking of converged Schur blocks, and conjugate
pairs never split. The operator can be a closure: here the second
difference matrix of order 100, never formed.
use ;
let n = 100;
// y = T x with T = tridiag(−1, 2, −1); λ_j = 2 − 2 cos(jπ/(n + 1)).
let mut t = from_fn;
let top = eigsh?;
for in top.values.iter.enumerate
assert_eq!;
# Ok::
use ;
// Block diagonal with blocks [a −1; 1 a], a = 0, 0.1, …, 4.9: the
// eigenvalues are a ± i; the largest real part is the pair 4.9 ± i.
let n = 100;
let mut a = from_fn;
let e = eigs?;
assert!;
assert!;
# Ok::
4. Shift-invert — eigsh_near and eigs_near run the same engine on
(A − σI)⁻¹ (ARPACK's mode 3), factorized by the LBLᵀ of
SupernodalLdl (symmetric) or the threshold Lu (general) of
xingo-sparse, with one step of iterative refinement per application so
that each solve is backward stable. The symmetric driver also returns how
many eigenvalues lie below σ — Sylvester's law of inertia, a completeness
check ARPACK does not offer.
use ;
use ;
// The same T = tridiag(−1, 2, −1), now stored (only the lower triangle is read).
let n = 100;
let mut entries = Vecnew;
for i in 0..n
let t = from_triplets?;
let = eigsh_near?;
// λ_j < 1 ⇔ j < (n + 1)/3: 33 eigenvalues lie below σ = 1.
assert_eq!;
let lambda = ;
// Nearest σ first: λ_34 ≈ 1.026, λ_33 ≈ 0.964, λ_35 ≈ 1.088.
for in near.values.iter.zip
# Ok::
Every matrix argument is a LinearOperator (and an AdjointOperator for
the SVDs): DenseBlock, the borrowed column-major view MatRef,
CscMatrix and CsrMatrix of xingo-sparse, a closure through
from_fn/from_fns, or your own type. The programs in
examples/ are accuracy (the measurements behind the
constants of the updatable factorizations; Markdown tables) and
windowed_regression (2 000 steps of a sliding-window fit, checked
against refitting from scratch).
Guarantees, and what was measured
Each guarantee is the stated criterion of a chapter of the sources, checked
by the test suite; the constants c_H, c_Q, c_G, c_K were
measured and then fixed with a margin, so they are not theorems. u
is the unit roundoff of the scalar (2⁻⁵³ for f64), n, m the
dimensions, ncv the Krylov dimension.
| what | criterion the tests enforce | worst measured |
|---|---|---|
Cholesky: backward error after any sequence of updates and downdates |
‖RᵀR − A_t‖_F ≤ 8·n·u·‖A_t‖_F (c_H = 8) |
4.0·n·u (at n = 1); ≤ 0.06·n·u for n ≥ 50 |
Cholesky: update then downdate (and back) |
within 10·n·u of the original factor |
4.9·n·u (n = 3); ≤ 0.05·n·u for n ≥ 50 |
Cholesky: forward error against a refactorization |
≤ 8·κ(A_t)·u per instance; ≤ 10⁻¹² where κ ≤ 10⁶ (maximum of 20 seeds, n = 100, 200) |
— |
Qr: orthogonality and backward error |
‖QᵀQ − I‖_F, ‖QR − A_t‖_F/‖A_t‖_F ≤ 16·m·u (c_Q = 16) |
8.0 and 5.4·m·u (on 2 × 1, 3 × 2); ≤ 0.6·m·u for m ≥ 100 |
Qr/Cholesky: a failed operation |
the factor unchanged, bit for bit | — |
rsvd: the HMT expected error |
the mean over 40 seeds below the bound | 0.19–0.63 of the bound (worst single run 0.66) |
svds: residual of every triplet |
‖(Av − σu; Aᵀu − σv)‖ ≤ (τ + 8·ncv·u)·σ₁ (c_G = 8) |
2.30·ncv·u·σ₁ |
svds: singular values, against a certified construction |
≤ 10⁻¹³·σ₁ where the gap is ≥ 10⁻⁸σ₁ |
3.6·10⁻¹⁵·σ₁ |
eigsh/eigs: residual of every pair |
‖Ay − θy‖ ≤ (τ + 8·ncv·u)·‖A‖ (c_K = 8) |
2.44·ncv·u·‖A‖ |
eigsh/eigs/shift-invert: eigenvalues, against ARPACK |
≤ 10⁻¹⁰ relative where the gap is ≥ 10⁻⁶‖A‖ |
9.2·10⁻¹⁴ |
shift-invert: residual on A |
as eigsh/eigs |
2.23·ncv·u·‖A‖ (114 without the refinement step) |
| shift-invert: backward error of each solve | ≤ 2u |
0.73u (up to 526u without refinement) |
svds against scipy.sparse.linalg.svds |
≤ 10⁻¹⁰ relative on the σᵢ ≥ 10⁻³σ₁ |
2.0·10⁻¹⁵ |
count_below of eigsh_near |
equal to the dense count | equal on every fixture |
The Cholesky and QR rows are over random matrices with prescribed
condition numbers κ from 10 to 10¹² (Haar-distributed singular
vectors), n ≤ 200, in f64 and in double-double. The svds rows are
over eleven matrices with prescribed spectra (geometric down to 10⁻¹⁴,
rank-deficient, clustered to 10⁻⁸, multiple values, 2000 × 200, wide,
sparse); the eigenvalue rows over six Matrix Market matrices of order 200
to 400 (symmetric random, 2-D Laplacian, graded tridiagonal,
convection–diffusion, nonsymmetric random, and a 300 × 200 rectangle for
svds), with ARPACK's answers from scipy committed as fixtures.
Two properties of the guarantees a user should know:
svdsand the symmetric eigenvalues are accurate in absolute terms. Small singular values carry an error of orderε σ₁, notε σᵢ(a relative test is unattainable for them and is not offered); for a general matrix the eigenvalue error is the residual times the eigenvalue's condition number.- A single-vector Krylov method can miss a copy of a multiple value:
the value returned is always within the bound of some singular value
or eigenvalue, but not necessarily of the
i-th when a multiplicity is missed — as in ARPACK.
And of the implementation:
- Errors, not panics. One
#[non_exhaustive]error type,StatlaError; no function panics on bad input. Non-convergence isErr(NoConvergence)unlessallow_partialasks for the converged part. - Deterministic, the same bits everywhere. The starting vectors and
sketches come from the crate's own generator (SplitMix64 → xoshiro256++
→ the polar method of Marsaglia & Bray, with a logarithm written in
+ − · /), never fromlibmorrand; loop orders are fixed; no threads. The first 64 deviates of seed 0 are pinned by a test, and changing them is a breaking change. - No
unsafe(#![forbid(unsafe_code)]) and no C.
Features
faer(off) — enables the feature of the same name ofxingo-sparse, whoseFaerDense(f64only) can then be the dense kernelKofCholesky<f64, FaerDense>andQr<f64, FaerDense>. It brings infaer(pure Rust, MIT).- Without it the only dependency is
xingo-sparsewithdefault-features = false, which has no dependency of its own.
Scope
In: MatRef/MatMut (column-major views with a leading dimension);
Cholesky (factor, update, transactional downdate, solves, determinant
as mantissa and exponent); the thin Qr with explicit Q and five
updates, least squares, the Q-less to_cholesky; the operator traits and
their implementations for dense, sparse and closures; rsvd and
range_finder; svds (the largest values); eigsh, eigs,
eigsh_near, eigs_near, ShiftInvert, SymShiftInvert.
Not in 0.1, and additive when they come: inserting or deleting a variable
of a Cholesky factor; the smallest singular values in svds
(SvdWhich is #[non_exhaustive] for them); a blocked (WY) Householder
QR for large factorizations; complex shifts.
Out, by decision: generalized eigenproblems A x = λ B x; complex
matrices; dense eigensolvers or SVDs as a public API (the small ones are
internal); rand or libm as dependencies.
How it was verified
- Exact or certified references. The matrices
A_tthat a sequence of updates defines are accumulated in double-double; thesvdsreferences are matrices built in double-double by Householder reflectors and rounded once, so their singular values are the prescribed ones tou‖A‖_F(Weyl), cross-checked against a one-sided Jacobi SVD in double-double; the eigenvalue references are ARPACK's answers throughscipy.sparse.linalg(scipy 1.18.1, numpy 2.5.5) on six matrices that a committed script generates (tests/data/make_fixtures.py; nothing downloaded); the inertia count is compared with a dense count. - Two scalars. The suite of the updatable factorizations runs in full
in
f64and in double-double;rsvd,svds,eigsh,eigsandeigsh_nearhave smoke tests in double-double (svdsvalues to4·10⁻³²). - Mutation testing. Deliberate defects were planted in the algorithms
and the suite was rerun: 7 of 8 caught for the factorizations, 9 of 11
for the SVDs, 13 of 14 for the eigensolvers, plus three more planted by
the maintainer, all caught. The survivors are listed as limitations
below when they matter (two of the SVD ones change nothing measurable:
the orthonormalization of the half step of the power scheme for
q ≤ 6, and a relative instead of absolute convergence test). - Defects found by the tests and fixed before release. In the
one-sided Jacobi SVD a column whose squared norm underflowed was rotated
forever, and the accumulated rotations drifted from orthogonality
(
1.3·10⁻¹⁴, now8·10⁻¹⁶); in Krylov–Schur the symmetric projected matrix had to be mirrored fortol = 0to converge nearθ = 0, and each restart lost aboutuof orthogonality cumulatively (85uin 30 restarts) until one Gram–Schmidt pass was added after it. - Platforms. The suite ran on macOS aarch64, in debug and release, on
stable and on Rust 1.90, and in release as
wasm32-wasip1under wasmtime on the same machine; the CI of the stand-alone repository runs it on x86_64 Linux and Windows, aarch64 Linux and macOS, i686 Linux, s390x Linux (big-endian, under QEMU, release only) andwasm32-wasip1(under wasmtime).
Known limitations
What is still open in 0.1, each in one sentence. The ones that can be closed have an issue.
- Shift-invert close to an eigenvalue: the refinement step was not
tested with
σwithinγ·u·‖A − σI‖of an eigenvalue, where one step may not suffice (the factorization usually fails there with a zero pivot) (#1). - Size and normality: no matrix above
400 × 400was tested for the eigensolvers (2000 × 200forsvds), nor any strongly non-normal matrix — the coupling check before locking a Schur block ineigsis defense code no test exercises (#2). - Interior
whichwithout shift-invert (SMon an indefinite matrix,SIon a complex spectrum) may not converge, as with ARPACK; useeigsh_near/eigs_near. - The symmetric shift-invert may factorize twice, because the
LBLᵀofxingo-sparseneeds the inertia declared in advance, until it gains an indefinite form (xingo-sparse#8). - Memory of the refinement: shift-invert keeps a copy of
A − σIbeside its factorization, which doubles the memory of the matrix (not measured on large matrices) (#3). - Hardware: s390x runs under emulation (QEMU), not on hardware, and no x86_64 CPU without SSE2 or with AVX-512 was tried.
- The literature in the chapters is cited from memory, including the
exact form of the HMT bound for
q > 0and ARPACK's tie order indngets, which was checked only against scipy's answers on the fixtures (#4). - The logarithm of the generator in double-double has a measured
bound (
2.7u, asserted16u), not a proven one; inf64it is proven (6.4u, measured3.5u) (#5). - The updatable factorizations were tested on random matrices with
n ≤ 200and Haar-distributed singular vectors only — not on graded or badly scaled matrices — and the guard against a new Cholesky diagonal underflowing to zero is defense code no test reaches (#6). - Not tested:
eigs_nearin double-double,svdswith both dimensions near 2 000 or with more than four restarts under heavy locking, and thefaerkernel beyond one test (#7). - No timing is claimed: nothing was timed on an idle machine (#8).
Design notes
- Literate. Every module is a chapter: notation, the algorithm in
numbered steps, invariants (each a
debug_assert!or acheck_invariants()), the measured constants, divergences from the references, references. The crate documentation is the text: start at the crate root on docs.rs (Chapter 12). Every chapter but the root is the documentation of a private module (the public items are re-exported at the root), so docs.rs builds with--document-private-items; private items are marked as such. Labels such as L3.4 are tasks of the plan of the Xingó solver, and D-xxxx entries of its decision log. - Read, not copied. ARPACK, LAPACK and scipy were the references and,
through scipy, the test oracle;
faerwas read for what it already offers; the defaults of scipy, scikit-learn, RSpectra andirlbathat the options follow are recalled, not checked. The code is written from the papers and includes no code from any of them. - Small and generic. Givens rotations, Householder reflectors, DGKS
Gram–Schmidt, one-sided and cyclic Jacobi, Hessenberg reduction, Francis
double-shift QR, Bai–Demmel block swaps and quasi-triangular
eigenvectors are written here, generic in
T: Real; the dense kernel ofxingo-sparseenters only the initial Cholesky factorization.
Minimum supported Rust version
1.90 (edition 2024), tested together with stable.
Repository, issues and citation
The crate is developed inside the Xingó monorepo
(StrategicProjects/xingo,
directory crates/statla), where every change is validated together with
the crates it depends on. The stand-alone repository,
StrategicProjects/xingo-statla,
is a read-only mirror of that directory (git subtree split, full
history), updated at every release; it exists so that the library can be
archived and cited on its own. Issues and pull requests about the crate are
welcome in either repository. Each release of the mirror is archived on
Zenodo, and CITATION.cff has the citation metadata.
Authorship, credits and disclaimer
xingo-statla is written and maintained by André Leite as part of the
Xingó project, developed at
StrategicProjects.
The algorithms are those of their authors, implemented here from the
published descriptions: LINPACK's dchud/dchdd (Dongarra, Bunch, Moler
& Stewart) and Saunders (the Cholesky update and downdate); Hammarling &
Lucas (the QR updates); Daniel, Gragg, Kaufman & Stewart (Gram–Schmidt
with reorthogonalization); Halko, Martinsson & Tropp (the randomized SVD);
Golub & Kahan (bidiagonalization) and Baglama & Reichel (its thick
restart); Stewart (the Krylov–Schur algorithm); Francis (the double-shift
QR); Bai & Demmel (swapping blocks of the real Schur form); Hestenes and
Demmel & Veselić (Jacobi methods); Blackman & Vigna (xoshiro256++);
Marsaglia & Bray (the polar method). ARPACK (Lehoucq, Sorensen & Yang),
LAPACK and scipy were the references and, through scipy, the test oracle.
Each chapter of the sources lists its references.
This is an independent project: it is not affiliated with, maintained by
or endorsed by the authors of ARPACK, LAPACK, scipy, numpy, faer,
RSpectra, irlba or scikit-learn, and it 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 licenses below.
License
Licensed under either of the Apache License, Version 2.0 or the MIT license, at your option.