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}