Skip to main content

Crate xingo_statla

Crate xingo_statla 

Source
Expand description

§Chapter 12 — xingo-statla: updatable and matrix-free linear algebra for statistics

Status: complete for v0.1 (tasks L3.2, L3.3 and L3.4). The contract of the crate was ratified on 2026-11-19 (decision log of the Xingó solver, D-0127) and amended by what the implementation measured (D-0132, D-0134, D-0135); where they differ, this text and the code are authoritative. Labels such as L3.2 are tasks of the solver’s plan, D-xxxx are entries of its decision log, and names such as l34-tables.md are the working notes of a task in the monorepo (not part of the package; the numbers that matter are quoted where they are used). L3.2 implemented the updatable factorizations: the dense views MatRef/MatMut, the error type StatlaError (Chapter 12.0), Cholesky with rank-1 update and transactional downdate (Chapter 12.2) and the thin Qr with explicit Q and five updating operations (Chapter 12.3). L3.3 added the matrix-free part: the operator traits LinearOperator/AdjointOperator (Chapter 12.0.5), the reproducible generator (Chapter 12.1, Sketch), rsvd() and range_finder (12.4), and svds() by Golub–Kahan–Lanczos bidiagonalization with thick restart (12.5), on the shared Krylov machinery (12.0.6–12.0.7). L3.4 completed the v0.1 surface: eigsh() and eigs() by Krylov–Schur restarted Lanczos/Arnoldi with ARPACK’s which vocabulary (12.6), the small dense eigensolvers they need (12.6.1), and shift-invert over the factorizations of xingo-sparse, eigsh_near with the inertia count and eigs_near (12.6.2). (The chapter number 12 is that of the Xingó book: 1–8, 10 and 11 are other parts of the solver.)

§Purpose

Statistical computing keeps asking questions that a dense library answers only by starting from scratch. The four this edition answers:

  1. A row arrived (or left); what is the new least-squares fit? — a QR factorization updated in O(mn) instead of refactorized in O(mn²) (sequential and windowed regression, recursive least squares, leave-one-out): Qr.

  2. A covariance or information matrix changed by ± x xᵀ; what is its new Cholesky factor? — a rank-1 update/downdate in O(n²) (Kalman/RLS filters, Gaussian-process and mixed-model refits, the Q-less QR, which is the Cholesky factor of AᵀA): Cholesky.

  3. What are the leading k singular triplets of a matrix I can only multiply by? — the randomized SVD of Halko, Martinsson & Tropp, with a stated expected error (rsvd()), and a deterministic truncated SVD by Golub–Kahan–Lanczos bidiagonalization accurate to ε σ_1 on every singular value (svds()).

  4. What are k eigenvalues at one end of the spectrum (or nearest σ) of a large sparse or implicit operator? — eigsh()/eigs() by Krylov–Schur restarted Lanczos/Arnoldi with ARPACK’s which vocabulary, and eigsh_near/eigs_near by shift-invert.

The crate does not depend on the solver; the R and Python packages will reach it through xingo-ffi (L4).

§Notation

T is the scalar (Real), ε_T its machine epsilon and u = ε_T/2 its unit roundoff (2⁻⁵³ for f64, 2⁻¹⁰⁵ for the double-double of xingo-extprec). Matrices are column-major: a_ij = data[i + j·ld], ld ≥ rows. A ∈ R^{m×n}; R upper triangular with positive diagonal (the convention of R’s chol and MATLAB’s chol/cholupdate; RᵀR = A); Q ∈ R^{m×n} with orthonormal columns; ‖·‖ the 2-norm, ‖·‖_F Frobenius; e_j the j-th unit vector. A_t is the matrix a sequence of operations defines (the exact result of applying them to the input).

§Layout of the crate

chaptermodulecontent
12this pageoverview, invariants, decisions
12.0error, view, real, small (private)errors, views, comparisons, Givens rotations, Householder reflectors and QR, DGKS Gram–Schmidt
12.0.5operatorLinearOperator, AdjointOperator, OperatorError, closures (from_fn, from_fns)
12.0.6jacobi (private)one-sided Jacobi SVD of a small matrix
12.0.7krylov (private)expansion with DGKS and breakdown, restart dimension
12.1randomAlgorithm G (xoshiro256++, polar method, own ln), Sketch
12.2choleskyCholesky, CholOptions, DowndateInfo
12.3qrQr, QrOptions
12.4rsvdrsvd(), range_finder, RsvdOptions, Svd, SvdStats
12.5svdssvds(), SvdsOptions, SvdWhich
12.6eigseigsh(), eigs(), EigsOptions, EigsStats, SymEigen, Eigen, Complex, Which
12.6.1schur (private)symmetric Jacobi, Hessenberg + Francis real Schur, block swaps and reordering, eigenvectors of the quasi-triangular form
12.6.2shift_invertShiftInvert, SymShiftInvert, eigsh_near, eigs_near

§What is reused from xingo-sparse, and why (D-0080 layering)

needtaken from xingo-sparsenew here
scalarReal (generic everywhere; f64 default; DoubleDouble of xingo-extprec instantiates unchanged)—
owned denseDenseBlock (column-major, ld = rows)borrowed views with ld (S3)
the initial Cholesky factorizationDenseKernel::potrf via a type parameter K = NaiveDense, as SupernodalLdl<T, K> does—
Householder, Givens, Gram–Schmidt, Jacobi, Francis/Schur— (not in DenseKernel)internal, generic in T (S1)
shift-invert solvesLu<T> (general), SupernodalLdl<T, K> LBLᵀ + inertia (symmetric)ShiftInvert, SymShiftInvert, one step of iterative refinement per application
comparisonsthe helpers of Chapter 5.6 are pub(crate) therea private copy with the same definitions (module real)

DoubleDouble. Every algorithm needs only + − · /, sqrt, abs and the order — exactly Real — so Cholesky<DoubleDouble> and Qr<DoubleDouble> instantiate without code (S1); the tests run the whole acceptance suite in both scalars. Random test matrices are generated in f64 and converted exactly (Real::from_f64).

Where the kernel K is used. In this edition only by Cholesky::factor_with (potrf). The Householder QR, the updates and the solves are O(n²)/O(mn) loops written here: the contract’s “large products” of Qr (a blocked WY Householder through gemm_sub) are a measured optimization for later, and Qr carries its K to Qr::to_cholesky.

§Divergences from the references

  • LINPACK dchud/dchdd (Saunders 1972; Stewart 1979) for the Cholesky update/downdate, not hyperbolic rotations: the pilot s01 measured both (same backward error ≈ 4·10⁻¹⁶ for κ up to 10¹²), and LINPACK detects indefiniteness before touching R — the transactional guarantee for free (12.2). This edition also computes the new diagonal before writing, so that an underflow to a zero pivot is refused transactionally too (step C3′).
  • Hammarling & Lucas (2008) for the QR updates, in the “economy” forms with an explicit thin Q; delete_row and rank1_update complete Q by one Gram–Schmidt vector with DGKS reorthogonalization (Daniel, Gragg, Kaufman & Stewart 1976) instead of keeping a full m × m factor (12.3).
  • faer 0.24.4 has a rank-r LLᵀ update with signed weights (D-0082 addendum); it lacks QR updating, T: Real and errors instead of assert!s.

§Invariants (each becomes a debug_assert! or check_invariants())

(H1) Cholesky: R is upper triangular (strict lower triangle exactly zero), r_jj > 0 and every entry finite. Cholesky::check_invariants; debug_assert! after every operation. (H2) Cholesky: after any sequence of operations, ‖RᵀR − A_t‖_F ≤ c_H · n · u · ‖A_t‖_F, checked by the tests against A_t accumulated in double-double; c_H = 8 (measured: 4.0 at n = 1, ≤ 0.06 for n ≥ 50, in f64; smaller in double-double). When downdates cancel more than half of the matrix the tests take the norm along the path, max_s ‖A_s‖_F, instead of ‖A_t‖_F (question Q-L32-3 of task L3.2). (H3) Transactional. A failed update/downdate leaves the factor bit for bit as it was. (Q1) Qr: ‖QᵀQ − I‖_F ≤ c_Q · m · u (reorthogonalization keeps it); Qr::check_invariants with c_Q given. (Q2) Qr: R upper triangular with r_jj > 0; ‖QR − A_t‖_F ≤ c_Q · m · u · ‖A_t‖_F (the tests, against A_t in double-double, with the path norm as in H2); c_Q = 16 for (Q1) and (Q2) (measured: 8.0 and 5.4 on 2 × 1 and 3 × 2 after delete_row, ≤ 0.6 for m ≥ 100). (Q3) As (H3): a failed operation leaves Q and R bit for bit as they were.

(R1)–(R2), (G1)–(G5): rsvd() and svds(), Chapters 12.4 and 12.5 (c_G = 8, measured). (K1)–(K4), (E1)–(E3), (I1)–(I3): eigsh()/eigs(), the small dense eigensolvers and shift-invert, Chapters 12.6–12.6.2 (c_K = 8, measured in f64).

The constants c_H, c_Q come from the measurements of the example accuracy with a margin, and live in the tests and in the argument of Qr::check_invariants, not as literals in kernels.

§Decisions of the review (2026-11-19; D-0127)

  • S1 — generic T: Real, with own small dense routines (internal).
  • S2 — svds() is Golub–Kahan–Lanczos bidiagonalization with thick restart, its own engine, full two-sided reorthogonalization.
  • S3 — MatRef/MatMut live here.
  • S4 — own xoshiro256++, Marsaglia polar method, own ln (12.1).
  • S5 — apply(&mut self, …) -> Result; separate AdjointOperator.
  • S6 — names eigs, eigsh, svds, rsvd, range_finder.
  • S7 — Krylov–Schur restart (Stewart 2001) for eigs() and eigsh(), one engine for both (Chapter 12.6), not ARPACK’s implicit QR shifts; results compared with ARPACK.
  • S8 — thin QR with five operations; Cholesky update/downdate; Cholesky insert/delete of a variable in v0.2.
  • S9 — acceptance criteria rewritten on the pilot’s numbers (each chapter states its own).
  • S10 — one #[non_exhaustive] StatlaError; Sketch and SvdWhich #[non_exhaustive]; options with public fields and Default; non-convergence is Err(NoConvergence) unless allow_partial.

§References

Golub & Van Loan, Matrix Computations, 4th ed. (2013), §5.1 (Givens, Householder), §6.5 (updating). Gill, Golub, Murray & Saunders, “Methods for modifying matrix factorizations”, Math. Comp. 28 (1974). Saunders, “Large-scale linear programming using the Cholesky factorization”, Stanford report (1972). Stewart, “The effects of rounding error on an algorithm for downdating a Cholesky factorization”, J. IMA 23 (1979). Dongarra, Bunch, Moler & Stewart, LINPACK Users’ Guide, SIAM (1979), ch. 10 (dchud, dchdd). Daniel, Gragg, Kaufman & Stewart, “Reorthogonalization and stable algorithms for updating the Gram–Schmidt QR factorization”, Math. Comp. 30 (1976). Hammarling & Lucas, “Updating the QR factorization and the least squares problem”, MIMS EPrint 2008.111 (2008). Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed. (2002), ch. 10 and 19. Halko, Martinsson & Tropp, “Finding structure with randomness”, SIAM Review 53 (2011). Golub & Kahan, SIAM J. Numer. Anal. 2 (1965). Baglama & Reichel, “Augmented implicitly restarted Lanczos bidiagonalization methods”, SISC 27 (2005). Hestenes, J. SIAM 6 (1958); Demmel & Veselić, SIMAX 13 (1992). Blackman & Vigna, ACM TOMS 47 (2021). Marsaglia & Bray, SIAM Review 6 (1964). Stewart, “A Krylov–Schur algorithm for large eigenproblems”, SIMAX 23 (2001); Wu & Simon, SIMAX 22 (2000); Lehoucq, Sorensen & Yang, ARPACK Users’ Guide (1998); Bai & Demmel, Linear Algebra Appl. 186 (1993); LAPACK dlahqr, dlanv2, dlaexc, dtrevc. All cited from memory; no source was reopened in tasks L3.2–L3.4 (the xoshiro256++ reference outputs were read in the tests of rand 0.9.4; ARPACK’s tie order in dngets is recalled, and checked only against scipy’s results on the fixtures).

Modules§

cholesky 🔒
Chapter 12.2 — Cholesky with rank-1 update and downdate
eigs 🔒
Chapter 12.6 — eigsh and eigs: Krylov–Schur restarted Lanczos and Arnoldi with ARPACK’s contract
error 🔒
Chapter 12.0.1 — Errors
jacobi 🔒
Chapter 12.0.6 — One-sided Jacobi SVD of a small dense matrix
krylov 🔒
Chapter 12.0.7 — Krylov machinery shared by the restarted drivers
operator 🔒
Chapter 12.0.5 — Linear operators
qr 🔒
Chapter 12.3 — Thin QR with explicit Q and five updating operations
random 🔒
Chapter 12.1 — Reproducible randomness: Algorithm G and the logarithm
real 🔒
Chapter 12.0.3 — Comparisons
rsvd 🔒
Chapter 12.4 — Randomized SVD (Halko, Martinsson & Tropp 2011)
schur 🔒
Chapter 12.6.1 — Small dense eigensolvers: symmetric Jacobi, Hessenberg–Francis real Schur, reordering, eigenvectors
shift_invert 🔒
Chapter 12.6.2 — Shift-invert: eigsh_near over SupernodalLdl, eigs_near over Lu
small 🔒
Chapter 12.0.4 — Small dense routines: norms, Givens rotations, Householder reflectors, DGKS Gram–Schmidt
svds 🔒
Chapter 12.5 — Truncated SVD by Golub–Kahan–Lanczos bidiagonalization with thick restart
view 🔒
Chapter 12.0.2 — Dense views

Structs§

CholOptions
Options of Cholesky: every threshold of chapter 12.2 lives here.
Cholesky
The upper Cholesky factor R of a symmetric positive definite A = RᵀR, kept up to date under A ← A ± x xᵀ (Chapter 12.2: Algorithms F, U, C).
Complex
A pair re + i·im (eigenvalues of a real nonsymmetric operator). No arithmetic: a value type for results, not a complex scalar (complex matrices are out of scope).
DenseBlock
A column-major dense block: a_ij = data[i + j·rows].
DowndateInfo
What a successful downdate saw.
Eigen
Eigenpairs of a real nonsymmetric operator, most wanted first; complex conjugate pairs are adjacent, positive imaginary part first (exactly k values: the conjugate of a k-th value with positive imaginary part is omitted, as scipy does).
EigsOptions
Options of eigs() and eigsh(). Defaults are scipy’s (scipy.sparse.linalg.eigs/eigsh) where it has one.
EigsStats
Work counters of the Krylov drivers.
FnAdjointOperator
An operator and its transpose from two closures. Build with from_fns.
FnOperator
An operator from a closure f(x, y) writing y ← A x (PLAN L3.1’s “operador-closure”). Build with from_fn.
MatMut
The mutable counterpart of MatRef.
MatRef
A borrowed column-major rows × cols matrix with leading dimension ld ≥ rows: a_ij = data[i + j·ld] (the LAPACK/R layout; a C-order NumPy array is the view of its transpose, a rule for xingo-ffi). data.len() ≥ ld·(cols − 1) + rows when cols > 0.
NaiveDense
Reference kernels: straightforward loops, always available, the oracle of the others in tests.
OperatorError
An error reported by a LinearOperator (for instance a closure whose inner solve failed). Carries a message only, so that crate::StatlaError stays Clone + PartialEq.
Qr
Thin QR A = QR, Q ∈ R^{m×n} explicit with orthonormal columns, R ∈ R^{n×n} upper triangular with r_jj > 0, m ≥ n, full column rank (Chapter 12.3: Algorithms F, I, D, C, E, R).
QrOptions
Options of Qr.
RsvdOptions
Options of rsvd() and range_finder; the defaults follow R’s rsvd (p = 10, q = 2; cited from memory) and HMT’s advice to re-orthonormalize at every half step of the power scheme.
ShiftInvert
x ↦ (A − σI)⁻¹ x for a square sparse A, by the threshold LU of xingo-sparse (Lu<T> over the columns of A − σI, factorized once), with one step of iterative refinement per application (Algorithm R: two solves and one product with A − σI, which the operator keeps). The operator of eigs_near (Algorithm SG of Chapter 12.6.2).
Svd
A truncated SVD A ≈ U diag(s) Vᵀ: U is m × k, V is n × k (not transposed: R’s svd convention), s nonincreasing.
SvdStats
Work counters of rsvd() and crate::svds().
SvdsOptions
Options of svds(). Defaults are scipy’s svds where it has one (cited from memory), with ARPACK’s dimension rule.
SymEigen
Symmetric eigenpairs, most wanted first (in the order of which).
SymShiftInvert
x ↦ (A − σI)⁻¹ x for a symmetric sparse A (lower triangle read), by SupernodalLdl<T, K> with no regularization; the inertia of A − σI is kept: by Sylvester’s law it counts the eigenvalues below σ (SymShiftInvert::count_below) — a check ARPACK does not offer. Each application refines once (Algorithm R: two solves and one product with the kept lower triangle of A − σI). The operator of eigsh_near (Algorithm SI of Chapter 12.6.2).

Enums§

Sketch
Distribution of the test matrix Ω of crate::rsvd() and crate::range_finder (Algorithm G).
StatlaError
Everything that can go wrong, for every function of the crate (decision S10: one error type). No function of the crate panics on bad input; panics are bugs.
SvdWhich
Which singular values svds() computes. v0.1 has only the largest; the smallest (harmonic Ritz or refined restarts, Baglama & Reichel; cited from memory) would be a new variant, hence #[non_exhaustive].
Which
Which part of the spectrum, with ARPACK’s two-letter codes (Which::from_arpack) so that R and Python pass their strings through xingo-ffi unchanged. eigsh() accepts LM SM LA SA BE; eigs() accepts LM SM LR SR LI SI; any other combination is StatlaError::InvalidArgument.

Traits§

AdjointOperator
An operator that also applies its transpose: y ← Aᵀ x. Needed by crate::rsvd() and crate::svds().
DenseKernel
The kernels a supernodal factorization needs (BLAS-3 names kept for recognizability). Square blocks are read and written in their lower triangle (invariant (D3)).
LinearOperator
y ← A x for an nrows × ncols operator known only by its action.
Real
The scalar type of every container and factorization of the crate.

Functions§

eigs
k eigenpairs of a general real operator.
eigs_near
The k eigenvalues of the general A nearest the real shift σ, by eigs() on ShiftInvert (LuOptions::for_scalar::<T>()), mapped back by λ = σ + 1/ν, nearest first; conjugate pairs keep the +i member first.
eigsh
k eigenpairs of a symmetric operator (the caller asserts the symmetry; it is not checked).
eigsh_near
The k eigenvalues of the symmetric A nearest σ: eigsh() with LargestMagnitude on SymShiftInvert, mapped back by λ = σ + 1/ν (ARPACK mode 3 for the standard problem), nearest first. Returns also SymShiftInvert::count_below. Only the lower triangle of a is read.
from_fn
FnOperator of the closure f.
from_fns
FnAdjointOperator of f (y ← A x) and g (y ← Aᵀ x).
range_finder
Steps S1–S3 only: an orthonormal Q ∈ R^{m×l} whose range approximates that of A (for sketching, CUR, randomized PCA by the caller). The width is l itself: RsvdOptions::oversample is not added (it belongs to rsvd()’s k + p).
rsvd
Randomized SVD of rank k.
svds
Leading k singular triplets by Golub–Kahan–Lanczos bidiagonalization with thick restart — a Krylov engine of its own, not an eigensolver on AᵀA (S2): it never squares the condition, so every singular value comes out with an absolute error of order ε σ_1.