Skip to main content

xingo_extprec/
verify.rs

1//! # Chapter 11.10 — Verified residuals and polishing
2//!
3//! ## Purpose
4//! Two things a solver wants to know about an approximate solution `x` of
5//! `A x = b`, for the `f64` data as stored (C1 of Chapter 11):
6//!
7//! 1. *how large the residual really is* — Algorithm V returns, row by
8//!    row, an interval that **contains** `a_iᵀx − b_i`, a theorem and not
9//!    an estimate (invariant V1);
10//! 2. *a better `x`* — Algorithm P refines `x` in double-double around a
11//!    solve the caller already has (its `f64` LU), after which Algorithm V
12//!    certifies the residual that was reached;
13//! 3. *how far `x` is from the exact solution* — Algorithm E proves, from
14//!    the enclosure of Algorithm V and `n` transposed solves (`2n` with
15//!    refinement), that a square `A` is nonsingular and bounds `‖x −
16//!    A⁻¹b‖∞` and every `|x_p − (A⁻¹b)_p|`, again a theorem (Theorem E).
17//!
18//! Algorithm E bounds the error of **one** approximate solution of **one**
19//! square system with point data. Verified *solution sets* of interval
20//! systems (Rump's `verifylss` on interval data), interval LU and Krawczyk
21//! iteration stay out of v0.1 (Chapter 11, "Out of scope").
22//!
23//! ## Notation
24//! `A ∈ F^{m×n}` in compressed rows (`xingo_sparse::CsrMatrix<f64>`), `a_i`
25//! its row `i` with `k_i` stored entries, `x ∈ F^n` or `x ∈ DD^n` (each
26//! component the exact sum `h_j + ℓ_j`), `b ∈ F^m`. `u = 2⁻⁵³`. `Dot2Err`
27//! is `kernels::dot2_err` (Chapter 11.5, Algorithm C): for `f64` vectors
28//! `p`, `q` it returns a double-double `r` and an `f64` `β` with `|pᵀq − r|
29//! ≤ β` for **every** input, `β = +∞` when a hypothesis of the bound fails
30//! (invariant K2). `▽`, `△` are the directed roundings of Chapter 11.9.
31//! `‖·‖∞` is the largest absolute value of a vector and the largest
32//! absolute row sum of a matrix.
33//!
34//! ## Algorithm V (verified residual)
35//! Input: `A`, `x`, `b`. Output: intervals `R_i ∋ a_iᵀx − b_i`.
36//!
37//! V1. \[Row.\] For each row `i`, gather two `f64` vectors `p`, `q` whose
38//!     dot product is the residual, *exactly, as real numbers*:
39//!     * `x ∈ F^n`: the `k_i` pairs `(a_ij, x_j)` and the pair `(−1, b_i)`;
40//!     * `x ∈ DD^n`: the pairs `(a_ij, h_j)`, then the pairs `(a_ij,
41//!       ℓ_j)`, then `(−1, b_i)` — `2 k_i + 1` in all;
42//!     * activities: the `k_i` pairs `(a_ij, x_j)` alone.
43//! V2. \[Accumulate.\] `(r, β) ← Dot2Err(p, q)`.
44//! V3. \[Enclose.\] If `β` or `r` is not finite, `R_i ← [−∞, +∞]`.
45//!     Otherwise, with `r = h + ℓ`, `R_i ← [▽(h + ▽(ℓ − β)), △(h + △(ℓ +
46//!     β))]`: the radius is applied to the *trailing* component, where it
47//!     is of the right size, before the leading one is added.
48//!
49//! For `x ∈ DD^n` ([`residual_of_dd`]) four more steps narrow `R_i` — the
50//! *distillation* of the residual (issue #5 of the mirror; "Why the
51//! polished residual needs more" below). `N = 2 k_i + 1` is the number of
52//! pairs of V1, `(p_j, q_j)` the pairs.
53//!
54//! V4. \[Split.\] `(π_j, ε_j) ← 2Prod(p_j, q_j)` for `j = 1, …, N`; `w ←
55//!     (π_1, ε_1, π_2, ε_2, …, π_N, ε_N)`, `2N` numbers. If one of them is
56//!     not finite, keep the `R_i` of V3 and stop.
57//! V5. \[Distil, twice.\] Two passes of *VecSum*: `σ ← w_1`; for `j = 2, …,
58//!     L` (`L` the current length of `w`): `(σ, w_{j−1}) ← 2Sum(σ, w_j)`;
59//!     then `w ← (w_1, …, w_{L−1})`. The two final `σ` are `σ_1`, `σ_2`; `w`
60//!     ends with `M = 2N − 2` numbers. If a `σ` or a `w_j` is not finite,
61//!     keep the `R_i` of V3 and stop.
62//! V6. \[Tail.\] `t ← RN(… RN(RN(w_1 + w_2) + w_3) … + w_M)` and `a ←` the
63//!     same sum of the `|w_j|` (`t = a = 0` if `M = 0`). With `m = max(M,
64//!     1) − 1`: if `2 m u ≥ 1`, or `t` or `a` is not finite, keep the `R_i`
65//!     of V3 and stop. Otherwise `β′ ← sup([δ]·[a] + [φ])`, `[δ] ← [m u] /
66//!     (1 − 2[m u])`, in `Interval` (`m u` is an `f64` exactly for `m <
67//!     2⁵²`), with `φ = (3η/u)(1 + 8u)`, the floor of `β` in step C5 of
68//!     Chapter 11.5 (an `f64` exactly).
69//! V7. \[Combine.\] `(s, τ) ← 2Sum(σ_1, σ_2)`; if `s` or `τ` is not finite,
70//!     keep the `R_i` of V3 and stop. `R′_i ← ((t ± β′) + τ) + s` in
71//!     `Interval` (`t ± β′` is `Interval::mid_rad`), and `R_i ← R_i ∩ R′_i`.
72//!
73//! **Proof of (V1).** `pᵀq` is the residual exactly: for a double-double
74//! `x`, `Σ_j a_ij (h_j + ℓ_j) − b_i = Σ_j a_ij h_j + Σ_j a_ij ℓ_j + (−1)
75//! b_i`, an identity of real numbers, and the value of `x_j` *is* `h_j +
76//! ℓ_j`. So the double-double case needs no bound of its own — it is
77//! `Dot2Err` on a vector twice as long (this replaces the "second-order
78//! terms" that the contract's sketch of step V2 announced). By (K2),
79//! `|pᵀq − r| ≤ β`, i.e. `h + (ℓ − β) ≤ pᵀq ≤ h + (ℓ + β)`, and each of
80//! the two directed sums of V3 on either side moves outward. When `β =
81//! +∞` nothing is claimed (C3). ∎ (Until review X0.3i, (K2) failed when an
82//! intermediate step of the last 2Sum of Dot2Err overflowed at `±Ω`, and
83//! this proof with it; the enclosures found there still contained the
84//! residual, by the margin of V3. Now `β = +∞` in that corner and the row is
85//! `ENTIRE`: Chapter 11.5, the proof of C5, "Overflow".) (The contract's sketch had `enclose(r) +
86//! [−β, β]`, which is also correct and one to two ulps wider: it rounds
87//! `r` to its neighbours before the radius is added.)
88//!
89//! **Proof of (V1) for steps V4–V7.** Write `s* = pᵀq`, the exact residual.
90//! (a) *Split.* By (T2) of Chapter 11.1, with `π_j` finite, `p_j q_j = π_j +
91//! ε_j − μ_j` with `μ_j = 0` when the product is in the exact range and
92//! `|μ_j| ≤ η/2` otherwise; so `s* = Σ w − μ`, `|μ| ≤ N η/2`. (b) *Distil.*
93//! By (T1), a 2Sum whose outputs are finite is exact (its only failure, at
94//! `|a| = Ω`, leaves the error term not finite, and V5 tests every one), so
95//! each pass keeps the exact sum: `Σ w⁽⁰⁾ = σ_1 + Σ w⁽¹⁾ = σ_1 + σ_2 + Σ
96//! w⁽²⁾`. (c) *Tail.* `t` is a floating-point sum of the `M` numbers of
97//! `w⁽²⁾`. An addition is exact when its result is subnormal, so every
98//! addition errs by at most `u` times its result, underflow or not; none
99//! overflowed, since an infinite partial sum cannot come back finite and
100//! `t`, `a` are finite. Hence `|Σ w⁽²⁾ − t| ≤ γ_m Σ|w_j|` (the
101//! order-independent bound of Higham §4.2, `m = M − 1` additions), and
102//! since each of the `m` additions of `a` is `RN(c) = c/(1 + θ)`, `|θ| ≤
103//! u`, `Σ|w_j| ≤ (1 + u)^m a`. With `m u < 1/2`, `(1 + u)^m ≤ e^{mu} ≤ 1/(1
104//! − mu)` and `(1 − mu)² ≥ 1 − 2mu`, so `γ_m (1 + u)^m ≤ mu/(1 − 2mu) = δ`,
105//! and `|Σ w⁽²⁾ − t| ≤ δ a`. `[δ]` contains `δ` (I1; `m u` is exact), and
106//! `φ > 3 · 2⁵³ η ≥ N η/2` (`N ≤ m/2 + 2 < 2⁵¹ + 2`), so `δ a + N η/2 ≤
107//! β′`. (d) *Combine.* `σ_1 + σ_2 = s + τ` exactly (T1, both
108//! finite). So `s* = s + τ + t + (Σ w⁽²⁾ − t) − μ` lies in `((t ± β′) +
109//! τ) + s` (I1), i.e. in `R′_i`; and in the `R_i` of V3 by the proof
110//! above; so in their intersection. ∎ (When a step keeps the `R_i` of V3,
111//! nothing new is claimed.) The intersection makes V4–V7 **never widen**
112//! the enclosure of V3 (invariant V3), and leaves it bit for bit when
113//! `R′_i ⊇ R_i`. That is the case when every operation of V2 and V4–V7 is
114//! exact and the residual is an `f64`: both are then that `f64` widened by
115//! `φ` — the floor is shared so that an exact row keeps its V3 bits.
116//!
117//! **Width.** For a finite result of V3, `width(R_i) ≤ 2 ulp(r) + 2β (1 +
118//! 2u)` — typically one ulp, two when `r` is an `f64` — and `β` is of
119//! order `k² u² Σ_j |a_ij x_j|` (Chapter 11.5, step C5): the enclosure of a
120//! residual of size `ρ` computed from terms of size `S` has
121//! a relative width of about `u + k² u² S/ρ`. An `f64` solution leaves `ρ
122//! ≈ κ u S` at best, so its residual is enclosed to about 16 digits by V3
123//! alone. A polished one has `ρ ≈ k u² S`, of the order of `β` itself: V3
124//! then only proves "`|a_iᵀx − b_i| ≤ c k² u² S`".
125//!
126//! *Why the polished residual needs more, and what V4–V7 give.* VecSum
127//! leaves error terms bounded by `γ_{L−1}` times the sum of the magnitudes
128//! it was given (Ogita, Rump & Oishi, Lemma 4.2 — cited from memory; the
129//! proof above does not use it), so after two passes `Σ|w⁽²⁾| ≲ 4N²u² S`
130//! and `β′ ≲ 8 N³ u³ S`, against `β ≈ N² u² S` for Dot2Err: one more factor
131//! `N u` — the accuracy of a sum in *three* times the working precision
132//! (SumK with `K = 3`, *ibid.* Algorithm 4.8), with an a posteriori bound
133//! in place of theirs. The other terms of the width are the outward
134//! roundings of V7, a few ulps of `s*` when `|s*| ≳ β′`. With `ρ ≈ k u² S`
135//! the relative width falls from `≈ k` to `≈ u + k² u`. **Measured** on
136//! the polished optimal bases of the 93 Netlib LPs (task X0.5, rows of up
137//! to 6 185 entries): the largest half-width over `‖r‖∞` of a basis went
138//! from `126` (median) and `9.4 · 10⁴` (largest) with V3 alone to at most
139//! `7.2 · 10⁻¹¹` with V4–V7. A third pass of V5 changed none of the bounds
140//! of Algorithm E below at three digits, so the chapter stops at two.
141//!
142//! **Cost.** About 25 flops per stored entry for `x ∈ F^n`; for `x ∈ DD^n`
143//! about 50 for V1–V3 and 65 more for V4–V7 (one 2Prod, four 2Sum and the
144//! tail per pair, two pairs per entry), and two gather buffers of the
145//! length of the longest row and one of four times that. Measured (task
146//! X0.5, M2 Pro under load, eight polished Netlib systems of 2 392 to
147//! 18 301 rows): [`residual_of_dd`] takes 3.0 to 4.5 times as long as V1–V3
148//! alone (whose Dot2Err is vectorized; V4–V7 are scalar), 0.4 to 3.4 ms — at most 5 % of the time of
149//! Algorithm E on the same bases, except where the basis is far smaller
150//! than the system (fit2d: `m = 25`, Algorithm E under 1 ms).
151//! [`residual_csc`] first converts to compressed rows (`O(nnz)` time and
152//! memory).
153//!
154//! ## Algorithm P (polishing: iterative refinement with extended residuals)
155//! Input: a square `A`, `b`, an approximate solution `x ∈ DD^n` (an `f64`
156//! solution has zero trailing components), a *solve* `s ↦ d ≈ A⁻¹ s` in
157//! `f64` (a closure: the caller's LU), the parameters `τ`, `ρ` and the
158//! iteration limit of [`PolishOptions`]. Output: `x`, polished in place,
159//! and a [`PolishReport`].
160//!
161//! P1. \[Residual.\] `r ← b − A x` in double-double ([`residual_dd`]); `ν ←
162//!     ‖r‖∞`. On the first pass, `ν₀ ← ν`.
163//! P2. \[Stop?\] In this order:
164//!     (a) if `ν` is not finite: restore the previous `x` (if any) and
165//!         stop, *not finite*;
166//!     (b) if `ν > ν_prev` (after a correction): the correction made
167//!         things worse — restore the previous `x` and stop, *stagnated*;
168//!     (c) if `|r_i| ≤ τ S_i` in **every** row `i`, with `S_i = Σ_j |a_ij
169//!         x_j| + |b_i|` the size of the terms of that row (the
170//!         componentwise test; "How step P2 (c) rounds" below): stop,
171//!         *converged*;
172//!     (d) if `ν > ρ ν_prev` (after a correction): stop, *stagnated* (the
173//!         new `x` is kept: it is not worse);
174//!     (e) if the iteration limit is reached: stop, *iteration limit*.
175//! P3. \[Correct.\] `s ← RN(r)` (the leading components); `d ← solve(s)`.
176//!     If some `d_i` is not finite, stop, *not finite* (`x` is the current
177//!     one). Otherwise save `x`, set `x ← x + d` in double-double, `ν_prev
178//!     ← ν`, and return to P1.
179//!
180//! **How step P2 (c) rounds.** The test is per row because a global scale
181//! `‖A‖∞‖x‖∞ + ‖b‖∞` — the contract's — is set by the largest row of a
182//! badly scaled model and declares the small rows converged while they
183//! still carry a residual far above double-double level (measured on the
184//! Netlib bases in task L2.3). The right-hand side must not be
185//! *over*estimated, or convergence would be declared unduly. It is
186//! computed in `f64` as `t_i = RN(RN(τ Ŝ_i) · d_i)`, with `Ŝ_i` the plain
187//! left-to-right sum of `|b_i|` and the `k` products `RN(|a_ij| |h_j|)`
188//! (`h_j` the leading component of `x_j`) and the deflation `d_i = RN(1 −
189//! (2k + 10) u)`. Barring underflow, `Ŝ_i ≤ S_i (1 + u)^{k+2}` for the
190//! exact `S_i = Σ_j |a_ij x_j| + |b_i|` (one rounding per product, `|h_j|
191//! ≤ (1 + u)|x_j|`, `k` additions of nonnegative terms), two more
192//! roundings give `t_i ≤ τ S_i (1 + u)^{k+4} d_i`, and the test compares
193//! the leading component `|RN(r_i)| ≥ |r_i|/(1 + u)`. Since `(1 +
194//! u)^{k+6} ≤ 1/(1 − (k + 6)u) ≤ 1/(1 − (2k + 10)u)`, **`|RN(r_i)| ≤ t_i`
195//! implies `|r_i| ≤ τ S_i`** for the double-double `r_i` of step P1 — the
196//! rounding of the test is always against convergence. (A product that
197//! underflows adds at most `η/2` to `Ŝ_i`: rows whose terms are all below
198//! `2⁻¹⁰²²` are outside this statement. A row of `2⁵¹` entries or more
199//! never passes, and neither does a row whose `t_i` overflows: an infinite
200//! bound proves nothing about `τ S_i`.) The `r_i` themselves are computed, not enclosed: P
201//! decides when to *stop*, Algorithm V what is *proved*.
202//!
203//! A row with `Ŝ_i = 0` — an empty row with `b_i = 0`, or terms that all
204//! underflow — needs no rule of its own: the test reads `|RN(r_i)| ≤ 0`,
205//! which holds exactly when the residual of that row is zero (and for
206//! finite data it is). No quotient is formed.
207//!
208//! **Convergence by rows, progress by the norm: a measurement.** Steps
209//! (b) and (d) compare the *norm* `ν = ‖r‖∞` of successive passes, not a
210//! row-scaled quantity. The other choice — progress measured as `ω =
211//! max_i |r_i| / S_i`, the scale of test (c) — **was implemented, measured
212//! on the optimal bases of the 93 Netlib LPs and rejected** (task L2.3,
213//! 2026-11-16; same `τ`, `ρ` and iteration limit throughout):
214//!
215//! | convergence / progress | converged | stagnated | largest certified `‖r‖∞` after P |
216//! |---|---:|---:|---:|
217//! | global / global (the contract) | 93 | 0 | `2.879e-20` |
218//! | by rows / global (**this version**) | 84 | 9 | `6.778e-22` |
219//! | by rows / `ω` | 83 | 10 | `2.879e-20` |
220//!
221//! With progress in `ω`, seven bases ended with a certified residual
222//! larger than with progress in the norm (greenbea `6.778e-22 → 2.879e-20`,
223//! maros `6.975e-24 → 1.088e-22`, dfl001 `7.740e-28 → 1.445e-27`, and
224//! cycle, stocfor2, scsd1, wood1p by 2 % or less), one with a smaller one
225//! (scsd8, by 1 %), and none ended above what the contract's criterion
226//! gives.
227//!
228//! *A limitation of the row scale, measured.* The cause was read off an
229//! instrumented run (eleven bases): when the *exact* solution has `S_i =
230//! 0` in some row — a nonbasic variable at a zero bound, in its row `x_v =
231//! 0`; a constraint all of whose terms vanish — every iterate that is not
232//! exactly right there has `|r_i| = S_i` up to rounding, however small
233//! `r_i` is. So `ω` was exactly `1` before the first correction on all
234//! eleven, and still between `0.96` and `1` after it on eight of the ten
235//! that stagnated (on rows with `|r_i| = S_i` between `1e-34` and
236//! `1e-29`): it did not halve, and P stopped after one pass where the
237//! norm criterion goes on for one or two more. The same rows are,
238//! presumably (this version was not instrumented), why test (c) leaves
239//! nine bases *stagnated* here: they pass only once their residual is
240//! exactly zero. That outcome is harmless — the point
241//! reached is kept and Algorithm V certifies it — and all nine have a
242//! certified residual no larger than under the contract's criterion,
243//! except scsd8 (`1.899e-29 → 1.919e-29`).
244//!
245//! *An open lever, not measured.* The literature on componentwise
246//! backward error replaces the denominator of such rows by a norm-based
247//! one — here it would be `max(S_i, θ ‖a_i‖₁ ‖x‖∞)` for a threshold `θ`
248//! (Arioli, Demmel & Duff, 1989: **cited from memory**, not reread). It
249//! was **not implemented and not measured**; it needs a threshold, to be
250//! chosen by a campaign like the one above.
251//!
252//! **What P guarantees.** (P-mono) `ν` at exit is at most `ν₀`: steps (a)
253//! and (b) undo the only corrections that could increase it. Nothing
254//! else: P is numerical, not rigorous — its residuals are double-double
255//! values without a bound, its norms plain `f64` — and the certificate of
256//! its result is Algorithm V. Higham (2002, ch. 12): with residuals in
257//! twice the working precision and a solve of relative accuracy `κ(A) u <
258//! 1`, each pass contracts the error by about `κ(A) u`, until the residual
259//! reaches the accuracy of its own evaluation, `≈ k u² (|A||x| + |b|)`;
260//! because `x` is *stored* in double-double here, the forward error keeps
261//! falling below `u` (to about `κ(A) k u²`), which a refinement that
262//! stores `x` in `f64` cannot do.
263//!
264//! ## Algorithm E (a rigorous bound of the error, by an implicit approximate inverse)
265//! Input: a square `A ∈ F^{n×n}` (compressed rows; one compressed-column
266//! copy is made), the enclosure `[r]` of the residual `A x̃ − b` of an
267//! approximate solution `x̃` — `n` intervals, from [`residual`] (`x̃ ∈ F^n`)
268//! or [`residual_of_dd`] (`x̃ ∈ DD^n`) — a *transposed solve* `c ↦ ≈ A⁻ᵀc`
269//! in `f64` (a closure: the BTRAN of the caller's LU) and the switch
270//! `refine_rows` of [`ForwardErrorOptions`] (default on). Output
271//! ([`ForwardErrorBound`]): `ε`, the `ε_p`, `α`, the number of solves and
272//! the outcome.
273//!
274//! *Notation.* `e_p` is the `p`-th unit vector and `δ_pq` the Kronecker
275//! delta; `a_iq` are the stored entries and `a_{:q}` the column `q`. A
276//! vector `y` of row `p` has components `y_i = h_i + ℓ_i` (two `f64`, the
277//! exact sum; `ℓ = 0` without refinement). `R` is the matrix whose row `p`
278//! is the `y` that step E3 **actually used**, taken as exact real numbers:
279//! `R` is not "the inverse", it is whatever came out, and the theorem
280//! holds for every `R`. `C = I − RA` (exact, real), `x* = A⁻¹b`, `e = x̃ −
281//! x*`. `mag(X) = max{|x| : x ∈ X}`.
282//!
283//! E0. \[Dimensions; trivial cases.\] If `A` is not square or `[r]` does not
284//!     have `n` entries: [`VerifyError::Dimension`], before any arithmetic.
285//!     If `n = 0`: certified, `ε = 0`, `α = 0`, no solve. If some `[r_i]`
286//!     is empty: not certified (*not finite*), no solve.
287//! E1. \[Row of `R`.\] For `p = 1, …, n`: `h ← e_p`, `ℓ ← 0`;
288//!     `solve_transpose(h)`. If some `h_i` is not finite: not certified
289//!     (*not finite*), stop.
290//! E2. \[Refinement, optional.\] If `refine_rows`: with `Q_p` of step E3
291//!     for this `y`, `d_q ← RN(δ_pq − Dot2(a_{:q}, h))` for `q ∈ Q_p` and
292//!     `d_q ← 0` elsewhere (`Dot2` of Chapter 11.5, *not* rigorous: it only
293//!     chooses `R`); `solve_transpose(d)`; if every `d_i` and every
294//!     `fl(h_i + d_i)` is finite, `(h_i, ℓ_i) ← h_i ⊕ d_i` (the addition
295//!     `dd + f64` of Chapter 11.2, A1: the exact sum `h_i + d_i` unless
296//!     `|h_i| = Ω`, where step E may return `(fl(h_i + d_i), 0)` — either
297//!     way a pair of finite `f64`); otherwise `y` stays the one of E1.
298//!     Nothing of this step enters the proof: `R` is the pairs that came
299//!     out, exact sums or not.
300//! E3. \[Row of `C`.\] `S_p = {i : h_i ≠ 0 or ℓ_i ≠ 0}`, `Q_p = {q : a_iq is
301//!     stored for some i ∈ S_p} ∪ {p}`. For each `q ∈ Q_p`, gather the
302//!     pairs `(a_iq, h_i)` for the stored `a_iq`, then — if step E2 set
303//!     `ℓ` — the pairs `(a_iq, ℓ_i)`, and `(−1, δ_pq)`; `(s, β) ←
304//!     Dot2Err`; `M_q ← mag(V3(s, β))`. `ρ_p ← sup(Σ_{q∈Q_p} M_q)`, the sum
305//!     in `Interval`.
306//! E4. \[Row of `R[r]`.\] `G ← Σ_{i∈S_p} ([r_i]·h_i + [r_i]·ℓ_i)` in
307//!     `Interval` (a term with a zero factor is omitted); `g_p ← mag(G)`.
308//! E5. \[Early stop.\] `α ← max(α, ρ_p)` (exact). If not `α < 1`: not
309//!     certified (*not contracting*), stop; the `α` reported is that of the
310//!     rows examined.
311//! E6. \[Norm.\] After the `n` rows: `γ ← max_p g_p`; if `γ = +∞`: *not
312//!     finite*. `ε ← sup([γ, γ] / (1 − [α, α]))` in `Interval`; if `ε = +∞`:
313//!     *not finite*.
314//! E7. \[Components.\] `ε_p ← min(ε, sup([g_p, g_p] + [ρ_p, ρ_p]·ε))`, in
315//!     `Interval`.
316//!
317//! **Theorem E.** If Algorithm E ends certified, `A` is nonsingular and,
318//! for **every** `b ∈ ℝⁿ` and `x̃ ∈ ℝⁿ` with `A x̃ − b ∈ [r]` componentwise
319//! — in use, the `b` and `x̃` whose residual [`residual`] enclosed — `x* =
320//! A⁻¹b` satisfies `‖x̃ − x*‖∞ ≤ ε` and `|x̃_p − x*_p| ≤ ε_p` for `p = 1, …,
321//! n`.
322//!
323//! *Proof.* (o) *`R` is a real matrix:* every `h_i` and `ℓ_i` used is a
324//! finite `f64` — E1 refuses a non-finite `h`, E2 keeps a correction only
325//! when every `d_i` and `fl(h_i + d_i)` is finite, and the addition A1
326//! never leaves a non-finite component then (step E of Chapter 11.2). (i) *Each `M_q` dominates `|c_pq|`.* As real numbers, `Σ_i a_iq
327//! (h_i + ℓ_i) − δ_pq = Σ_i a_iq h_i + Σ_i a_iq ℓ_i + (−1) δ_pq` (when E2
328//! did not set `ℓ`, `ℓ = 0` and the second sum is omitted) is exactly the
329//! dot product of the pairs of E3, and it equals `−c_pq` (`c_pq = δ_pq −
330//! Σ_i y_i a_iq`). By (K2) of Chapter 11.5, `|−c_pq − s| ≤ β`, with `β =
331//! +∞` when a hypothesis of Dot2Err fails (a length with `2(k + 3)u ≥ 1`,
332//! an overflow — of an intermediate step at `±Ω` too, since X0.3i — a NaN) — then
333//! V3 is `ENTIRE`, `M_q = ρ_p = +∞` and E5 refuses. By the proof of (V1)
334//! the interval V3 contains `−c_pq`, hence `|c_pq| ≤ M_q`.
335//! (ii) *The columns outside `Q_p` have `c_pq = 0` exactly:* for `q ∉ Q_p`,
336//! `q ≠ p`, and every product `a_iq y_i` has a zero factor (either `a_iq`
337//! is not stored or `i ∉ S_p`, i.e. `y_i = h_i + ℓ_i = 0`).
338//! (iii) *`ρ_p ≥ Σ_q |c_pq|`:* a sum of nonnegative reals each dominated by
339//! an `f64`, computed in `Interval` (by (I1) its `sup` dominates the exact
340//! sum). Hence `‖C‖∞ = max_p Σ_q |c_pq| ≤ α < 1`.
341//! (iv) *Nonsingularity.* `RA = I − C` with `‖C‖∞ < 1` is invertible
342//! (Neumann series), so `A` and `R` are invertible; `x*` exists and is
343//! unique.
344//! (v) *`g_p ≥ |(R r)_p|` for every `r ∈ [r]`:* `(R r)_p = Σ_i (h_i + ℓ_i)
345//! r_i = Σ_i h_i r_i + Σ_i ℓ_i r_i`; each term lies in `[r_i]·h_i` or
346//! `[r_i]·ℓ_i` (I1, with a point operand), the omitted terms (`i ∉ S_p`, or
347//! a zero factor) are zero, and the sum lies in the interval sum (I1).
348//! (vi) *The bound.* `A e = A x̃ − b = r ∈ [r]`; multiplying by `R`, `(I −
349//! C) e = R r`, i.e. `e = R r + C e`. So `‖e‖∞ ≤ ‖R r‖∞ + α ‖e‖∞`, and since
350//! `α < 1`, `‖e‖∞ ≤ ‖R r‖∞/(1 − α) ≤ γ/(1 − α) ≤ ε` — the quotient in
351//! `Interval` (I1, I3), with `▽(1 − α) > 0` because `α < 1` is an `f64`.
352//! Componentwise, `|e_p| ≤ |(R r)_p| + Σ_q |c_pq| |e_q| ≤ g_p + ρ_p ‖e‖∞ ≤
353//! g_p + ρ_p ε`, whose `sup` in `Interval` is an upper bound; and `|e_p| ≤
354//! ‖e‖∞ ≤ ε`, so the minimum of the two bounds is one. ∎
355//!
356//! Nothing in the proof depends on how `y` was obtained: a wrong, noisy or
357//! adversarial `solve_transpose` can only make `α ≥ 1` (no certificate) or
358//! the bound loose, never false (invariant E1). For an exactly singular `A`
359//! there is no `R` with `‖I − RA‖∞ < 1` (it would make `A` invertible), so
360//! Algorithm E cannot certify it (invariant E2).
361//!
362//! **Where each rounding is.** This is where textbook versions of the bound
363//! fail:
364//!
365//! | quantity | computed as | enclosed by |
366//! |---|---|---|
367//! | `R` | `f64` (E1) or double-double (E2), no bound | nothing needed: `R` *is* the numbers that came out |
368//! | `c_pq` | Dot2Err on the exact pairs of E3 | (K2) and V3: `\|c_pq\| ≤ M_q`, underflow included in `β` |
369//! | `c_pq`, `q ∉ Q_p` | not computed | exactly zero (proof, ii) |
370//! | `ρ_p = Σ M_q` | `Interval` | (I1), outward, exact under underflow (I3) |
371//! | `α = max ρ_p` | `f64::max` | exact |
372//! | `r = A x̃ − b` | [`residual`], [`residual_of_dd`] | (V1) |
373//! | `(R r)_p` | `Interval`, interval × point, `h` and `ℓ` apart | (I1) |
374//! | `γ/(1 − α)`, `g_p + ρ_p ε` | `Interval` | (I1), (I3) |
375//!
376//! The errors this avoids: computing `I − RA` in floating point and taking
377//! the norm of the result (the rounding of `RA` is of the order of `C`
378//! itself); using `‖R‖ ‖r‖` with `r` recomputed in `f64` (noise of the
379//! size of the residual itself); forgetting the underflow of the products
380//! (here it is in `β`); and accumulating the products of a double-double
381//! `R` in `f64`, whose error `≈ n u Σ|R||A|` undoes the refinement — hence
382//! `h` and `ℓ` enter Dot2Err as separate pairs, the device of (V1) for a
383//! double-double `x`.
384//!
385//! **How tight, and why.** For an `f64` solution the error *is* `R r` up to
386//! `C e`, and `C` is small: in the measurements of the contract (task X0.3,
387//! decision log D-0125) `ε/‖e‖∞` was between 1.00 and 1.04 on every
388//! certified case with `α ≤ 0.04`, and 1.00 on all 93 optimal bases of
389//! Netlib. For a polished solution the same holds since steps V4–V7 of
390//! Algorithm V (task X0.5): before them its exact residual was of the
391//! order of the width of its Dot2Err enclosure ("Width" above), `g_p`
392//! reflected `|R| rad([r])`, and the overestimation `ε̂/‖e‖∞` went from
393//! 1.4 to `7.7 · 10⁴` (median about 230 over the 88 bases with a nonzero
394//! error). Measured term by term on those bases, nothing else contributed:
395//! `α ≤ 1.2 · 10⁻⁷`, so `1/(1 − α)` and `ρ_p ε` are invisible at three
396//! digits, and with `[r]` replaced by a tight enclosure of the *exact*
397//! residual (computed in rationals) the ratio was already 1.000 on every
398//! basis — `|R| |r|` does not overestimate `|R r|` there. With V4–V7 the
399//! ratio is 1.000 at three digits on all 88 too (the true error bracketed
400//! rigorously, by Algorithm E itself on `A e = A x̂ − b` with the exact
401//! residual), and at most `1 + 5 · 10⁻⁶` on the dense test matrices of
402//! `κ ≤ 10¹⁴` (before: up to 572). One solve per row
403//! leaves `α` of the order of `κ(A) u`; the refinement E2 lowers it by
404//! orders of magnitude (`7.5 · 10⁻³ → 3.1 · 10⁻⁶` at `κ = 10¹⁴`, order
405//! 20): measured, it certifies dense matrices up to `κ ≈ 10¹⁶`, where one
406//! solve per row stops near `10¹⁴`.
407//!
408//! **A basis of a linear program.** The right-hand side `b = −K_N β_N` of
409//! a basis is not made of `f64` values. Pass `A = B` and, as `[r]`, the
410//! enclosure of the first `m` rows of the square system of order `n + m`
411//! of `xingo-simplex`'s `residual_certificates` test (`K z = 0`, `z_v =
412//! β_v` for the nonbasic `v`), evaluated with the nonbasic variables set
413//! **exactly** to their bounds: those rows are then `B z_B − b` exactly,
414//! and Theorem E holds for the exact real `b`.
415//!
416//! **Cost.** `n` calls of `solve_transpose` (`2n` with `refine_rows`), plus
417//! `Σ_p Σ_{q∈Q_p} (nnz(a_{:q}) + 1)` pairs of Dot2Err (about 25 flops each;
418//! up to twice as many with refinement) — `n · nnz(A)` at worst — and an
419//! `O(n)` scan per row for `S_p`. Memory `O(n + nnz(A))`: one
420//! compressed-column copy, a few vectors of length `n`, buffers of the
421//! length of the longest column. Measured (X0.3, a loaded machine): 10.8 s
422//! summed over the 93 optimal bases of Netlib with refinement, the largest
423//! (dfl001, `m = 6 071`) 3.7 s; on a sparse synthetic family `n = 10⁴` in
424//! 21 s and `3 · 10⁴` in 271 s — quadratic in `n`, because each solve and
425//! each scan is `O(n)` with dense vectors.
426//!
427//! **What stays out.** Bounds in the 2-norm (by `σ_min`; rejected by the
428//! measurements of X0.3); an explicit `R`; a componentwise criterion with a
429//! vector `v ≠ 𝟙` (Perron, H-matrices: another pass of `n` solves);
430//! Krawczyk iteration; bounds through the LU factors with comparison
431//! matrices (they would need the factors of `xingo-sparse`, which are
432//! opaque); parallel rows; a bound for a subset of the components (`α` is
433//! global); interval `A` or `b`. The transposed system needs no function of
434//! its own: call again with `Aᵀ` and the FTRAN as the solve.
435//!
436//! ## Invariants
437//! (V1) *Residuals.* [`residual`]`(A, x, b)[i] ∋ a_iᵀx − b_i`, and likewise
438//!      [`residual_of_dd`], [`residual_csc`] and [`activity`] (`∋ a_iᵀx`),
439//!      for every row and every input; an unbounded interval when a
440//!      hypothesis fails (C3). Checked against exact rationals.
441//! (V2) *Well-formed.* Every interval returned satisfies (I2) of Chapter
442//!      11.9 and is not empty (a `debug_assert!`).
443//! (V3) *Never wider.* Each row of [`residual_of_dd`] is contained in the
444//!      enclosure of steps V1–V3 for the same pairs (by construction, the
445//!      intersection of V7; a `debug_assert!`; an empty intersection, which
446//!      only a defect could produce, falls back to the enclosure of V3).
447//!      Checked against exact rationals, with the width `≤ 8u|s*| +
448//!      2⁻¹²⁸S + 2⁻¹⁰⁰⁰`, and on a row built so that the tail bound `β′`
449//!      is needed to within a factor 1.7 (`tests/data/tail_bound_row.txt`).
450//! (P1) *Monotone.* [`PolishReport::residual_after`] `≤`
451//!      [`PolishReport::residual_before`] whenever the latter is finite (a
452//!      `debug_assert!`).
453//! (P2) *Untouched on failure.* With [`PolishStop::NotFinite`] and zero
454//!      iterations, `x` is the input.
455//! (E1) *Never false.* [`ForwardErrorOutcome::Certified`] implies Theorem
456//!      E for the stored data, whatever the closure (a wrong one can only
457//!      prevent the certificate). Checked against exact rationals, with
458//!      adversarial closures.
459//! (E2) *Nonsingular.* Certified implies `A` nonsingular; an exactly
460//!      singular `A` is never certified (checked).
461//! (E3) *Shape.* Certified ⇔ `ε` finite ⇔ every `ε_p` finite; then `0 ≤
462//!      ε_p ≤ ε` and `0 ≤ α < 1`. Not certified ⇒ `ε = +∞` and every `ε_p =
463//!      +∞` (a `debug_assert!`).
464//! (E4) *Deterministic.* The same bits for the same data and the same
465//!      closure (K1, D5), if the closure is a function of its argument.
466//!      The BTRAN of `xingo_sparse::Lu` is not, by design: it chooses
467//!      between its hypersparse and its dense path by a moving average of
468//!      the density of the previous results, so two equal calls can sum in
469//!      different orders (on one Netlib basis, share1b, they returned other
470//!      bits); the same sequence of calls gives the same bits. Each result
471//!      is a theorem for its own `R` either way.
472//!
473//! ## References
474//! Ogita, Rump & Oishi, "Accurate sum and dot product", SIAM J. Sci.
475//! Comput. 26 (2005), Algorithm 5.8 and Corollary 5.9 (through Chapter
476//! 11.5, which adapts and proves them), and VecSum and SumK (their
477//! Algorithms 4.3 and 4.8, Lemma 4.2), the model of steps V4–V7 — **cited
478//! from memory**; the a posteriori bound of V6 and its proof are this
479//! chapter's; Higham, *Accuracy and Stability of
480//! Numerical Algorithms*, 2nd ed. (2002), ch. 12 (iterative refinement;
481//! §12.1 for the mixed-precision form) — **cited from memory**, the
482//! statement above is the qualitative one and nothing in the code depends
483//! on its constants; Rump, "Verification methods: rigorous results using
484//! floating-point arithmetic", Acta Numerica 19 (2010) — the distinction
485//! between a verified residual and a verified solution, and (§10) the bound
486//! `‖I − RA‖ ≤ α < 1 ⇒ ‖x̃ − x*‖ ≤ ‖R(A x̃ − b)‖/(1 − α)` for an
487//! approximate inverse `R` that Algorithm E applies one implicit row at a
488//! time (*cited from memory, not reread*; the constants and the proof of
489//! Theorem E are this chapter's, from (K2), (V1) and (I1)–(I3) only).
490//! Before release the proof and the code of Algorithm E were reviewed by an
491//! independent reviewer (task X0.3, 262 000 adversarial cases of order at
492//! most 8 checked in exact arithmetic): no false bound; the review found
493//! the corner of (K2) fixed in Chapter 11.5 and the textual corrections of
494//! steps E2 and (o) above.
495
496use xingo_sparse::{Col, CscMatrix, CsrMatrix, Row};
497
498use crate::dd::DoubleDouble;
499use crate::eft::{two_prod, two_sum};
500use crate::interval::Interval;
501use crate::kernels;
502
503/// What went wrong before any arithmetic. (`Display` and
504/// `core::error::Error` are implemented.)
505#[derive(Clone, Debug, PartialEq, Eq)]
506#[non_exhaustive]
507pub enum VerifyError {
508    /// `x` or `b` has the wrong length for `A` (for [`polish`], also: `A`
509    /// is not square — `expected` is its number of rows, `got` its number
510    /// of columns; for [`forward_error_bound`], also: `A` not square or `r`
511    /// of the wrong length).
512    Dimension {
513        /// What was expected.
514        expected: usize,
515        /// What was given.
516        got: usize,
517    },
518}
519
520impl core::fmt::Display for VerifyError {
521    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
522        match self {
523            Self::Dimension { expected, got } => {
524                write!(f, "dimension mismatch: expected {expected}, got {got}")
525            }
526        }
527    }
528}
529
530impl core::error::Error for VerifyError {}
531
532/// `Ok` iff `got == expected`.
533fn dimension(expected: usize, got: usize) -> Result<(), VerifyError> {
534    if got == expected {
535        Ok(())
536    } else {
537        Err(VerifyError::Dimension { expected, got })
538    }
539}
540
541/// Step V3: the interval of `r ± β`.
542fn enclosure(r: DoubleDouble, beta: f64) -> Interval {
543    // False for a NaN `β` too. A non-finite `r` comes with `β = +∞` (K2);
544    // it is tested all the same.
545    let known = beta.is_finite() && beta >= 0.0 && r.hi().is_finite() && r.lo().is_finite();
546    let x = if known {
547        Interval::mid_rad(r.lo(), beta) + r.hi()
548    } else {
549        Interval::ENTIRE
550    };
551    debug_assert!(
552        x.check_invariants().is_ok() && !x.is_empty(),
553        "V2: {x:?} from r = {r:?}, β = {beta:e}"
554    );
555    x
556}
557
558/// One pass of VecSum (step V5): replaces `w` by the errors of the cascade
559/// of 2Sum over it (one shorter) and returns the sum; `None` if a value
560/// produced is not finite (then nothing is claimed: (T1)).
561fn vec_sum(w: &mut Vec<f64>) -> Option<f64> {
562    let Some(&first) = w.first() else {
563        return Some(0.0);
564    };
565    let mut sigma = first;
566    for j in 1..w.len() {
567        let (s, e) = two_sum(sigma, w[j]);
568        if !(s.is_finite() && e.is_finite()) {
569            return None;
570        }
571        w[j - 1] = e;
572        sigma = s;
573    }
574    w.pop();
575    Some(sigma)
576}
577
578/// `φ = (3η/u)(1 + 8u)`, the underflow term of step V6: the floor of `β` in
579/// step C5 of Chapter 11.5, exactly (the product is an `f64`).
580const FLOOR: f64 = 6.0 * f64::MIN_POSITIVE * (1.0 + 4.0 * f64::EPSILON);
581
582/// Steps V4–V7 for the pairs `(p, q)`: `R′ ∋ pᵀq`, or `None` when a step
583/// keeps the enclosure of V3. `w` is a buffer.
584fn distilled(p: &[f64], q: &[f64], w: &mut Vec<f64>) -> Option<Interval> {
585    /// `2(m u) < 1` iff `m < 2⁵²`.
586    // `u64`, not `usize`: `2⁵²` does not fit a 32-bit `usize` (i686, wasm32).
587    const MAX_TERMS: u64 = 1 << 52;
588    // V4.
589    w.clear();
590    for (&pj, &qj) in p.iter().zip(q) {
591        let (pi, eps) = two_prod(pj, qj);
592        if !(pi.is_finite() && eps.is_finite()) {
593            return None;
594        }
595        w.push(pi);
596        w.push(eps);
597    }
598    // V5.
599    let sigma_1 = vec_sum(w)?;
600    let sigma_2 = vec_sum(w)?;
601    // V6: `t` and `a` left to right, as the chapter states.
602    let (mut t, mut a) = (0.0_f64, 0.0_f64);
603    for &v in w.iter() {
604        t += v;
605        a += v.abs();
606    }
607    let m = w.len().max(1) - 1;
608    if u64::try_from(m).map_or(true, |m| m >= MAX_TERMS) || !(t.is_finite() && a.is_finite()) {
609        return None;
610    }
611    #[allow(clippy::cast_precision_loss)] // exact: m < 2⁵²
612    let mu = m as f64 * U;
613    let delta = Interval::point(mu) / (1.0 - Interval::point(2.0 * mu));
614    let beta = upper((delta * Interval::point(a) + Interval::point(FLOOR)).sup());
615    if !beta.is_finite() {
616        return None;
617    }
618    // V7.
619    let (s, tau) = two_sum(sigma_1, sigma_2);
620    if !(s.is_finite() && tau.is_finite()) {
621        return None;
622    }
623    Some(Interval::mid_rad(t, beta) + tau + s)
624}
625
626/// Algorithm V over the rows of `a`: `fill(i, cols, vals, p, q)` appends
627/// to the empty `(p, q)` the pairs of row `i` (step V1); with `distil`,
628/// steps V4–V7 narrow each row.
629fn rows(
630    a: &CsrMatrix<f64>,
631    distil: bool,
632    mut fill: impl FnMut(usize, &[u32], &[f64], &mut Vec<f64>, &mut Vec<f64>),
633) -> Vec<Interval> {
634    let (mut p, mut q, mut w) = (Vec::new(), Vec::new(), Vec::new());
635    (0..a.n_rows())
636        .map(|i| {
637            p.clear();
638            q.clear();
639            let (cols, vals) = a.row(Row::from_usize(i));
640            fill(i, cols, vals, &mut p, &mut q); // V1
641            let (r, beta) = kernels::dot2_err(&p, &q); // V2
642            let x = enclosure(r, beta); // V3
643            if !distil {
644                return x;
645            }
646            match distilled(&p, &q, &mut w) {
647                None => x,
648                Some(narrow) => {
649                    let y = x.intersection(narrow);
650                    debug_assert!(
651                        !y.is_empty() && y.is_subset_of(x),
652                        "V1/V3: {x:?} ∩ {narrow:?} in row {i}"
653                    );
654                    // Both contain the residual, so the intersection is never
655                    // empty; should a defect of V4–V7 make it so, a release
656                    // build falls back to the enclosure of V3 (V2).
657                    if y.is_empty() { x } else { y }
658                }
659            }
660        })
661        .collect()
662}
663
664/// Algorithm V for an `f64` solution: `R_i ∋ a_iᵀx − b_i` (invariant V1 of
665/// Chapter 11.10), for the stored `f64` values. A row whose bound cannot
666/// be established (overflow, a NaN or an infinity in the data) gets
667/// [`Interval::ENTIRE`].
668///
669/// # Errors
670/// [`VerifyError::Dimension`].
671///
672/// # Panics
673/// If `a` violates the invariants of its type (a column index out of
674/// range).
675pub fn residual(a: &CsrMatrix<f64>, x: &[f64], b: &[f64]) -> Result<Vec<Interval>, VerifyError> {
676    dimension(a.n_cols(), x.len())?;
677    dimension(a.n_rows(), b.len())?;
678    Ok(rows(a, false, |i, cols, vals, p, q| {
679        p.extend_from_slice(vals);
680        q.extend(cols.iter().map(|&j| x[j as usize]));
681        p.push(-1.0);
682        q.push(b[i]);
683    }))
684}
685
686/// Algorithm V for a double-double (polished) solution: `R_i ∋ a_iᵀx −
687/// b_i` for the exact values `hi + lo` of the components of `x`. Steps
688/// V4–V7 of Chapter 11.10 distil the residual as if it were summed in
689/// three times the working precision, so that the width follows a residual
690/// of double-double size: a few ulps of it plus `≈ 8N³u³ Σ_j |a_ij x_j|`
691/// for `N = 2k + 1` pairs, never wider than the Dot2Err enclosure of steps
692/// V1–V3 (invariant V3).
693///
694/// # Errors
695/// [`VerifyError::Dimension`].
696///
697/// # Panics
698/// If `a` violates the invariants of its type.
699pub fn residual_of_dd(
700    a: &CsrMatrix<f64>,
701    x: &[DoubleDouble],
702    b: &[f64],
703) -> Result<Vec<Interval>, VerifyError> {
704    dimension(a.n_cols(), x.len())?;
705    dimension(a.n_rows(), b.len())?;
706    // V1: the leading terms first, then the trailing ones; V4–V7.
707    Ok(rows(a, true, |i, cols, vals, p, q| {
708        p.extend_from_slice(vals);
709        q.extend(cols.iter().map(|&j| x[j as usize].hi()));
710        p.extend_from_slice(vals);
711        q.extend(cols.iter().map(|&j| x[j as usize].lo()));
712        p.push(-1.0);
713        q.push(b[i]);
714    }))
715}
716
717/// As [`residual`] for a column-compressed matrix (one scatter pass;
718/// `O(nnz)` extra memory for the row gather).
719///
720/// # Errors
721/// [`VerifyError::Dimension`].
722///
723/// # Panics
724/// If `a` violates the invariants of its type.
725pub fn residual_csc(
726    a: &CscMatrix<f64>,
727    x: &[f64],
728    b: &[f64],
729) -> Result<Vec<Interval>, VerifyError> {
730    dimension(a.n_cols(), x.len())?;
731    dimension(a.n_rows(), b.len())?;
732    residual(&a.to_csr(), x, b)
733}
734
735/// `b − A x` in double-double, not rigorous (step P1): each component
736/// within `≈ k u²` relative to `Σ|a_ij x_j| + |b_i|`, `k` the number of
737/// entries of the row (`kernels::dot_mixed`, then one subtraction). Note
738/// the sign: the *interval* residuals of this module enclose `A x − b`.
739///
740/// # Errors
741/// [`VerifyError::Dimension`].
742///
743/// # Panics
744/// If `a` violates the invariants of its type.
745pub fn residual_dd(
746    a: &CsrMatrix<f64>,
747    x: &[DoubleDouble],
748    b: &[f64],
749) -> Result<Vec<DoubleDouble>, VerifyError> {
750    dimension(a.n_cols(), x.len())?;
751    dimension(a.n_rows(), b.len())?;
752    let mut gathered = Vec::new();
753    Ok(b.iter()
754        .enumerate()
755        .map(|(i, &bi)| {
756            let (cols, vals) = a.row(Row::from_usize(i));
757            gathered.clear();
758            gathered.extend(cols.iter().map(|&j| x[j as usize]));
759            DoubleDouble::from_f64(bi) - kernels::dot_mixed(&gathered, vals)
760        })
761        .collect())
762}
763
764/// A rigorous upper bound of `‖R‖∞ = max_i mag(R_i)` (`+∞` if some `R_i`
765/// is unbounded; `0` for no rows). An **empty** `R_i` also gives `+∞`: no
766/// function of this module returns one, and an empty enclosure proves
767/// nothing (Chapter 11.9).
768#[must_use]
769pub fn norm_inf_bound(r: &[Interval]) -> f64 {
770    r.iter().fold(0.0, |norm: f64, x| {
771        if x.is_empty() {
772            f64::INFINITY
773        } else {
774            norm.max(x.mag())
775        }
776    })
777}
778
779/// Row activities with bounds, for feasibility certificates: `S_i ∋
780/// a_iᵀx`, to be tested with `certainly_le(u_i + t)` and
781/// `certainly_ge(l_i − t)`.
782///
783/// # Errors
784/// [`VerifyError::Dimension`].
785///
786/// # Panics
787/// If `a` violates the invariants of its type.
788pub fn activity(a: &CsrMatrix<f64>, x: &[f64]) -> Result<Vec<Interval>, VerifyError> {
789    dimension(a.n_cols(), x.len())?;
790    Ok(rows(a, false, |_, cols, vals, p, q| {
791        p.extend_from_slice(vals);
792        q.extend(cols.iter().map(|&j| x[j as usize]));
793    }))
794}
795
796/// The parameters of Algorithm P. No literal lives in the kernel: the
797/// defaults are here.
798#[derive(Clone, Copy, Debug, PartialEq)]
799pub struct PolishOptions {
800    /// `τ` of step P2: convergence is `|r_i| ≤ τ (Σ_j |a_ij x_j| + |b_i|)`
801    /// in every row `i` — relative to the terms of *that* row, not to a
802    /// global norm (default `2⁻⁹⁰`).
803    pub tol: f64,
804    /// `ρ` of step P2: stop unless the norm `‖r‖∞` fell below `ρ` times
805    /// its previous value (default `0.5`). Progress is measured in the
806    /// norm although convergence is tested row by row: Chapter 11.10 has
807    /// the measurement behind that choice.
808    pub min_progress: f64,
809    /// Iteration limit (default 10).
810    pub max_iter: u32,
811}
812
813impl Default for PolishOptions {
814    fn default() -> Self {
815        Self {
816            // 2⁻⁹⁰ = 2¹⁶ u²: sixteen binary digits above the accuracy `≈ 3k
817            // u²` of the double-double residual of a row of `k` entries,
818            // so reachable for rows of up to thousands of entries.
819            tol: f64::from_bits((1023 - 90) << 52),
820            min_progress: 0.5,
821            max_iter: 10,
822        }
823    }
824}
825
826/// Why Algorithm P stopped.
827#[derive(Clone, Copy, Debug, PartialEq, Eq)]
828#[non_exhaustive]
829pub enum PolishStop {
830    /// The test of step P2 (c) holds in every row.
831    Converged,
832    /// The norm of the residual stopped shrinking, or a correction
833    /// increased it and was undone, before every row passed the test of
834    /// convergence: `κ(A) u ≳ 1`, the solve is not a solve of `A` — or,
835    /// **commonly and harmlessly**, the residual is already at the
836    /// accuracy of double-double while some row whose exact terms are all
837    /// zero cannot pass a relative test (9 of the 93 optimal bases of
838    /// Netlib; Chapter 11.10). The point reached is kept.
839    Stagnated,
840    /// [`PolishOptions::max_iter`] corrections were made.
841    IterationLimit,
842    /// A residual or a correction was not finite.
843    NotFinite,
844}
845
846/// The outcome of Algorithm P.
847#[derive(Clone, Debug, PartialEq)]
848#[non_exhaustive]
849pub struct PolishReport {
850    /// Why it stopped.
851    pub stop: PolishStop,
852    /// Corrections applied (and kept: one undone by step P2 does not
853    /// count).
854    pub iterations: u32,
855    /// `‖b − A x⁰‖∞` (double-double residual, as an `f64`).
856    pub residual_before: f64,
857    /// `‖b − A x‖∞` at the end.
858    pub residual_after: f64,
859}
860
861/// `‖v‖∞` of the leading components; NaN if a component is NaN.
862fn norm_inf(v: &[DoubleDouble]) -> f64 {
863    v.iter().fold(0.0, |norm: f64, c| {
864        let h = c.hi().abs();
865        // `f64::max` would drop a NaN.
866        if h.is_nan() || norm.is_nan() {
867            f64::NAN
868        } else {
869            norm.max(h)
870        }
871    })
872}
873
874/// `2⁻⁵³`.
875const U: f64 = 0.5 * f64::EPSILON;
876
877/// Step P2 (c): `|RN(r_i)| ≤ t_i` in every row, with `t_i` rounded against
878/// convergence (the chapter, "How step P2 (c) rounds").
879fn rows_converged(
880    a: &CsrMatrix<f64>,
881    x: &[DoubleDouble],
882    b: &[f64],
883    r: &[DoubleDouble],
884    tol: f64,
885) -> bool {
886    r.iter().zip(b).enumerate().all(|(i, (ri, bi))| {
887        let (cols, vals) = a.row(Row::from_usize(i));
888        let mut s = bi.abs();
889        for (&j, v) in cols.iter().zip(vals) {
890            s += v.abs() * x[j as usize].hi().abs();
891        }
892        #[allow(clippy::cast_precision_loss)] // a deflation: any rounding is covered
893        let deflate = 1.0 - (2 * cols.len() + 10) as f64 * U;
894        let t = tol * s * deflate;
895        // False for a NaN on either side, and for a bound that overflowed:
896        // an infinite `t` says nothing about `τ S_i`.
897        t.is_finite() && ri.hi().abs() <= t
898    })
899}
900
901/// Algorithm P. `x` enters as the approximate solution (trailing
902/// components zero for an `f64` solution) and leaves polished; `solve`
903/// overwrites its argument `s` with `≈ A⁻¹ s` in `f64`.
904///
905/// The residual norm never increases (invariant P1 of Chapter 11.10): a
906/// correction that makes it worse is undone. The result is *not* a
907/// certificate; [`residual_of_dd`] certifies it.
908///
909/// # Errors
910/// [`VerifyError::Dimension`], also when `a` is not square.
911///
912/// # Panics
913/// If `a` violates the invariants of its type.
914pub fn polish(
915    a: &CsrMatrix<f64>,
916    b: &[f64],
917    x: &mut [DoubleDouble],
918    solve: &mut dyn FnMut(&mut [f64]),
919    opts: &PolishOptions,
920) -> Result<PolishReport, VerifyError> {
921    dimension(a.n_cols(), x.len())?;
922    dimension(a.n_rows(), b.len())?;
923    dimension(a.n_rows(), a.n_cols())?;
924    let mut previous: Vec<DoubleDouble> = x.to_vec();
925    let mut s = vec![0.0; b.len()];
926    let mut iterations = 0_u32;
927    let mut nu_prev = f64::INFINITY;
928    let mut nu_first = f64::NAN;
929    let (stop, nu) = loop {
930        // P1.
931        let r = residual_dd(a, x, b)?;
932        let nu = norm_inf(&r);
933        if iterations == 0 {
934            nu_first = nu;
935        }
936        // P2.
937        if !nu.is_finite() || nu > nu_prev {
938            let stop = if nu.is_finite() {
939                PolishStop::Stagnated // (b)
940            } else {
941                PolishStop::NotFinite // (a)
942            };
943            if iterations > 0 {
944                x.copy_from_slice(&previous);
945                iterations -= 1;
946                break (stop, nu_prev);
947            }
948            break (stop, nu);
949        }
950        if rows_converged(a, x, b, &r, opts.tol) {
951            break (PolishStop::Converged, nu); // (c)
952        }
953        if iterations > 0 && nu > opts.min_progress * nu_prev {
954            break (PolishStop::Stagnated, nu); // (d)
955        }
956        if iterations >= opts.max_iter {
957            break (PolishStop::IterationLimit, nu); // (e)
958        }
959        // P3.
960        for (si, ri) in s.iter_mut().zip(&r) {
961            *si = ri.hi();
962        }
963        solve(&mut s);
964        if !s.iter().all(|d| d.is_finite()) {
965            break (PolishStop::NotFinite, nu);
966        }
967        previous.copy_from_slice(x);
968        for (xi, &di) in x.iter_mut().zip(&s) {
969            // The `dd + f64` addition (Chapter 11.2), not a promotion.
970            #[allow(clippy::assign_op_pattern)]
971            {
972                *xi = *xi + di;
973            }
974        }
975        nu_prev = nu;
976        iterations += 1;
977    };
978    debug_assert!(
979        !nu_first.is_finite() || nu <= nu_first,
980        "P1: the residual grew from {nu_first:e} to {nu:e}"
981    );
982    Ok(PolishReport {
983        stop,
984        iterations,
985        residual_before: nu_first,
986        residual_after: nu,
987    })
988}
989
990/// The parameters of Algorithm E.
991#[derive(Clone, Copy, Debug, PartialEq, Eq)]
992pub struct ForwardErrorOptions {
993    /// Refine each row of the implicit inverse once in double-double
994    /// (step E2): up to twice the solves (default `true`). Measured on dense
995    /// matrices, it certified up to `κ(A) ≈ 1e16` where one solve per row
996    /// stopped near `1e14` — a measurement, not a guarantee: whether a
997    /// matrix is certified depends on the solve and the data, not on `κ`
998    /// alone.
999    pub refine_rows: bool,
1000}
1001
1002impl Default for ForwardErrorOptions {
1003    fn default() -> Self {
1004        Self { refine_rows: true }
1005    }
1006}
1007
1008/// Why Algorithm E stopped.
1009#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1010#[non_exhaustive]
1011pub enum ForwardErrorOutcome {
1012    /// The bounds are a theorem (Chapter 11.10, Theorem E).
1013    Certified,
1014    /// `‖I − RA‖∞ < 1` could not be shown: `A` singular or too
1015    /// ill-conditioned for the solve, or the solve is not one of `Aᵀ`.
1016    NotContracting,
1017    /// A solve, the residual enclosure or the bound was not finite.
1018    NotFinite,
1019}
1020
1021/// The outcome of Algorithm E.
1022#[derive(Clone, Debug, PartialEq)]
1023#[non_exhaustive]
1024pub struct ForwardErrorBound {
1025    /// Why it stopped.
1026    pub outcome: ForwardErrorOutcome,
1027    /// `ε ≥ ‖x − x*‖∞` (`+∞` unless certified).
1028    pub norm_inf: f64,
1029    /// `ε_p ≥ |x_p − x*_p|`, `0 ≤ ε_p ≤ ε` (all `+∞` unless certified).
1030    pub componentwise: Vec<f64>,
1031    /// `α ≥ ‖I − RA‖∞` over the rows examined: `< 1` when certified;
1032    /// `≥ 1` when [`ForwardErrorOutcome::NotContracting`]; with
1033    /// [`ForwardErrorOutcome::NotFinite`], the value reached when it
1034    /// stopped (`0` if no row was examined).
1035    pub contraction: f64,
1036    /// Calls of `solve_transpose`.
1037    pub solves: usize,
1038}
1039
1040impl ForwardErrorBound {
1041    /// The outcome is [`ForwardErrorOutcome::Certified`].
1042    pub fn is_certified(&self) -> bool {
1043        self.outcome == ForwardErrorOutcome::Certified
1044    }
1045
1046    /// No certificate: every bound `+∞` (invariant E3).
1047    fn refused(outcome: ForwardErrorOutcome, n: usize, contraction: f64, solves: usize) -> Self {
1048        Self {
1049            outcome,
1050            norm_inf: f64::INFINITY,
1051            componentwise: vec![f64::INFINITY; n],
1052            contraction,
1053            solves,
1054        }
1055    }
1056
1057    /// Invariant E3.
1058    fn check_invariants(&self) -> Result<(), &'static str> {
1059        let finite = self.norm_inf.is_finite();
1060        if self.is_certified() {
1061            if !(finite && self.norm_inf >= 0.0) {
1062                return Err("E3: a certificate with an infinite or negative ε");
1063            }
1064            if !(0.0..1.0).contains(&self.contraction) {
1065                return Err("E3: a certificate with α outside [0, 1)");
1066            }
1067            if !self
1068                .componentwise
1069                .iter()
1070                .all(|&c| c >= 0.0 && c <= self.norm_inf)
1071            {
1072                return Err("E3: some ε_p outside [0, ε]");
1073            }
1074        } else if finite || self.componentwise.iter().any(|c| c.is_finite()) {
1075            return Err("E3: a finite bound without a certificate");
1076        }
1077        Ok(())
1078    }
1079}
1080
1081/// An upper bound as computed, with a NaN read as `+∞`: it proves nothing
1082/// (invariant C3 of Chapter 11), and `f64::max` and `f64::min` would drop
1083/// it.
1084fn upper(x: f64) -> f64 {
1085    if x.is_nan() { f64::INFINITY } else { x }
1086}
1087
1088/// `δ_pq`.
1089fn kronecker(p: usize, q: usize) -> f64 {
1090    if p == q { 1.0 } else { 0.0 }
1091}
1092
1093/// Step E3, the sets: `support ← S_p` (the `i` with `h_i ≠ 0` or `ℓ_i ≠
1094/// 0`) and `cols ← Q_p` (the columns stored in the rows of `S_p`, and
1095/// `p`), each without repetition; `mark` is all `false` on entry and on
1096/// exit.
1097fn row_sets(
1098    a: &CsrMatrix<f64>,
1099    p: usize,
1100    (h, l): (&[f64], &[f64]),
1101    mark: &mut [bool],
1102    support: &mut Vec<usize>,
1103    cols: &mut Vec<usize>,
1104) {
1105    support.clear();
1106    cols.clear();
1107    for (i, (&hi, &li)) in h.iter().zip(l).enumerate() {
1108        if hi != 0.0 || li != 0.0 {
1109            support.push(i);
1110            for &q in a.row(Row::from_usize(i)).0 {
1111                let q = q as usize;
1112                if !mark[q] {
1113                    mark[q] = true;
1114                    cols.push(q);
1115                }
1116            }
1117        }
1118    }
1119    if !mark[p] {
1120        mark[p] = true;
1121        cols.push(p);
1122    }
1123    for &q in cols.iter() {
1124        mark[q] = false;
1125    }
1126}
1127
1128/// Algorithm E: from `r ∋ A x − b` (from [`residual`] or
1129/// [`residual_of_dd`]) and a transposed solve (`c ← ≈ A⁻ᵀ c`, `f64`),
1130/// proves that `A` is nonsingular and bounds `x − A⁻¹b` (Theorem E of
1131/// Chapter 11.10): if the result is certified, then for the `b` whose
1132/// residual `r` encloses — precisely, for every `x` and `b` with `A x − b ∈
1133/// r` componentwise — `‖x − A⁻¹b‖∞ ≤ norm_inf` and `|x_p − (A⁻¹b)_p| ≤
1134/// componentwise[p]`, for the stored `f64` values of `A`.
1135///
1136/// The bound is a theorem **whatever** `solve_transpose` returns: a wrong
1137/// solve can only prevent the certificate or loosen the bound. It is called
1138/// at most `n` times (at most `2n` with
1139/// [`ForwardErrorOptions::refine_rows`]; fewer when it stops early), each
1140/// time on a vector of length `n`.
1141///
1142/// ```
1143/// use xingo_extprec::verify::{
1144///     ForwardErrorOptions, forward_error_bound, residual,
1145/// };
1146/// use xingo_sparse::CsrMatrix;
1147///
1148/// // [[2, 1], [1, 3]] x = (1, 1): x* = (2/5, 1/5), not representable.
1149/// let a = CsrMatrix::from_raw_parts(2, vec![0, 2, 4], vec![0, 1, 0, 1],
1150///     vec![2.0, 1.0, 1.0, 3.0]).unwrap();
1151/// let (b, x) = ([1.0, 1.0], [0.4, 0.2]);
1152/// // Aᵀ = A: the transposed solve is the exact inverse, rounded.
1153/// let mut solve_t = |c: &mut [f64]| {
1154///     let (p, q) = (c[0], c[1]);
1155///     c[0] = (3.0 * p - q) / 5.0;
1156///     c[1] = (2.0 * q - p) / 5.0;
1157/// };
1158/// let r = residual(&a, &x, &b).unwrap();
1159/// let e = forward_error_bound(&a, &r, &mut solve_t, &ForwardErrorOptions::default())
1160///     .unwrap();
1161/// assert!(e.is_certified() && e.contraction < 1e-15);
1162/// // |0.4 − 2/5| and |0.2 − 1/5| are below 2⁻⁵⁴ and 2⁻⁵⁵.
1163/// assert!(e.norm_inf < 1e-16 && e.componentwise[1] < 1e-16);
1164/// ```
1165///
1166/// # Errors
1167/// [`VerifyError::Dimension`] if `a` is not square or `r` does not have
1168/// one entry per row.
1169///
1170/// # Panics
1171/// If `a` violates the invariants of its type.
1172pub fn forward_error_bound(
1173    a: &CsrMatrix<f64>,
1174    r: &[Interval],
1175    solve_transpose: &mut dyn FnMut(&mut [f64]),
1176    opts: &ForwardErrorOptions,
1177) -> Result<ForwardErrorBound, VerifyError> {
1178    use ForwardErrorOutcome::{Certified, NotContracting, NotFinite};
1179    // E0.
1180    dimension(a.n_rows(), a.n_cols())?;
1181    let n = a.n_rows();
1182    dimension(n, r.len())?;
1183    if r.iter().any(|x| x.is_empty()) {
1184        return Ok(ForwardErrorBound::refused(NotFinite, n, 0.0, 0));
1185    }
1186    let bound =
1187        forward_error_rows(a, r, solve_transpose, opts.refine_rows).unwrap_or_else(|refusal| {
1188            let (outcome, alpha, solves) = refusal;
1189            ForwardErrorBound::refused(outcome, n, alpha, solves)
1190        });
1191    debug_assert!(
1192        bound.check_invariants().is_ok(),
1193        "{:?}: {bound:?}",
1194        bound.check_invariants()
1195    );
1196    debug_assert!(n > 0 || bound.outcome == Certified);
1197    debug_assert!(bound.outcome != NotContracting || bound.contraction >= 1.0);
1198    Ok(bound)
1199}
1200
1201/// Steps E1–E7 for a square `a` and a nonempty `[r]` of the right length;
1202/// `Err((outcome, α, solves))` when there is no certificate.
1203// Every upper bound goes through `upper`, so a NaN — none arises today:
1204// the operations of `Interval` on non-empty operands return none — would
1205// count as `+∞` and refuse; `!(α < 1)` refuses one too.
1206#[allow(clippy::neg_cmp_op_on_partial_ord)]
1207fn forward_error_rows(
1208    a: &CsrMatrix<f64>,
1209    r: &[Interval],
1210    solve_transpose: &mut dyn FnMut(&mut [f64]),
1211    refine_rows: bool,
1212) -> Result<ForwardErrorBound, (ForwardErrorOutcome, f64, usize)> {
1213    use ForwardErrorOutcome::{Certified, NotContracting, NotFinite};
1214    let n = a.n_rows();
1215    let csc = a.to_csc();
1216    // `y = h + ℓ`, the row of `R`; `d` the correction of step E2.
1217    let (mut h, mut l, mut d) = (vec![0.0; n], vec![0.0; n], vec![0.0; n]);
1218    let mut mark = vec![false; n];
1219    let (mut support, mut cols) = (Vec::new(), Vec::new());
1220    let (mut pp, mut qq) = (Vec::new(), Vec::new());
1221    let (mut rho, mut g) = (vec![0.0; n], vec![0.0; n]);
1222    let mut alpha = 0.0_f64;
1223    let mut solves = 0_usize;
1224    for p in 0..n {
1225        // E1.
1226        h.fill(0.0);
1227        l.fill(0.0);
1228        h[p] = 1.0;
1229        solve_transpose(&mut h);
1230        solves += 1;
1231        if !h.iter().all(|v| v.is_finite()) {
1232            return Err((NotFinite, alpha, solves));
1233        }
1234        // E2: only chooses `R`; nothing here enters the proof. `refined`:
1235        // the trailing components `ℓ` were set (otherwise all zero).
1236        let mut refined = false;
1237        if refine_rows {
1238            row_sets(a, p, (&h, &l), &mut mark, &mut support, &mut cols);
1239            d.fill(0.0);
1240            for &q in &cols {
1241                let (rows, vals) = csc.col(Col::from_usize(q));
1242                qq.clear();
1243                qq.extend(rows.iter().map(|&i| h[i as usize]));
1244                d[q] = (DoubleDouble::from_f64(kronecker(p, q)) - kernels::dot2(vals, &qq)).hi();
1245            }
1246            solve_transpose(&mut d);
1247            solves += 1;
1248            // (Q2 of X0.3i: also discard a correction whose sum overflows.)
1249            if d.iter()
1250                .zip(&h)
1251                .all(|(&di, &hi)| di.is_finite() && (hi + di).is_finite())
1252            {
1253                refined = true;
1254                for ((hi, li), &di) in h.iter_mut().zip(l.iter_mut()).zip(&d) {
1255                    let s = DoubleDouble::from_f64(*hi) + di;
1256                    (*hi, *li) = (s.hi(), s.lo());
1257                }
1258            }
1259        }
1260        // Proof of Theorem E, (o): `R` is real.
1261        debug_assert!(
1262            h.iter().chain(&l).all(|v| v.is_finite()),
1263            "(o): a non-finite component in row {p} of R"
1264        );
1265        // E3.
1266        row_sets(a, p, (&h, &l), &mut mark, &mut support, &mut cols);
1267        let mut sum = Interval::ZERO;
1268        for &q in &cols {
1269            let (rows, vals) = csc.col(Col::from_usize(q));
1270            pp.clear();
1271            qq.clear();
1272            pp.extend_from_slice(vals);
1273            qq.extend(rows.iter().map(|&i| h[i as usize]));
1274            if refined {
1275                pp.extend_from_slice(vals);
1276                qq.extend(rows.iter().map(|&i| l[i as usize]));
1277            }
1278            pp.push(-1.0);
1279            qq.push(kronecker(p, q));
1280            let (s, beta) = kernels::dot2_err(&pp, &qq);
1281            sum += enclosure(s, beta).mag();
1282        }
1283        rho[p] = upper(sum.sup());
1284        // E4.
1285        let mut acc = Interval::ZERO;
1286        for &i in &support {
1287            for y in [h[i], l[i]] {
1288                if y != 0.0 {
1289                    acc += r[i] * y;
1290                }
1291            }
1292        }
1293        g[p] = upper(acc.mag());
1294        // E5.
1295        alpha = alpha.max(rho[p]);
1296        if !(alpha < 1.0) {
1297            return Err((NotContracting, alpha, solves));
1298        }
1299    }
1300    // E6.
1301    let gamma = g.iter().fold(0.0_f64, |m, &v| m.max(v));
1302    if !gamma.is_finite() {
1303        return Err((NotFinite, alpha, solves));
1304    }
1305    let eps = upper((Interval::point(gamma) / (1.0 - Interval::point(alpha))).sup());
1306    if !eps.is_finite() {
1307        return Err((NotFinite, alpha, solves));
1308    }
1309    // E7.
1310    let componentwise = g
1311        .iter()
1312        .zip(&rho)
1313        .map(|(&gp, &rp)| upper((Interval::point(gp) + Interval::point(rp) * eps).sup()).min(eps))
1314        .collect();
1315    Ok(ForwardErrorBound {
1316        outcome: Certified,
1317        norm_inf: eps,
1318        componentwise,
1319        contraction: alpha,
1320        solves,
1321    })
1322}
1323
1324#[cfg(test)]
1325#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
1326#[allow(clippy::float_cmp)] // the tests compare exact values
1327mod tests {
1328    use super::*;
1329
1330    type Dd = DoubleDouble;
1331
1332    /// `[[2, 1], [1, 3]]`.
1333    fn small() -> CsrMatrix<f64> {
1334        CsrMatrix::from_raw_parts(2, vec![0, 2, 4], vec![0, 1, 0, 1], vec![2.0, 1.0, 1.0, 3.0])
1335            .expect("a valid matrix")
1336    }
1337
1338    #[test]
1339    fn exact_data_give_point_like_residuals() {
1340        let a = small();
1341        // x = (1, 2): A x = (4, 7).
1342        let r = residual(&a, &[1.0, 2.0], &[4.0, 6.0]).unwrap();
1343        // Only the underflow term of Dot2Err widens them.
1344        assert!(r[0].contains(0.0) && r[0].width() < 1e-300);
1345        assert!(r[1].contains(1.0) && r[1].width() < 1e-15);
1346        assert!(r[1].certainly_within(1.0 + 1e-15) && !r[1].certainly_within(0.5));
1347        let s = activity(&a, &[1.0, 2.0]).unwrap();
1348        assert!(s[0].contains(4.0) && s[1].contains(7.0));
1349        assert!(s[1].certainly_le(7.0 + 1e-12) && s[1].certainly_ge(7.0 - 1e-12));
1350        let n = norm_inf_bound(&r);
1351        assert!((1.0..1.0 + 1e-15).contains(&n));
1352        assert_eq!(
1353            residual_csc(&a.to_csc(), &[1.0, 2.0], &[4.0, 6.0]).unwrap(),
1354            r
1355        );
1356        let x = [Dd::from_f64(1.0), Dd::from_f64(2.0)];
1357        assert_eq!(residual_of_dd(&a, &x, &[4.0, 6.0]).unwrap(), r);
1358        assert_eq!(
1359            residual_dd(&a, &x, &[4.0, 6.0]).unwrap(),
1360            vec![Dd::ZERO, Dd::from_f64(-1.0)]
1361        );
1362    }
1363
1364    #[test]
1365    fn a_residual_below_the_f64_grid_is_seen() {
1366        // (1 + 2^-52)·(1 + 2^-52) − (1 + 2^-51) = 2^-104: zero in f64.
1367        let x = 1.0 + f64::EPSILON;
1368        let a = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![x]).unwrap();
1369        let r = residual(&a, &[x], &[1.0 + 2.0 * f64::EPSILON]).unwrap();
1370        let exact = f64::EPSILON * f64::EPSILON;
1371        assert!(r[0].contains(exact) && r[0].certainly_ge(exact * 0.5));
1372        // A double-double x: the trailing component is part of the value.
1373        let xd = [Dd::from_sum(1.0, exact)];
1374        let one = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![1.0]).unwrap();
1375        let r = residual_of_dd(&one, &xd, &[1.0]).unwrap();
1376        assert!(r[0].contains(exact) && r[0].certainly_ge(exact * 0.5));
1377    }
1378
1379    #[test]
1380    fn failed_hypotheses_claim_nothing() {
1381        let a = small();
1382        for bad in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
1383            let r = residual(&a, &[bad, 1.0], &[0.0, 0.0]).unwrap();
1384            assert_eq!(r, vec![Interval::ENTIRE; 2], "{bad}");
1385            assert_eq!(norm_inf_bound(&r), f64::INFINITY);
1386            let s = activity(&a, &[1.0, bad]).unwrap();
1387            assert_eq!(s, vec![Interval::ENTIRE; 2], "{bad}");
1388        }
1389        // Overflow in one row only: 2 · 10³⁰⁸ in the first, not the second.
1390        let r = residual(&a, &[1e308, 1.0], &[0.0, 0.0]).unwrap();
1391        assert_eq!(r[0], Interval::ENTIRE);
1392        assert!(r[1].contains(1e308) && r[1].width() < 1e293);
1393        let r = residual(&a, &[1.0, 1.0], &[f64::NAN, 0.0]).unwrap();
1394        assert_eq!(r[0], Interval::ENTIRE);
1395        assert!(r[1].contains(4.0));
1396        let r = residual_of_dd(&a, &[Dd::NAN, Dd::ONE], &[0.0, 0.0]).unwrap();
1397        assert_eq!(r, vec![Interval::ENTIRE; 2]);
1398        assert_eq!(norm_inf_bound(&[]), 0.0);
1399        assert_eq!(
1400            norm_inf_bound(&[Interval::ZERO, Interval::EMPTY]),
1401            f64::INFINITY
1402        );
1403        assert_eq!(enclosure(Dd::ONE, f64::NAN), Interval::ENTIRE);
1404    }
1405
1406    #[test]
1407    fn dimensions_are_checked_first() {
1408        let a = small();
1409        let err = |expected, got| VerifyError::Dimension { expected, got };
1410        assert_eq!(residual(&a, &[1.0], &[0.0, 0.0]), Err(err(2, 1)));
1411        assert_eq!(residual(&a, &[1.0, 1.0], &[0.0]), Err(err(2, 1)));
1412        assert_eq!(
1413            residual_csc(&a.to_csc(), &[1.0; 3], &[0.0; 2]),
1414            Err(err(2, 3))
1415        );
1416        assert_eq!(residual_of_dd(&a, &[Dd::ONE], &[0.0; 2]), Err(err(2, 1)));
1417        assert_eq!(residual_dd(&a, &[Dd::ONE; 2], &[0.0; 3]), Err(err(2, 3)));
1418        assert_eq!(activity(&a, &[]), Err(err(2, 0)));
1419        let mut x = [Dd::ONE; 2];
1420        let o = PolishOptions::default();
1421        assert_eq!(polish(&a, &[0.0], &mut x, &mut |_| {}, &o), Err(err(2, 1)));
1422        // 1 × 2: not square.
1423        let wide = CsrMatrix::from_raw_parts(2, vec![0, 2], vec![0, 1], vec![1.0, 1.0]).unwrap();
1424        assert_eq!(
1425            polish(&wide, &[0.0], &mut x, &mut |_| {}, &o),
1426            Err(err(1, 2))
1427        );
1428    }
1429
1430    #[test]
1431    fn errors_are_errors() {
1432        let e: Box<dyn core::error::Error> = Box::new(VerifyError::Dimension {
1433            expected: 3,
1434            got: 2,
1435        });
1436        assert_eq!(e.to_string(), "dimension mismatch: expected 3, got 2");
1437    }
1438
1439    /// Step P2 (c) is per row: a row of small terms is not declared
1440    /// converged because another row is large.
1441    #[test]
1442    fn convergence_is_tested_row_by_row() {
1443        // diag(1e20, 1), b = (1e20, 1): x = (1, 1). Start with the second
1444        // component off by 1e-10: its residual, 1e-10, is 5e-31 of the
1445        // global scale ‖A‖‖x‖ + ‖b‖ = 2e20 (below τ ≈ 8e-28) and 5e-11 of
1446        // its own row.
1447        let a = CsrMatrix::from_raw_parts(2, vec![0, 1, 2], vec![0, 1], vec![1e20, 1.0]).unwrap();
1448        let b = [1e20, 1.0];
1449        let mut x = [Dd::ONE, Dd::from_f64(1.0 + 1e-10)];
1450        let mut solve = |s: &mut [f64]| s[0] /= 1e20;
1451        let rep = polish(&a, &b, &mut x, &mut solve, &PolishOptions::default()).unwrap();
1452        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 1));
1453        assert_eq!(x, [Dd::ONE, Dd::ONE]);
1454        // The threshold is exactly relative to the row: 2 x = 2 with x one
1455        // ulp off has |r| = 2ε against Σ|a x| + |b| ≈ 4.
1456        let two = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![2.0]).unwrap();
1457        let start = [Dd::from_f64(1.0 + f64::EPSILON)];
1458        let loose = PolishOptions {
1459            tol: 0.6 * f64::EPSILON,
1460            ..PolishOptions::default()
1461        };
1462        let tight = PolishOptions {
1463            tol: 0.4 * f64::EPSILON,
1464            ..PolishOptions::default()
1465        };
1466        let mut x = start;
1467        let rep = polish(&two, &[2.0], &mut x, &mut |s| s[0] /= 2.0, &loose).unwrap();
1468        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
1469        let mut x = start;
1470        let rep = polish(&two, &[2.0], &mut x, &mut |s| s[0] /= 2.0, &tight).unwrap();
1471        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 1));
1472        assert_eq!(x, [Dd::ONE]);
1473    }
1474
1475    /// Progress is measured in the norm (step P2 (d)) while convergence is
1476    /// tested row by row.
1477    #[test]
1478    fn progress_is_measured_in_the_norm() {
1479        let a = CsrMatrix::from_raw_parts(2, vec![0, 1, 2], vec![0, 1], vec![1e20, 1.0]).unwrap();
1480        let b = [1e20, 1.0];
1481        // Row 1 keeps a residual of 1e20 ε that the "solve" never touches;
1482        // row 2 is solved exactly by the first correction. The norm ‖r‖∞,
1483        // set by row 1, does not move: stagnated, the correction kept.
1484        let start = [Dd::from_f64(1.0 + f64::EPSILON), Dd::from_f64(1.5)];
1485        let mut x = start;
1486        let mut solve = |s: &mut [f64]| s[0] = 0.0;
1487        let rep = polish(&a, &b, &mut x, &mut solve, &PolishOptions::default()).unwrap();
1488        assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 1));
1489        assert_eq!(x, [start[0], Dd::ONE]);
1490        assert_eq!(rep.residual_after, rep.residual_before);
1491    }
1492
1493    /// Rows whose scale `S_i` is zero need no rule of their own in step
1494    /// P2 (c): an empty row with `b_i = 0` and a row whose only term
1495    /// underflows completely pass with a zero residual, and only then.
1496    #[test]
1497    fn rows_of_zero_scale() {
1498        // Row 0 is empty, row 1 is 1e-200 x_1 = 0 with x_1 = 1e-200, row 2
1499        // is 2 x_2 = 2.
1500        let a =
1501            CsrMatrix::from_raw_parts(3, vec![0, 0, 1, 2], vec![1, 2], vec![1e-200, 2.0]).unwrap();
1502        let b = [0.0, 0.0, 2.0];
1503        let x = [Dd::ZERO, Dd::from_f64(1e-200), Dd::ONE];
1504        let r = residual_dd(&a, &x, &b).unwrap();
1505        assert_eq!(r, vec![Dd::ZERO; 3]);
1506        assert!(rows_converged(&a, &x, &b, &r, 2f64.powi(-90)));
1507        let mut y = x;
1508        let rep = polish(
1509            &a,
1510            &b,
1511            &mut y,
1512            &mut |_| panic!("no solve"),
1513            &PolishOptions::default(),
1514        )
1515        .unwrap();
1516        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
1517        // A nonzero residual against a zero scale never passes, whatever
1518        // τ; nor does a NaN.
1519        let fake = [Dd::from_f64(1e-300), Dd::ZERO, Dd::ZERO];
1520        assert!(!rows_converged(&a, &x, &b, &fake, 1e300));
1521        let fake = [Dd::ZERO, Dd::ZERO, Dd::NAN];
1522        assert!(!rows_converged(&a, &x, &b, &fake, 1e300));
1523        // A scale that overflows proves nothing: the row does not pass,
1524        // although each product and the residual are finite (1.5e308 −
1525        // 1.5e308, whose scale 3e308 is not an `f64`).
1526        let big =
1527            CsrMatrix::from_raw_parts(2, vec![0, 2], vec![0, 1], vec![1e150, -1e150]).unwrap();
1528        let xb = [Dd::from_f64(1.5e158), Dd::from_f64(1.5e158)];
1529        let rb = residual_dd(&big, &xb, &[0.0]).unwrap();
1530        assert_eq!(rb, vec![Dd::ZERO]);
1531        assert!(!rows_converged(&big, &xb, &[0.0], &rb, 2f64.powi(-90)));
1532        let rb = [Dd::from_f64(1e290)];
1533        assert!(!rows_converged(&big, &xb, &[0.0], &rb, 2f64.powi(-90)));
1534    }
1535
1536    #[test]
1537    fn defaults_are_those_of_the_contract() {
1538        let o = PolishOptions::default();
1539        assert_eq!(
1540            (o.tol, o.min_progress, o.max_iter),
1541            (2f64.powi(-90), 0.5, 10)
1542        );
1543    }
1544
1545    /// The exact inverse of [`small`], times `damping`.
1546    fn solve_small(damping: f64) -> impl FnMut(&mut [f64]) {
1547        move |s: &mut [f64]| {
1548            let (p, q) = (s[0], s[1]);
1549            s[0] = damping * (3.0 * p - q) / 5.0;
1550            s[1] = damping * (2.0 * q - p) / 5.0;
1551        }
1552    }
1553
1554    #[test]
1555    fn polish_converges_and_reports() {
1556        let a = small();
1557        let b = [1.0, 1.0]; // x = (2/5, 1/5): not representable
1558        let mut x = [Dd::from_f64(0.4), Dd::from_f64(0.2)];
1559        let rep = polish(
1560            &a,
1561            &b,
1562            &mut x,
1563            &mut solve_small(1.0),
1564            &PolishOptions::default(),
1565        )
1566        .unwrap();
1567        assert_eq!(rep.stop, PolishStop::Converged);
1568        assert!(rep.iterations >= 1 && rep.iterations <= 3, "{rep:?}");
1569        assert!(
1570            rep.residual_before > 1e-17 && rep.residual_after < 1e-30,
1571            "{rep:?}"
1572        );
1573        assert!(x[0].lo() != 0.0 && x[1].lo() != 0.0);
1574        let cert = norm_inf_bound(&residual_of_dd(&a, &x, &b).unwrap());
1575        assert!(cert < 1e-30, "{cert:e}");
1576        // An exact solution converges without a correction.
1577        let mut x = [Dd::ONE, Dd::from_f64(2.0)];
1578        let rep = polish(
1579            &a,
1580            &[4.0, 7.0],
1581            &mut x,
1582            &mut |_| panic!("no solve"),
1583            &PolishOptions::default(),
1584        )
1585        .unwrap();
1586        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
1587        assert_eq!((rep.residual_before, rep.residual_after), (0.0, 0.0));
1588        // The empty system.
1589        let empty = CsrMatrix::from_raw_parts(0, vec![0], vec![], vec![]).unwrap();
1590        let rep = polish(&empty, &[], &mut [], &mut |_| {}, &PolishOptions::default()).unwrap();
1591        assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
1592    }
1593
1594    #[test]
1595    fn polish_stops_for_each_reason() {
1596        let a = small();
1597        let b = [1.0, 1.0];
1598        let start = [Dd::from_f64(0.5), Dd::from_f64(0.5)];
1599        let o = PolishOptions::default();
1600
1601        // A "solve" that is not one (the identity): the residual grows,
1602        // the correction is undone (P2 (b)).
1603        let mut x = start;
1604        let rep = polish(&a, &b, &mut x, &mut |_| {}, &o).unwrap();
1605        assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 0));
1606        assert_eq!(x, start);
1607        assert_eq!(rep.residual_after, rep.residual_before);
1608        assert_eq!(rep.residual_before, 1.0);
1609
1610        // A solve that is 40 % right: the residual shrinks by 0.6 > ρ per
1611        // pass; the first correction is kept (P2 (d)).
1612        let mut x = start;
1613        let rep = polish(&a, &b, &mut x, &mut solve_small(0.4), &o).unwrap();
1614        assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 1));
1615        assert!(rep.residual_after < rep.residual_before && x != start);
1616
1617        // The same with ρ = 0.9: the limit of 10 corrections (P2 (e)).
1618        let slow = PolishOptions {
1619            min_progress: 0.9,
1620            ..o
1621        };
1622        let mut x = start;
1623        let rep = polish(&a, &b, &mut x, &mut solve_small(0.4), &slow).unwrap();
1624        assert_eq!((rep.stop, rep.iterations), (PolishStop::IterationLimit, 10));
1625        assert!(rep.residual_after < 0.01 * rep.residual_before, "{rep:?}");
1626        // No correction at all with a limit of zero.
1627        let none = PolishOptions { max_iter: 0, ..o };
1628        let mut x = start;
1629        let rep = polish(&a, &b, &mut x, &mut |_| panic!("no solve"), &none).unwrap();
1630        assert_eq!((rep.stop, rep.iterations), (PolishStop::IterationLimit, 0));
1631        assert_eq!(x, start);
1632
1633        // A correction that is not finite: x untouched (P2).
1634        let mut x = start;
1635        let rep = polish(&a, &b, &mut x, &mut |s| s[0] = f64::NAN, &o).unwrap();
1636        assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
1637        assert_eq!(x, start);
1638        // A residual that is not finite from the start.
1639        let mut x = [Dd::NAN, Dd::ONE];
1640        let rep = polish(&a, &b, &mut x, &mut |_| panic!("no solve"), &o).unwrap();
1641        assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
1642        assert!(rep.residual_before.is_nan() && rep.residual_after.is_nan());
1643        // A correction that overflows the next residual is undone (P2 (a)).
1644        let mut x = start;
1645        let rep = polish(&a, &b, &mut x, &mut |s| s[0] = 1e308, &o).unwrap();
1646        assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
1647        assert_eq!(x, start);
1648        assert_eq!(rep.residual_after, rep.residual_before);
1649    }
1650}