◆ Rust · linear algebra for statistics

Update the fit, don't start over.

QR and Cholesky factors updated when a row, a column or a rank-1 term arrives or leaves; randomized and truncated SVDs; ARPACK-style eigensolvers with shift-invert — over any operator you can multiply by. Pure Rust, generic in the scalar, 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

Four entry points, one operator trait

Not a dense LAPACK and not a statistics package: the factorizations and Krylov methods that statistical computing needs when refitting from scratch is the cost to avoid. Every matrix argument is a LinearOperator — a dense block, a sparse matrix, a closure or your own type.

↻

Qr and Cholesky with updates

A thin QR with explicit Q and five updates (insert or delete a row or a column, rank-1 A + u vᵀ; Hammarling & Lucas, DGKS reorthogonalization); a Cholesky factor with LINPACK's update and downdate. A failed operation — an indefinite downdate, a dependent column — leaves the factor bit for bit as it was.

≈

rsvd and svds

The randomized SVD of Halko, Martinsson & Tropp, reproducible from a seed on every platform; a truncated SVD by thick-restart Golub–Kahan–Lanczos bidiagonalization with full reorthogonalization on both sides, every value within (τ + 8·ncv·u)·σ₁ of a singular value.

λ

eigsh and eigs

One Krylov–Schur engine for the symmetric and the general problem, with ARPACK's which vocabulary, convergence test and scipy's defaults; locking of converged Schur blocks; conjugate pairs never split; exactly k values, as scipy returns them.

σ

Shift-invert

eigsh_near and eigs_near on (A − σI)⁻¹, factorized by the LBLᵀ or the Lu of xingo-sparse, with one step of iterative refinement per solve; the symmetric driver also returns how many eigenvalues lie below σ, from the inertia (Sylvester's law).

MatRefQr::insert_rowQr::delete_rowQr::rank1_updateCholesky::downdateLinearOperatorfrom_fnrsvdrange_findersvdseigsheigseigsh_nearcount_belowStatlaError

Generic in the Real trait of xingo-sparse: f64 by default, and the double-double of xingo-extprec (about 32 digits) without extra code. The only runtime dependency is xingo-sparse, with no dependency of its own.

Stated, then measured

Each chapter states an acceptance criterion and the tests enforce it. The constants of the bounds were measured and fixed with a margin — they are not theorems. The numbers come from the decision log of the solver this crate belongs to.

Worst measured, as a fraction of the criterion

Each bar is the worst case the tests measured, divided by the bound they enforce (named at the right): backward errors and orthogonality in units of n·u or m·u, residuals in units of ncv·u times the norm, the randomized SVD as the mean over 40 seeds against the expected-error bound of Halko, Martinsson & Tropp.

criterionworst measured
0 criterion Cholesky bwd c_H = 8 QR orth. c_Q = 16 QR bwd c_Q = 16 rsvd (mean) HMT bound svds resid. c_G = 8 eigs resid. c_K = 8 shift-inv. resid. c_K = 8 shift-inv. solve 2u

Without the refinement step, the residual of shift-invert reached 114·ncv·u and the backward error of a solve 526u: far outside the criterion, which is why the step is always on.

Against the references

Largest disagreement with an independent answer, where the criterion applies.

WhatReferenceCriterionWorst
svds valuescertified construction10⁻¹³ σ₁3.6 × 10⁻¹⁵ σ₁
svds valuesscipy svds10⁻¹⁰ rel.2.0 × 10⁻¹⁵
eigsh, eigs, shift-invertARPACK (scipy)10⁻¹⁰ rel.9.2 × 10⁻¹⁴
count_belowdense countequalequal
windowed regression, 2 000 stepsrefit from scratch—2.6 × 10⁻¹⁴ (QR)
svds in double-doublecertified construction—4 × 10⁻³²

The eigenvalue criterion applies where the gap to the rest of the spectrum is at least 10⁻⁶‖A‖; the svds one where it is at least 10⁻⁸σ₁. The error of svds is absolute: small singular values carry ε σ₁.

⇄

Updates that come back

update then downdate returns the Cholesky factor to within 4.9·n·u at n = 3 and 0.05·n·u for n ≥ 50, over condition numbers from 10 to 10¹², in f64 and double-double.

🔒

Transactional

Every failure of an update is detected before the first write, or computed on copies: the tests compare the factor bit for bit after every error path, in both scalars.

🎲

Random, reproducibly

Starting vectors and sketches come from the crate's own xoshiro256++ and polar method, with a logarithm written in + − · / (proven to 6.4u in f64): a seed gives the same bits everywhere.

Written as a book

Every module is a chapter: purpose, notation, the algorithm in numbered steps, invariants, the measured constants, divergences from the references, references. The crate documentation is the text, every chapter included (docs.rs builds it with the private items, where the chapters live), starting at Chapter 12.

§

Invariants that run

Each invariant of a chapter is a debug_assert! or a check_invariants(); property-based tests replay them against matrices accumulated in double-double.

🧾

Deterministic

Fixed loop orders, no threads, no libm, no rand: the generator, the Krylov drivers and the small dense solvers are fixed sequences of IEEE operations. The first 64 deviates of seed 0 are pinned by a test.

ℝ

Generic in the scalar

Every algorithm needs only + − · /, sqrt, abs and the order, so Qr<DoubleDouble> or eigsh in double-double exist without one line of extra code.

⚠️

Errors, not panics

One #[non_exhaustive] StatlaError; no function panics on bad input. Non-convergence is an error unless allow_partial asks for the converged part.

🦀

No unsafe, no C

#![forbid(unsafe_code)]. The one dependency, xingo-sparse, is pure Rust; the optional faer feature brings faer (MIT). Nothing GPL or LGPL is used or linked.

📄

Read, not copied

ARPACK, LAPACK and scipy were the references and, through scipy, the test oracle; the code is written from the papers: LINPACK, Saunders, Hammarling–Lucas, DGKS, Halko–Martinsson–Tropp, Golub–Kahan, Baglama–Reichel, Stewart, Francis, Bai–Demmel.

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-statla
$ cargo add xingo-sparse --no-default-features   # DenseBlock, CscMatrix
$ cargo add xingo-statla --features faer        # FaerDense as the kernel
// y = 1 + 2 s, the window moves by one observation
use xingo_statla::{MatRef, Qr, QrOptions};

let x = [1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 2.0, 3.0];
let mut qr = Qr::factor(
    MatRef::new(4, 2, 4, &x)?, &QrOptions::default())?;
qr.delete_row(0)?;
qr.insert_row(3, &[1.0, 4.0])?;

let y = [3.0, 5.0, 7.0, 9.0];
let mut beta = [0.0; 2];
qr.solve_least_squares(&y, &mut beta)?;   // (1, 2)
// T = tridiag(−1, 2, −1), stored: 3 nearest σ = 1
use xingo_statla::{EigsOptions, eigsh_near};

let t = CscMatrix::from_triplets(n, n, &entries)?;
let (near, below) =
    eigsh_near(&t, 3, 1.0, &EigsOptions::default())?;
assert_eq!(below, 33);  // λ below σ
// λ₃₄ ≈ 1.026, λ₃₃ ≈ 0.964, λ₃₅ ≈ 1.088

// or matrix-free: any closure y ← A x
let mut op = from_fn(n, n,
    |x: &[f64], y: &mut [f64]| { … });
let top = eigsh(&mut op, 4,
    Which::LargestAlgebraic, &EigsOptions::default())?;

Two programs ship with the crate: cargo run --release --example accuracy prints the tables behind the constants of the updatable factorizations, and windowed_regression runs 2 000 steps of a sliding-window fit against refitting from scratch.

How it was verified

What was checked before 0.1, and against what.

🎯

Certified references

The matrices a sequence of updates defines are accumulated in double-double; the svds references are built in double-double from prescribed spectra and rounded once, so their singular values are known to u‖A‖_F, and cross-checked by a Jacobi SVD in double-double.

📦

ARPACK as oracle

Six Matrix Market matrices of order 200 to 400 — symmetric and nonsymmetric random, 2-D Laplacian, graded tridiagonal, convection–diffusion, a rectangle — generated by a committed script, with ARPACK's answers from scipy 1.18.1 committed as fixtures. Nothing downloaded.

🧬

Mutation testing

Defects planted on purpose: 7 of 8 caught for the factorizations, 9 of 11 for the SVDs, 13 of 14 for the eigensolvers, and three more planted by the maintainer, all caught. The survivors are named below when they matter.

🐞

Defects caught

The tests found a Jacobi SVD that rotated an underflowed column forever, rotations drifting from orthogonality, a symmetric projection that would not converge near zero with tol = 0, and a loss of orthogonality of u per restart. All fixed before release.

ℝ²

Two scalars

The suite of the updatable factorizations runs in full in f64 and in double-double; rsvd, svds, eigsh, eigs and eigsh_near have smoke tests in double-double.

💻

Platforms

The suite ran on macOS aarch64, in debug and release, on stable and on Rust 1.90, and as WebAssembly under wasmtime on the same machine; it was compiled for i686 Linux. The CI of this repository adds x86_64 Linux and Windows, aarch64 Linux, i686, s390x (big-endian, under QEMU) and WebAssembly (wasmtime).

Known limitations of 0.1

What is still open, each in one sentence. The ones that can be closed have an issue.

The refinement of shift-invert was not tested with σ very close to an eigenvalue, where one step may not suffice (#1).
No matrix above 400 × 400 and no strongly non-normal matrix was tested for the eigensolvers, so the coupling check before locking a Schur block is untested defense code (#2).
Interior which without shift-invert (SM on an indefinite matrix, SI on a complex spectrum) may not converge, as with ARPACK; use eigsh_near or eigs_near.
Shift-invert of a symmetric matrix factorizes up to twice until xingo-sparse gains an indefinite form (xingo-sparse#8).
Shift-invert keeps a copy of A − σI for the refinement, which doubles the memory of the matrix (#3).
s390x runs in CI under emulation (QEMU), not on hardware; no x86_64 CPU without SSE2 or with AVX-512 was tried.
The literature in the chapters is cited from memory, including ARPACK's tie order, which was checked only against scipy's answers (#4).
The bound of the generator's logarithm in double-double is measured, not proven (in f64 it is proven) (#5).
The updatable factorizations were tested on random matrices with n ≤ 200 only, not on graded or badly scaled ones, and their guard against an underflowing Cholesky diagonal is never reached by a test (#6).
eigs_near in double-double, svds with both dimensions near 2 000 and the faer kernel beyond one test were not tested (#7).
No timing is claimed: nothing was timed on an idle machine (#8).

Authorship, credits and disclaimer

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

✍️

Authorship

xingo-statla is written and maintained by André Leite as part of the Xingó project, developed at StrategicProjects. It is developed inside the Xingó monorepo and mirrored, at every release, to its own repository, where issues and pull requests are welcome. To cite it, use the Zenodo DOI or the repository's CITATION.cff.

⚖️

Disclaimer

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

🙏

Credits

The algorithms are those of their authors, implemented here from the published descriptions. Each chapter of the sources lists its references.

  • LINPACK dchud/dchdd (Dongarra, Bunch, Moler & Stewart) and Saunders — Cholesky update and downdate
  • Hammarling & Lucas — updating the QR factorization
  • Daniel, Gragg, Kaufman & Stewart — Gram–Schmidt with reorthogonalization
  • Halko, Martinsson & Tropp — the randomized SVD
  • Golub & Kahan — bidiagonalization
  • Baglama & Reichel — thick-restart Lanczos bidiagonalization
  • Stewart — the Krylov–Schur algorithm
  • Francis — the double-shift QR algorithm
  • 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 — references and, through scipy, the test oracle
  • xingo-sparse — the factorizations of shift-invert; xingo-extprec — the double-double of the tests