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:
-
A row arrived (or left); what is the new least-squares fit? — a QR factorization updated in
O(mn)instead of refactorized inO(mn²)(sequential and windowed regression, recursive least squares, leave-one-out):Qr. -
A covariance or information matrix changed by
± x xᵀ; what is its new Cholesky factor? — a rank-1 update/downdate inO(n²)(Kalman/RLS filters, Gaussian-process and mixed-model refits, the Q-less QR, which is the Cholesky factor ofAᵀA):Cholesky. -
What are the leading
ksingular 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ε σ_1on every singular value (svds()). -
What are
keigenvalues 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’swhichvocabulary, andeigsh_near/eigs_nearby 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
| chapter | module | content |
|---|---|---|
| 12 | this page | overview, invariants, decisions |
| 12.0 | error, view, real, small (private) | errors, views, comparisons, Givens rotations, Householder reflectors and QR, DGKS Gram–Schmidt |
| 12.0.5 | operator | LinearOperator, AdjointOperator, OperatorError, closures (from_fn, from_fns) |
| 12.0.6 | jacobi (private) | one-sided Jacobi SVD of a small matrix |
| 12.0.7 | krylov (private) | expansion with DGKS and breakdown, restart dimension |
| 12.1 | random | Algorithm G (xoshiro256++, polar method, own ln), Sketch |
| 12.2 | cholesky | Cholesky, CholOptions, DowndateInfo |
| 12.3 | qr | Qr, QrOptions |
| 12.4 | rsvd | rsvd(), range_finder, RsvdOptions, Svd, SvdStats |
| 12.5 | svds | svds(), SvdsOptions, SvdWhich |
| 12.6 | eigs | eigsh(), eigs(), EigsOptions, EigsStats, SymEigen, Eigen, Complex, Which |
| 12.6.1 | schur (private) | symmetric Jacobi, Hessenberg + Francis real Schur, block swaps and reordering, eigenvectors of the quasi-triangular form |
| 12.6.2 | shift_invert | ShiftInvert, SymShiftInvert, eigsh_near, eigs_near |
§What is reused from xingo-sparse, and why (D-0080 layering)
| need | taken from xingo-sparse | new here |
|---|---|---|
| scalar | Real (generic everywhere; f64 default; DoubleDouble of xingo-extprec instantiates unchanged) | — |
| owned dense | DenseBlock (column-major, ld = rows) | borrowed views with ld (S3) |
| the initial Cholesky factorization | DenseKernel::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 solves | Lu<T> (general), SupernodalLdl<T, K> LBLᵀ + inertia (symmetric) | ShiftInvert, SymShiftInvert, one step of iterative refinement per application |
| comparisons | the helpers of Chapter 5.6 are pub(crate) there | a 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 pilots01measured both (same backward error≈ 4·10⁻¹⁶forκup to10¹²), and LINPACK detects indefiniteness before touchingR— 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_rowandrank1_updatecompleteQby one Gram–Schmidt vector with DGKS reorthogonalization (Daniel, Gragg, Kaufman & Stewart 1976) instead of keeping a fullm × mfactor (12.3). - faer 0.24.4 has a rank-
rLLᵀ update with signed weights (D-0082 addendum); it lacks QR updating,T: Realand errors instead ofassert!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/MatMutlive here. - S4 — own xoshiro256++, Marsaglia polar method, own
ln(12.1). - S5 —
apply(&mut self, …) -> Result; separateAdjointOperator. - S6 — names
eigs,eigsh,svds,rsvd,range_finder. - S7 — Krylov–Schur restart (Stewart 2001) for
eigs()andeigsh(), 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;SketchandSvdWhich#[non_exhaustive]; options with public fields andDefault; non-convergence isErr(NoConvergence)unlessallow_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 —
eigshandeigs: 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
Qand 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_nearoverSupernodalLdl,eigs_nearoverLu - 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§
- Chol
Options - Options of
Cholesky: every threshold of chapter 12.2 lives here. - Cholesky
- The upper Cholesky factor
Rof a symmetric positive definiteA = RᵀR, kept up to date underA ← 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). - Dense
Block - A column-major dense block:
a_ij = data[i + j·rows]. - Downdate
Info - 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
kvalues: the conjugate of ak-th value with positive imaginary part is omitted, as scipy does). - Eigs
Options - Options of
eigs()andeigsh(). Defaults are scipy’s (scipy.sparse.linalg.eigs/eigsh) where it has one. - Eigs
Stats - Work counters of the Krylov drivers.
- FnAdjoint
Operator - An operator and its transpose from two closures. Build with
from_fns. - FnOperator
- An operator from a closure
f(x, y)writingy ← A x(PLAN L3.1’s “operador-closure”). Build withfrom_fn. - MatMut
- The mutable counterpart of
MatRef. - MatRef
- A borrowed column-major
rows × colsmatrix with leading dimensionld ≥ rows:a_ij = data[i + j·ld](the LAPACK/R layout; a C-order NumPy array is the view of its transpose, a rule forxingo-ffi).data.len() ≥ ld·(cols − 1) + rowswhencols > 0. - Naive
Dense - Reference kernels: straightforward loops, always available, the oracle of the others in tests.
- Operator
Error - An error reported by a
LinearOperator(for instance a closure whose inner solve failed). Carries a message only, so thatcrate::StatlaErrorstaysClone + PartialEq. - Qr
- Thin QR
A = QR,Q ∈ R^{m×n}explicit with orthonormal columns,R ∈ R^{n×n}upper triangular withr_jj > 0,m ≥ n, full column rank (Chapter 12.3: Algorithms F, I, D, C, E, R). - QrOptions
- Options of
Qr. - Rsvd
Options - Options of
rsvd()andrange_finder; the defaults follow R’srsvd(p = 10,q = 2; cited from memory) and HMT’s advice to re-orthonormalize at every half step of the power scheme. - Shift
Invert x ↦ (A − σI)⁻¹ xfor a square sparseA, by the threshold LU ofxingo-sparse(Lu<T>over the columns ofA − σI, factorized once), with one step of iterative refinement per application (Algorithm R: two solves and one product withA − σI, which the operator keeps). The operator ofeigs_near(Algorithm SG of Chapter 12.6.2).- Svd
- A truncated SVD
A ≈ U diag(s) Vᵀ:Uism × k,Visn × k(not transposed: R’ssvdconvention),snonincreasing. - SvdStats
- Work counters of
rsvd()andcrate::svds(). - Svds
Options - Options of
svds(). Defaults are scipy’ssvdswhere it has one (cited from memory), with ARPACK’s dimension rule. - SymEigen
- Symmetric eigenpairs, most wanted first (in the order of
which). - SymShift
Invert x ↦ (A − σI)⁻¹ xfor a symmetric sparseA(lower triangle read), bySupernodalLdl<T, K>with no regularization; the inertia ofA − σIis 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 ofA − σI). The operator ofeigsh_near(Algorithm SI of Chapter 12.6.2).
Enums§
- Sketch
- Distribution of the test matrix
Ωofcrate::rsvd()andcrate::range_finder(Algorithm G). - Statla
Error - 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 throughxingo-ffiunchanged.eigsh()acceptsLM SM LA SA BE;eigs()acceptsLM SM LR SR LI SI; any other combination isStatlaError::InvalidArgument.
Traits§
- Adjoint
Operator - An operator that also applies its transpose:
y ← Aᵀ x. Needed bycrate::rsvd()andcrate::svds(). - Dense
Kernel - The kernels a supernodal factorization needs (BLAS-3 names kept for recognizability). Square blocks are read and written in their lower triangle (invariant (D3)).
- Linear
Operator y ← A xfor annrows × ncolsoperator known only by its action.- Real
- The scalar type of every container and factorization of the crate.
Functions§
- eigs
keigenpairs of a general real operator.- eigs_
near - The
keigenvalues of the generalAnearest the real shiftσ, byeigs()onShiftInvert(LuOptions::for_scalar::<T>()), mapped back byλ = σ + 1/ν, nearest first; conjugate pairs keep the+imember first. - eigsh
keigenpairs of a symmetric operator (the caller asserts the symmetry; it is not checked).- eigsh_
near - The
keigenvalues of the symmetricAnearestσ:eigsh()withLargestMagnitudeonSymShiftInvert, mapped back byλ = σ + 1/ν(ARPACK mode 3 for the standard problem), nearest first. Returns alsoSymShiftInvert::count_below. Only the lower triangle ofais read. - from_fn
FnOperatorof the closuref.- from_
fns FnAdjointOperatoroff(y ← A x) andg(y ← Aᵀ x).- range_
finder - Steps S1–S3 only: an orthonormal
Q ∈ R^{m×l}whose range approximates that ofA(for sketching, CUR, randomized PCA by the caller). The width islitself:RsvdOptions::oversampleis not added (it belongs torsvd()’sk + p). - rsvd
- Randomized SVD of rank
k. - svds
- Leading
ksingular triplets by Golub–Kahan–Lanczos bidiagonalization with thick restart — a Krylov engine of its own, not an eigensolver onAᵀA(S2): it never squares the condition, so every singular value comes out with an absolute error of orderε σ_1.