Skip to main content

xingo_statla/
lib.rs

1//! # Chapter 12 — `xingo-statla`: updatable and matrix-free linear algebra for statistics
2//!
3//! **Status: complete for v0.1 (tasks L3.2, L3.3 and L3.4).** The contract
4//! of the crate was ratified on 2026-11-19 (decision log of the Xingó
5//! solver, D-0127) and amended by what the implementation measured (D-0132,
6//! D-0134, D-0135); where they differ, this text and the code are
7//! authoritative. Labels such as L3.2 are tasks of the solver's plan, D-xxxx
8//! are entries of its decision log, and names such as `l34-tables.md` are
9//! the working notes of a task in the monorepo (not part of the package;
10//! the numbers that matter are quoted where they are used). L3.2
11//! implemented the *updatable factorizations*: the dense views
12//! [`MatRef`]/[`MatMut`], the error type [`StatlaError`] (Chapter 12.0),
13//! [`Cholesky`] with rank-1 update and transactional downdate (Chapter
14//! 12.2) and the thin [`Qr`] with explicit `Q` and five updating operations
15//! (Chapter 12.3). L3.3 added the *matrix-free* part: the operator traits
16//! [`LinearOperator`]/[`AdjointOperator`] (Chapter 12.0.5), the
17//! reproducible generator (Chapter 12.1, [`Sketch`]), [`rsvd()`] and
18//! [`range_finder`] (12.4), and [`svds()`] by Golub–Kahan–Lanczos
19//! bidiagonalization with thick restart (12.5), on the shared Krylov
20//! machinery (12.0.6–12.0.7). L3.4 completed the v0.1 surface:
21//! [`eigsh()`] and [`eigs()`] by Krylov–Schur restarted Lanczos/Arnoldi
22//! with ARPACK's `which` vocabulary (12.6), the small dense eigensolvers
23//! they need (12.6.1), and shift-invert over the factorizations of
24//! `xingo-sparse`, [`eigsh_near`] with the inertia count and [`eigs_near`]
25//! (12.6.2). (The chapter number 12 is that of the Xingó book: 1–8, 10 and
26//! 11 are other parts of the solver.)
27//!
28//! ## Purpose
29//! Statistical computing keeps asking questions that a dense library
30//! answers only by starting from scratch. The four this edition answers:
31//!
32//! 1. *A row arrived (or left); what is the new least-squares fit?* — a QR
33//!    factorization **updated** in `O(mn)` instead of refactorized in
34//!    `O(mn²)` (sequential and windowed regression, recursive least
35//!    squares, leave-one-out): [`Qr`].
36//! 2. *A covariance or information matrix changed by `± x xᵀ`; what is its
37//!    new Cholesky factor?* — a rank-1 **update/downdate** in `O(n²)`
38//!    (Kalman/RLS filters, Gaussian-process and mixed-model refits, the
39//!    Q-less QR, which *is* the Cholesky factor of `AᵀA`): [`Cholesky`].
40//!
41//! 3. *What are the leading `k` singular triplets of a matrix I can only
42//!    multiply by?* — the **randomized** SVD of Halko, Martinsson & Tropp,
43//!    with a stated expected error ([`rsvd()`]), and a deterministic truncated
44//!    SVD by Golub–Kahan–Lanczos bidiagonalization accurate to `ε σ_1` on
45//!    every singular value ([`svds()`]).
46//! 4. *What are `k` eigenvalues at one end of the spectrum (or nearest
47//!    `σ`) of a large sparse or implicit operator?* — [`eigsh()`]/[`eigs()`]
48//!    by Krylov–Schur restarted Lanczos/Arnoldi with ARPACK's `which`
49//!    vocabulary, and [`eigsh_near`]/[`eigs_near`] by shift-invert.
50//!
51//! The crate does not depend on the solver; the R and Python packages will
52//! reach it through `xingo-ffi` (L4).
53//!
54//! ## Notation
55//! `T` is the scalar ([`Real`]), `ε_T` its machine epsilon and `u = ε_T/2`
56//! its unit roundoff (`2⁻⁵³` for `f64`, `2⁻¹⁰⁵` for the double-double of
57//! `xingo-extprec`). Matrices are column-major: `a_ij = data[i + j·ld]`,
58//! `ld ≥ rows`. `A ∈ R^{m×n}`; `R` upper triangular with positive diagonal
59//! (the convention of R's `chol` and MATLAB's `chol`/`cholupdate`; `RᵀR =
60//! A`); `Q ∈ R^{m×n}` with orthonormal columns; `‖·‖` the 2-norm, `‖·‖_F`
61//! Frobenius; `e_j` the `j`-th unit vector. `A_t` is the matrix a sequence
62//! of operations defines (the exact result of applying them to the input).
63//!
64//! ## Layout of the crate
65//! | chapter | module | content |
66//! |---|---|---|
67//! | 12 | this page | overview, invariants, decisions |
68//! | 12.0 | `error`, `view`, `real`, `small` (private) | errors, views, comparisons, Givens rotations, Householder reflectors and QR, DGKS Gram–Schmidt |
69//! | 12.0.5 | `operator` | [`LinearOperator`], [`AdjointOperator`], [`OperatorError`], closures ([`from_fn`], [`from_fns`]) |
70//! | 12.0.6 | `jacobi` (private) | one-sided Jacobi SVD of a small matrix |
71//! | 12.0.7 | `krylov` (private) | expansion with DGKS and breakdown, restart dimension |
72//! | 12.1 | `random` | Algorithm G (xoshiro256++, polar method, own `ln`), [`Sketch`] |
73//! | 12.2 | `cholesky` | [`Cholesky`], [`CholOptions`], [`DowndateInfo`] |
74//! | 12.3 | `qr` | [`Qr`], [`QrOptions`] |
75//! | 12.4 | `rsvd` | [`rsvd()`], [`range_finder`], [`RsvdOptions`], [`Svd`], [`SvdStats`] |
76//! | 12.5 | `svds` | [`svds()`], [`SvdsOptions`], [`SvdWhich`] |
77//! | 12.6 | `eigs` | [`eigsh()`], [`eigs()`], [`EigsOptions`], [`EigsStats`], [`SymEigen`], [`Eigen`], [`Complex`], [`Which`] |
78//! | 12.6.1 | `schur` (private) | symmetric Jacobi, Hessenberg + Francis real Schur, block swaps and reordering, eigenvectors of the quasi-triangular form |
79//! | 12.6.2 | `shift_invert` | [`ShiftInvert`], [`SymShiftInvert`], [`eigsh_near`], [`eigs_near`] |
80//!
81//! ## What is reused from `xingo-sparse`, and why (D-0080 layering)
82//! | need | taken from `xingo-sparse` | new here |
83//! |---|---|---|
84//! | scalar | [`Real`] (generic everywhere; `f64` default; `DoubleDouble` of `xingo-extprec` instantiates unchanged) | — |
85//! | owned dense | [`DenseBlock`] (column-major, `ld = rows`) | borrowed views with `ld` (S3) |
86//! | the initial Cholesky factorization | [`DenseKernel::potrf`] via a type parameter `K = NaiveDense`, as `SupernodalLdl<T, K>` does | — |
87//! | Householder, Givens, Gram–Schmidt, Jacobi, Francis/Schur | — (not in `DenseKernel`) | internal, generic in `T` (S1) |
88//! | shift-invert solves | `Lu<T>` (general), `SupernodalLdl<T, K>` `LBLᵀ` + inertia (symmetric) | [`ShiftInvert`], [`SymShiftInvert`], one step of iterative refinement per application |
89//! | comparisons | the helpers of Chapter 5.6 are `pub(crate)` there | a private copy with the same definitions (module `real`) |
90//!
91//! **`DoubleDouble`.** Every algorithm needs only `+ − · /`, `sqrt`, `abs`
92//! and the order — exactly [`Real`] — so `Cholesky<DoubleDouble>` and
93//! `Qr<DoubleDouble>` instantiate without code (S1); the tests run the
94//! whole acceptance suite in both scalars. Random test matrices are
95//! generated in `f64` and converted exactly (`Real::from_f64`).
96//!
97//! **Where the kernel `K` is used.** In this edition only by
98//! [`Cholesky::factor_with`] (`potrf`). The Householder QR, the updates and
99//! the solves are `O(n²)`/`O(mn)` loops written here: the contract's "large
100//! products" of `Qr` (a blocked WY Householder through `gemm_sub`) are a
101//! measured optimization for later, and `Qr` carries its `K` to
102//! [`Qr::to_cholesky`].
103//!
104//! ## Divergences from the references
105//! * **LINPACK `dchud`/`dchdd`** (Saunders 1972; Stewart 1979) for the
106//!   Cholesky update/downdate, not hyperbolic rotations: the pilot `s01`
107//!   measured both (same backward error `≈ 4·10⁻¹⁶` for `κ` up to
108//!   `10¹²`), and LINPACK detects indefiniteness *before* touching `R` —
109//!   the transactional guarantee for free (12.2). This edition also
110//!   computes the new diagonal before writing, so that an underflow to a
111//!   zero pivot is refused transactionally too (step C3′).
112//! * **Hammarling & Lucas (2008)** for the QR updates, in the "economy"
113//!   forms with an explicit thin `Q`; `delete_row` and `rank1_update`
114//!   complete `Q` by one Gram–Schmidt vector with DGKS reorthogonalization
115//!   (Daniel, Gragg, Kaufman & Stewart 1976) instead of keeping a full
116//!   `m × m` factor (12.3).
117//! * **faer 0.24.4** has a rank-`r` LLᵀ update with signed weights (D-0082
118//!   addendum); it lacks QR updating, `T: Real` and errors instead of
119//!   `assert!`s.
120//!
121//! ## Invariants (each becomes a `debug_assert!` or `check_invariants()`)
122//! (H1) `Cholesky`: `R` is upper triangular (strict lower triangle exactly
123//!      zero), `r_jj > 0` and every entry finite.
124//!      [`Cholesky::check_invariants`]; `debug_assert!` after every
125//!      operation.
126//! (H2) `Cholesky`: after any sequence of operations, `‖RᵀR − A_t‖_F ≤
127//!      c_H · n · u · ‖A_t‖_F`, checked by the tests against `A_t`
128//!      accumulated in double-double; `c_H = 8` (measured: `4.0` at `n =
129//!      1`, `≤ 0.06` for `n ≥ 50`, in `f64`; smaller in double-double).
130//!      When downdates cancel more than half of the matrix the tests take
131//!      the norm along the path, `max_s ‖A_s‖_F`, instead of `‖A_t‖_F`
132//!      (question Q-L32-3 of task L3.2).
133//! (H3) *Transactional.* A failed `update`/`downdate` leaves the factor
134//!      bit for bit as it was.
135//! (Q1) `Qr`: `‖QᵀQ − I‖_F ≤ c_Q · m · u` (reorthogonalization keeps it);
136//!      [`Qr::check_invariants`] with `c_Q` given.
137//! (Q2) `Qr`: `R` upper triangular with `r_jj > 0`; `‖QR − A_t‖_F ≤ c_Q · m
138//!      · u · ‖A_t‖_F` (the tests, against `A_t` in double-double, with the
139//!      path norm as in H2); `c_Q = 16` for (Q1) and (Q2) (measured: `8.0`
140//!      and `5.4` on `2 × 1` and `3 × 2` after `delete_row`, `≤ 0.6` for `m
141//!      ≥ 100`).
142//! (Q3) As (H3): a failed operation leaves `Q` and `R` bit for bit as they
143//!      were.
144//!
145//! (R1)–(R2), (G1)–(G5): [`rsvd()`] and [`svds()`], Chapters 12.4 and 12.5
146//!      (`c_G = 8`, measured).
147//! (K1)–(K4), (E1)–(E3), (I1)–(I3): [`eigsh()`]/[`eigs()`], the small dense
148//!      eigensolvers and shift-invert, Chapters 12.6–12.6.2 (`c_K = 8`,
149//!      measured in `f64`).
150//!
151//! The constants `c_H`, `c_Q` come from the measurements of the example
152//! `accuracy` with a margin, and live in the tests and in the argument of
153//! [`Qr::check_invariants`], not as literals in kernels.
154//!
155//! ## Decisions of the review (2026-11-19; D-0127)
156//! * **S1** — generic `T: Real`, with own small dense routines (internal).
157//! * **S2** — [`svds()`] is Golub–Kahan–Lanczos bidiagonalization with thick
158//!   restart, its own engine, full two-sided reorthogonalization.
159//! * **S3** — `MatRef`/`MatMut` live here.
160//! * **S4** — own xoshiro256++, Marsaglia polar method, own `ln` (12.1).
161//! * **S5** — `apply(&mut self, …) -> Result`; separate [`AdjointOperator`].
162//! * **S6** — names `eigs`, `eigsh`, `svds`, `rsvd`, `range_finder`.
163//! * **S7** — Krylov–Schur restart (Stewart 2001) for [`eigs()`] and
164//!   [`eigsh()`], one engine for both (Chapter 12.6), not ARPACK's
165//!   implicit QR shifts; results compared with ARPACK.
166//! * **S8** — thin QR with five operations; Cholesky update/downdate;
167//!   Cholesky insert/delete of a variable in v0.2.
168//! * **S9** — acceptance criteria rewritten on the pilot's numbers (each
169//!   chapter states its own).
170//! * **S10** — one `#[non_exhaustive]` [`StatlaError`]; [`Sketch`] and
171//!   [`SvdWhich`] `#[non_exhaustive]`; options with public fields and
172//!   `Default`; non-convergence is `Err(NoConvergence)` unless
173//!   `allow_partial`.
174
175//!
176//! ## References
177//! Golub & Van Loan, *Matrix Computations*, 4th ed. (2013), §5.1 (Givens,
178//! Householder), §6.5 (updating). Gill, Golub, Murray & Saunders, "Methods
179//! for modifying matrix factorizations", Math. Comp. 28 (1974). Saunders,
180//! "Large-scale linear programming using the Cholesky factorization",
181//! Stanford report (1972). Stewart, "The effects of rounding error on an
182//! algorithm for downdating a Cholesky factorization", J. IMA 23 (1979).
183//! Dongarra, Bunch, Moler & Stewart, *LINPACK Users' Guide*, SIAM (1979),
184//! ch. 10 (`dchud`, `dchdd`). Daniel, Gragg, Kaufman & Stewart,
185//! "Reorthogonalization and stable algorithms for updating the Gram–Schmidt
186//! QR factorization", Math. Comp. 30 (1976). Hammarling & Lucas, "Updating
187//! the QR factorization and the least squares problem", MIMS EPrint
188//! 2008.111 (2008). Higham, *Accuracy and Stability of Numerical
189//! Algorithms*, 2nd ed. (2002), ch. 10 and 19. Halko, Martinsson & Tropp,
190//! "Finding structure with randomness", SIAM Review 53 (2011). Golub &
191//! Kahan, SIAM J. Numer. Anal. 2 (1965). Baglama & Reichel, "Augmented
192//! implicitly restarted Lanczos bidiagonalization methods", SISC 27
193//! (2005). Hestenes, J. SIAM 6 (1958); Demmel & Veselić, SIMAX 13 (1992).
194//! Blackman & Vigna, ACM TOMS 47 (2021). Marsaglia & Bray, SIAM Review 6
195//! (1964). Stewart, "A Krylov–Schur algorithm for large eigenproblems",
196//! SIMAX 23 (2001); Wu & Simon, SIMAX 22 (2000); Lehoucq, Sorensen & Yang,
197//! *ARPACK Users' Guide* (1998); Bai & Demmel, Linear Algebra Appl. 186
198//! (1993); LAPACK `dlahqr`, `dlanv2`, `dlaexc`, `dtrevc`. **All cited from
199//! memory**; no source was reopened in tasks L3.2–L3.4 (the xoshiro256++
200//! reference outputs were read in the tests of `rand` 0.9.4; ARPACK's tie
201//! order in `dngets` is recalled, and checked only against scipy's
202//! results on the fixtures).
203
204#![forbid(unsafe_code)]
205
206mod cholesky;
207mod eigs;
208mod error;
209mod jacobi;
210mod krylov;
211mod operator;
212mod qr;
213mod random;
214mod real;
215mod rsvd;
216mod schur;
217mod shift_invert;
218mod small;
219mod svds;
220mod view;
221
222/// The code blocks of the crate's README, compiled and run as doc-tests
223/// (`cargo test --doc`) so that the README never drifts from the API, as in
224/// `xingo-sparse` and `xingo-extprec`. The README is not the root
225/// documentation — this chapter is.
226#[cfg(doctest)]
227#[doc = include_str!("../README.md")]
228pub struct ReadmeDoctests;
229
230pub use cholesky::{CholOptions, Cholesky, DowndateInfo};
231pub use eigs::{Complex, Eigen, EigsOptions, EigsStats, SymEigen, Which, eigs, eigsh};
232pub use error::StatlaError;
233pub use operator::{
234    AdjointOperator, FnAdjointOperator, FnOperator, LinearOperator, OperatorError, from_fn,
235    from_fns,
236};
237pub use qr::{Qr, QrOptions};
238pub use random::Sketch;
239pub use rsvd::{RsvdOptions, Svd, SvdStats, range_finder, rsvd};
240pub use shift_invert::{ShiftInvert, SymShiftInvert, eigs_near, eigsh_near};
241pub use svds::{SvdWhich, SvdsOptions, svds};
242pub use view::{MatMut, MatRef};
243pub use xingo_sparse::{DenseBlock, DenseKernel, NaiveDense, Real};