1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
//! # 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
//! | 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 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).
/// The code blocks of the crate's README, compiled and run as doc-tests
/// (`cargo test --doc`) so that the README never drifts from the API, as in
/// `xingo-sparse` and `xingo-extprec`. The README is not the root
/// documentation — this chapter is.
;
pub use ;
pub use ;
pub use StatlaError;
pub use ;
pub use ;
pub use Sketch;
pub use ;
pub use ;
pub use ;
pub use ;
pub use ;