Skip to main content

Module verify

Module verify 

Source
Expand description

§Chapter 11.10 — Verified residuals and polishing

§Purpose

Two things a solver wants to know about an approximate solution x of A x = b, for the f64 data as stored (C1 of Chapter 11):

  1. how large the residual really is — Algorithm V returns, row by row, an interval that contains a_iᵀx − b_i, a theorem and not an estimate (invariant V1);
  2. a better x — Algorithm P refines x in double-double around a solve the caller already has (its f64 LU), after which Algorithm V certifies the residual that was reached;
  3. how far x is from the exact solution — Algorithm E proves, from the enclosure of Algorithm V and n transposed solves (2n with refinement), that a square A is nonsingular and bounds ‖x − A⁻¹b‖∞ and every |x_p − (A⁻¹b)_p|, again a theorem (Theorem E).

Algorithm E bounds the error of one approximate solution of one square system with point data. Verified solution sets of interval systems (Rump’s verifylss on interval data), interval LU and Krawczyk iteration stay out of v0.1 (Chapter 11, “Out of scope”).

§Notation

A ∈ F^{m×n} in compressed rows (xingo_sparse::CsrMatrix<f64>), a_i its row i with k_i stored entries, x ∈ F^n or x ∈ DD^n (each component the exact sum h_j + ℓ_j), b ∈ F^m. u = 2⁻⁵³. Dot2Err is kernels::dot2_err (Chapter 11.5, Algorithm C): for f64 vectors p, q it returns a double-double r and an f64 β with |pᵀq − r| ≤ β for every input, β = +∞ when a hypothesis of the bound fails (invariant K2). ▽, △ are the directed roundings of Chapter 11.9. ‖·‖∞ is the largest absolute value of a vector and the largest absolute row sum of a matrix.

§Algorithm V (verified residual)

Input: A, x, b. Output: intervals R_i ∋ a_iᵀx − b_i.

V1. [Row.] For each row i, gather two f64 vectors p, q whose dot product is the residual, exactly, as real numbers: * x ∈ F^n: the k_i pairs (a_ij, x_j) and the pair (−1, b_i); * x ∈ DD^n: the pairs (a_ij, h_j), then the pairs (a_ij, ℓ_j), then (−1, b_i) — 2 k_i + 1 in all; * activities: the k_i pairs (a_ij, x_j) alone. V2. [Accumulate.] (r, β) ← Dot2Err(p, q). V3. [Enclose.] If β or r is not finite, R_i ← [−∞, +∞]. Otherwise, with r = h + ℓ, R_i ← [▽(h + ▽(ℓ − β)), △(h + △(ℓ + β))]: the radius is applied to the trailing component, where it is of the right size, before the leading one is added.

For x ∈ DD^n (residual_of_dd) four more steps narrow R_i — the distillation of the residual (issue #5 of the mirror; “Why the polished residual needs more” below). N = 2 k_i + 1 is the number of pairs of V1, (p_j, q_j) the pairs.

V4. [Split.] (π_j, ε_j) ← 2Prod(p_j, q_j) for j = 1, …, N; w ← (π_1, ε_1, π_2, ε_2, …, π_N, ε_N), 2N numbers. If one of them is not finite, keep the R_i of V3 and stop. V5. [Distil, twice.] Two passes of VecSum: σ ← w_1; for j = 2, …, L (L the current length of w): (σ, w_{j−1}) ← 2Sum(σ, w_j); then w ← (w_1, …, w_{L−1}). The two final σ are σ_1, σ_2; w ends with M = 2N − 2 numbers. If a σ or a w_j is not finite, keep the R_i of V3 and stop. V6. [Tail.] t ← RN(… RN(RN(w_1 + w_2) + w_3) … + w_M) and a ← the same sum of the |w_j| (t = a = 0 if M = 0). With m = max(M, 1) − 1: if 2 m u ≥ 1, or t or a is not finite, keep the R_i of V3 and stop. Otherwise β′ ← sup([δ]·[a] + [φ]), [δ] ← [m u] / (1 − 2[m u]), in Interval (m u is an f64 exactly for m < 2⁵²), with φ = (3η/u)(1 + 8u), the floor of β in step C5 of Chapter 11.5 (an f64 exactly). V7. [Combine.] (s, τ) ← 2Sum(σ_1, σ_2); if s or τ is not finite, keep the R_i of V3 and stop. R′_i ← ((t ± β′) + τ) + s in Interval (t ± β′ is Interval::mid_rad), and R_i ← R_i ∩ R′_i.

Proof of (V1). pᵀq is the residual exactly: for a double-double x, Σ_j a_ij (h_j + ℓ_j) − b_i = Σ_j a_ij h_j + Σ_j a_ij ℓ_j + (−1) b_i, an identity of real numbers, and the value of x_j is h_j + ℓ_j. So the double-double case needs no bound of its own — it is Dot2Err on a vector twice as long (this replaces the “second-order terms” that the contract’s sketch of step V2 announced). By (K2), |pᵀq − r| ≤ β, i.e. h + (ℓ − β) ≤ pᵀq ≤ h + (ℓ + β), and each of the two directed sums of V3 on either side moves outward. When β = +∞ nothing is claimed (C3). ∎ (Until review X0.3i, (K2) failed when an intermediate step of the last 2Sum of Dot2Err overflowed at ±Ω, and this proof with it; the enclosures found there still contained the residual, by the margin of V3. Now β = +∞ in that corner and the row is ENTIRE: Chapter 11.5, the proof of C5, “Overflow”.) (The contract’s sketch had enclose(r) + [−β, β], which is also correct and one to two ulps wider: it rounds r to its neighbours before the radius is added.)

Proof of (V1) for steps V4–V7. Write s* = pᵀq, the exact residual. (a) Split. By (T2) of Chapter 11.1, with π_j finite, p_j q_j = π_j + ε_j − μ_j with μ_j = 0 when the product is in the exact range and |μ_j| ≤ η/2 otherwise; so s* = Σ w − μ, |μ| ≤ N η/2. (b) Distil. By (T1), a 2Sum whose outputs are finite is exact (its only failure, at |a| = Ω, leaves the error term not finite, and V5 tests every one), so each pass keeps the exact sum: Σ w⁽⁰⁾ = σ_1 + Σ w⁽¹⁾ = σ_1 + σ_2 + Σ w⁽²⁾. (c) Tail. t is a floating-point sum of the M numbers of w⁽²⁾. An addition is exact when its result is subnormal, so every addition errs by at most u times its result, underflow or not; none overflowed, since an infinite partial sum cannot come back finite and t, a are finite. Hence |Σ w⁽²⁾ − t| ≤ γ_m Σ|w_j| (the order-independent bound of Higham §4.2, m = M − 1 additions), and since each of the m additions of a is RN(c) = c/(1 + θ), |θ| ≤ u, Σ|w_j| ≤ (1 + u)^m a. With m u < 1/2, (1 + u)^m ≤ e^{mu} ≤ 1/(1 − mu) and (1 − mu)² ≥ 1 − 2mu, so γ_m (1 + u)^m ≤ mu/(1 − 2mu) = δ, and |Σ w⁽²⁾ − t| ≤ δ a. [δ] contains δ (I1; m u is exact), and φ > 3 · 2⁵³ η ≥ N η/2 (N ≤ m/2 + 2 < 2⁵¹ + 2), so δ a + N η/2 ≤ β′. (d) Combine. σ_1 + σ_2 = s + τ exactly (T1, both finite). So s* = s + τ + t + (Σ w⁽²⁾ − t) − μ lies in ((t ± β′) + τ) + s (I1), i.e. in R′_i; and in the R_i of V3 by the proof above; so in their intersection. ∎ (When a step keeps the R_i of V3, nothing new is claimed.) The intersection makes V4–V7 never widen the enclosure of V3 (invariant V3), and leaves it bit for bit when R′_i ⊇ R_i. That is the case when every operation of V2 and V4–V7 is exact and the residual is an f64: both are then that f64 widened by φ — the floor is shared so that an exact row keeps its V3 bits.

Width. For a finite result of V3, width(R_i) ≤ 2 ulp(r) + 2β (1 + 2u) — typically one ulp, two when r is an f64 — and β is of order k² u² Σ_j |a_ij x_j| (Chapter 11.5, step C5): the enclosure of a residual of size ρ computed from terms of size S has a relative width of about u + k² u² S/ρ. An f64 solution leaves ρ ≈ κ u S at best, so its residual is enclosed to about 16 digits by V3 alone. A polished one has ρ ≈ k u² S, of the order of β itself: V3 then only proves “|a_iᵀx − b_i| ≤ c k² u² S”.

Why the polished residual needs more, and what V4–V7 give. VecSum leaves error terms bounded by γ_{L−1} times the sum of the magnitudes it was given (Ogita, Rump & Oishi, Lemma 4.2 — cited from memory; the proof above does not use it), so after two passes Σ|w⁽²⁾| ≲ 4N²u² S and β′ ≲ 8 N³ u³ S, against β ≈ N² u² S for Dot2Err: one more factor N u — the accuracy of a sum in three times the working precision (SumK with K = 3, ibid. Algorithm 4.8), with an a posteriori bound in place of theirs. The other terms of the width are the outward roundings of V7, a few ulps of s* when |s*| ≳ β′. With ρ ≈ k u² S the relative width falls from ≈ k to ≈ u + k² u. Measured on the polished optimal bases of the 93 Netlib LPs (task X0.5, rows of up to 6 185 entries): the largest half-width over ‖r‖∞ of a basis went from 126 (median) and 9.4 · 10⁴ (largest) with V3 alone to at most 7.2 · 10⁻¹¹ with V4–V7. A third pass of V5 changed none of the bounds of Algorithm E below at three digits, so the chapter stops at two.

Cost. About 25 flops per stored entry for x ∈ F^n; for x ∈ DD^n about 50 for V1–V3 and 65 more for V4–V7 (one 2Prod, four 2Sum and the tail per pair, two pairs per entry), and two gather buffers of the length of the longest row and one of four times that. Measured (task X0.5, M2 Pro under load, eight polished Netlib systems of 2 392 to 18 301 rows): residual_of_dd takes 3.0 to 4.5 times as long as V1–V3 alone (whose Dot2Err is vectorized; V4–V7 are scalar), 0.4 to 3.4 ms — at most 5 % of the time of Algorithm E on the same bases, except where the basis is far smaller than the system (fit2d: m = 25, Algorithm E under 1 ms). residual_csc first converts to compressed rows (O(nnz) time and memory).

§Algorithm P (polishing: iterative refinement with extended residuals)

Input: a square A, b, an approximate solution x ∈ DD^n (an f64 solution has zero trailing components), a solve s ↦ d ≈ A⁻¹ s in f64 (a closure: the caller’s LU), the parameters τ, ρ and the iteration limit of PolishOptions. Output: x, polished in place, and a PolishReport.

P1. [Residual.] r ← b − A x in double-double (residual_dd); ν ← ‖r‖∞. On the first pass, ν₀ ← ν. P2. [Stop?] In this order: (a) if ν is not finite: restore the previous x (if any) and stop, not finite; (b) if ν > ν_prev (after a correction): the correction made things worse — restore the previous x and stop, stagnated; (c) if |r_i| ≤ τ S_i in every row i, with S_i = Σ_j |a_ij x_j| + |b_i| the size of the terms of that row (the componentwise test; “How step P2 (c) rounds” below): stop, converged; (d) if ν > ρ ν_prev (after a correction): stop, stagnated (the new x is kept: it is not worse); (e) if the iteration limit is reached: stop, iteration limit. P3. [Correct.] s ← RN(r) (the leading components); d ← solve(s). If some d_i is not finite, stop, not finite (x is the current one). Otherwise save x, set x ← x + d in double-double, ν_prev ← ν, and return to P1.

How step P2 (c) rounds. The test is per row because a global scale ‖A‖∞‖x‖∞ + ‖b‖∞ — the contract’s — is set by the largest row of a badly scaled model and declares the small rows converged while they still carry a residual far above double-double level (measured on the Netlib bases in task L2.3). The right-hand side must not be overestimated, or convergence would be declared unduly. It is computed in f64 as t_i = RN(RN(τ Ŝ_i) · d_i), with Ŝ_i the plain left-to-right sum of |b_i| and the k products RN(|a_ij| |h_j|) (h_j the leading component of x_j) and the deflation d_i = RN(1 − (2k + 10) u). Barring underflow, Ŝ_i ≤ S_i (1 + u)^{k+2} for the exact S_i = Σ_j |a_ij x_j| + |b_i| (one rounding per product, |h_j| ≤ (1 + u)|x_j|, k additions of nonnegative terms), two more roundings give t_i ≤ τ S_i (1 + u)^{k+4} d_i, and the test compares the leading component |RN(r_i)| ≥ |r_i|/(1 + u). Since (1 + u)^{k+6} ≤ 1/(1 − (k + 6)u) ≤ 1/(1 − (2k + 10)u), |RN(r_i)| ≤ t_i implies |r_i| ≤ τ S_i for the double-double r_i of step P1 — the rounding of the test is always against convergence. (A product that underflows adds at most η/2 to Ŝ_i: rows whose terms are all below 2⁻¹⁰²² are outside this statement. A row of 2⁵¹ entries or more never passes, and neither does a row whose t_i overflows: an infinite bound proves nothing about τ S_i.) The r_i themselves are computed, not enclosed: P decides when to stop, Algorithm V what is proved.

A row with Ŝ_i = 0 — an empty row with b_i = 0, or terms that all underflow — needs no rule of its own: the test reads |RN(r_i)| ≤ 0, which holds exactly when the residual of that row is zero (and for finite data it is). No quotient is formed.

Convergence by rows, progress by the norm: a measurement. Steps (b) and (d) compare the norm ν = ‖r‖∞ of successive passes, not a row-scaled quantity. The other choice — progress measured as ω = max_i |r_i| / S_i, the scale of test (c) — was implemented, measured on the optimal bases of the 93 Netlib LPs and rejected (task L2.3, 2026-11-16; same τ, ρ and iteration limit throughout):

convergence / progressconvergedstagnatedlargest certified ‖r‖∞ after P
global / global (the contract)9302.879e-20
by rows / global (this version)8496.778e-22
by rows / ω83102.879e-20

With progress in ω, seven bases ended with a certified residual larger than with progress in the norm (greenbea 6.778e-22 → 2.879e-20, maros 6.975e-24 → 1.088e-22, dfl001 7.740e-28 → 1.445e-27, and cycle, stocfor2, scsd1, wood1p by 2 % or less), one with a smaller one (scsd8, by 1 %), and none ended above what the contract’s criterion gives.

A limitation of the row scale, measured. The cause was read off an instrumented run (eleven bases): when the exact solution has S_i = 0 in some row — a nonbasic variable at a zero bound, in its row x_v = 0; a constraint all of whose terms vanish — every iterate that is not exactly right there has |r_i| = S_i up to rounding, however small r_i is. So ω was exactly 1 before the first correction on all eleven, and still between 0.96 and 1 after it on eight of the ten that stagnated (on rows with |r_i| = S_i between 1e-34 and 1e-29): it did not halve, and P stopped after one pass where the norm criterion goes on for one or two more. The same rows are, presumably (this version was not instrumented), why test (c) leaves nine bases stagnated here: they pass only once their residual is exactly zero. That outcome is harmless — the point reached is kept and Algorithm V certifies it — and all nine have a certified residual no larger than under the contract’s criterion, except scsd8 (1.899e-29 → 1.919e-29).

An open lever, not measured. The literature on componentwise backward error replaces the denominator of such rows by a norm-based one — here it would be max(S_i, θ ‖a_i‖₁ ‖x‖∞) for a threshold θ (Arioli, Demmel & Duff, 1989: cited from memory, not reread). It was not implemented and not measured; it needs a threshold, to be chosen by a campaign like the one above.

What P guarantees. (P-mono) ν at exit is at most ν₀: steps (a) and (b) undo the only corrections that could increase it. Nothing else: P is numerical, not rigorous — its residuals are double-double values without a bound, its norms plain f64 — and the certificate of its result is Algorithm V. Higham (2002, ch. 12): with residuals in twice the working precision and a solve of relative accuracy κ(A) u < 1, each pass contracts the error by about κ(A) u, until the residual reaches the accuracy of its own evaluation, ≈ k u² (|A||x| + |b|); because x is stored in double-double here, the forward error keeps falling below u (to about κ(A) k u²), which a refinement that stores x in f64 cannot do.

§Algorithm E (a rigorous bound of the error, by an implicit approximate inverse)

Input: a square A ∈ F^{n×n} (compressed rows; one compressed-column copy is made), the enclosure [r] of the residual A x̃ − b of an approximate solution x̃ — n intervals, from residual (x̃ ∈ F^n) or residual_of_dd (x̃ ∈ DD^n) — a transposed solve c ↦ ≈ A⁻ᵀc in f64 (a closure: the BTRAN of the caller’s LU) and the switch refine_rows of ForwardErrorOptions (default on). Output (ForwardErrorBound): ε, the ε_p, α, the number of solves and the outcome.

Notation. e_p is the p-th unit vector and δ_pq the Kronecker delta; a_iq are the stored entries and a_{:q} the column q. A vector y of row p has components y_i = h_i + ℓ_i (two f64, the exact sum; ℓ = 0 without refinement). R is the matrix whose row p is the y that step E3 actually used, taken as exact real numbers: R is not “the inverse”, it is whatever came out, and the theorem holds for every R. C = I − RA (exact, real), x* = A⁻¹b, e = x̃ − x*. mag(X) = max{|x| : x ∈ X}.

E0. [Dimensions; trivial cases.] If A is not square or [r] does not have n entries: VerifyError::Dimension, before any arithmetic. If n = 0: certified, ε = 0, α = 0, no solve. If some [r_i] is empty: not certified (not finite), no solve. E1. [Row of R.] For p = 1, …, n: h ← e_p, ℓ ← 0; solve_transpose(h). If some h_i is not finite: not certified (not finite), stop. E2. [Refinement, optional.] If refine_rows: with Q_p of step E3 for this y, d_q ← RN(δ_pq − Dot2(a_{:q}, h)) for q ∈ Q_p and d_q ← 0 elsewhere (Dot2 of Chapter 11.5, not rigorous: it only chooses R); solve_transpose(d); if every d_i and every fl(h_i + d_i) is finite, (h_i, ℓ_i) ← h_i ⊕ d_i (the addition dd + f64 of Chapter 11.2, A1: the exact sum h_i + d_i unless |h_i| = Ω, where step E may return (fl(h_i + d_i), 0) — either way a pair of finite f64); otherwise y stays the one of E1. Nothing of this step enters the proof: R is the pairs that came out, exact sums or not. E3. [Row of C.] S_p = {i : h_i ≠ 0 or ℓ_i ≠ 0}, Q_p = {q : a_iq is stored for some i ∈ S_p} ∪ {p}. For each q ∈ Q_p, gather the pairs (a_iq, h_i) for the stored a_iq, then — if step E2 set ℓ — the pairs (a_iq, ℓ_i), and (−1, δ_pq); (s, β) ← Dot2Err; M_q ← mag(V3(s, β)). ρ_p ← sup(Σ_{q∈Q_p} M_q), the sum in Interval. E4. [Row of R[r].] G ← Σ_{i∈S_p} ([r_i]·h_i + [r_i]·ℓ_i) in Interval (a term with a zero factor is omitted); g_p ← mag(G). E5. [Early stop.] α ← max(α, ρ_p) (exact). If not α < 1: not certified (not contracting), stop; the α reported is that of the rows examined. E6. [Norm.] After the n rows: γ ← max_p g_p; if γ = +∞: not finite. ε ← sup([γ, γ] / (1 − [α, α])) in Interval; if ε = +∞: not finite. E7. [Components.] ε_p ← min(ε, sup([g_p, g_p] + [ρ_p, ρ_p]·ε)), in Interval.

Theorem E. If Algorithm E ends certified, A is nonsingular and, for every b ∈ ℝⁿ and x̃ ∈ ℝⁿ with A x̃ − b ∈ [r] componentwise — in use, the b and x̃ whose residual residual enclosed — x* = A⁻¹b satisfies ‖x̃ − x*‖∞ ≤ ε and |x̃_p − x*_p| ≤ ε_p for p = 1, …, n.

Proof. (o) R is a real matrix: every h_i and ℓ_i used is a finite f64 — E1 refuses a non-finite h, E2 keeps a correction only when every d_i and fl(h_i + d_i) is finite, and the addition A1 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 (h_i + ℓ_i) − δ_pq = Σ_i a_iq h_i + Σ_i a_iq ℓ_i + (−1) δ_pq (when E2 did not set ℓ, ℓ = 0 and the second sum is omitted) is exactly the dot product of the pairs of E3, and it equals −c_pq (c_pq = δ_pq − Σ_i y_i a_iq). By (K2) of Chapter 11.5, |−c_pq − s| ≤ β, with β = +∞ when a hypothesis of Dot2Err fails (a length with 2(k + 3)u ≥ 1, an overflow — of an intermediate step at ±Ω too, since X0.3i — a NaN) — then V3 is ENTIRE, M_q = ρ_p = +∞ and E5 refuses. By the proof of (V1) the interval V3 contains −c_pq, hence |c_pq| ≤ M_q. (ii) The columns outside Q_p have c_pq = 0 exactly: for q ∉ Q_p, q ≠ p, and every product a_iq y_i has a zero factor (either a_iq is not stored or i ∉ S_p, i.e. y_i = h_i + ℓ_i = 0). (iii) ρ_p ≥ Σ_q |c_pq|: a sum of nonnegative reals each dominated by an f64, computed in Interval (by (I1) its sup dominates the exact sum). Hence ‖C‖∞ = max_p Σ_q |c_pq| ≤ α < 1. (iv) Nonsingularity. RA = I − C with ‖C‖∞ < 1 is invertible (Neumann series), so A and R are invertible; x* exists and is unique. (v) g_p ≥ |(R r)_p| for every r ∈ [r]: (R r)_p = Σ_i (h_i + ℓ_i) r_i = Σ_i h_i r_i + Σ_i ℓ_i r_i; each term lies in [r_i]·h_i or [r_i]·ℓ_i (I1, with a point operand), the omitted terms (i ∉ S_p, or a zero factor) are zero, and the sum lies in the interval sum (I1). (vi) The bound. A e = A x̃ − b = r ∈ [r]; multiplying by R, (I − C) e = R r, i.e. e = R r + C e. So ‖e‖∞ ≤ ‖R r‖∞ + α ‖e‖∞, and since α < 1, ‖e‖∞ ≤ ‖R r‖∞/(1 − α) ≤ γ/(1 − α) ≤ ε — the quotient in Interval (I1, I3), with ▽(1 − α) > 0 because α < 1 is an f64. Componentwise, |e_p| ≤ |(R r)_p| + Σ_q |c_pq| |e_q| ≤ g_p + ρ_p ‖e‖∞ ≤ g_p + ρ_p ε, whose sup in Interval is an upper bound; and |e_p| ≤ ‖e‖∞ ≤ ε, so the minimum of the two bounds is one. ∎

Nothing in the proof depends on how y was obtained: a wrong, noisy or adversarial solve_transpose can only make α ≥ 1 (no certificate) or the bound loose, never false (invariant E1). For an exactly singular A there is no R with ‖I − RA‖∞ < 1 (it would make A invertible), so Algorithm E cannot certify it (invariant E2).

Where each rounding is. This is where textbook versions of the bound fail:

quantitycomputed asenclosed by
Rf64 (E1) or double-double (E2), no boundnothing needed: R is the numbers that came out
c_pqDot2Err on the exact pairs of E3(K2) and V3: |c_pq| ≤ M_q, underflow included in β
c_pq, q ∉ Q_pnot computedexactly zero (proof, ii)
ρ_p = Σ M_qInterval(I1), outward, exact under underflow (I3)
α = max ρ_pf64::maxexact
r = A x̃ − bresidual, residual_of_dd(V1)
(R r)_pInterval, interval × point, h and ℓ apart(I1)
γ/(1 − α), g_p + ρ_p εInterval(I1), (I3)

The errors this avoids: computing I − RA in floating point and taking the norm of the result (the rounding of RA is of the order of C itself); using ‖R‖ ‖r‖ with r recomputed in f64 (noise of the size of the residual itself); forgetting the underflow of the products (here it is in β); and accumulating the products of a double-double R in f64, whose error ≈ n u Σ|R||A| undoes the refinement — hence h and ℓ enter Dot2Err as separate pairs, the device of (V1) for a double-double x.

How tight, and why. For an f64 solution the error is R r up to C e, and C is small: in the measurements of the contract (task X0.3, decision log D-0125) ε/‖e‖∞ was between 1.00 and 1.04 on every certified case with α ≤ 0.04, and 1.00 on all 93 optimal bases of Netlib. For a polished solution the same holds since steps V4–V7 of Algorithm V (task X0.5): before them its exact residual was of the order of the width of its Dot2Err enclosure (“Width” above), g_p reflected |R| rad([r]), and the overestimation ε̂/‖e‖∞ went from 1.4 to 7.7 · 10⁴ (median about 230 over the 88 bases with a nonzero error). Measured term by term on those bases, nothing else contributed: α ≤ 1.2 · 10⁻⁷, so 1/(1 − α) and ρ_p ε are invisible at three digits, and with [r] replaced by a tight enclosure of the exact residual (computed in rationals) the ratio was already 1.000 on every basis — |R| |r| does not overestimate |R r| there. With V4–V7 the ratio is 1.000 at three digits on all 88 too (the true error bracketed rigorously, by Algorithm E itself on A e = A x̂ − b with the exact residual), and at most 1 + 5 · 10⁻⁶ on the dense test matrices of κ ≤ 10¹⁴ (before: up to 572). One solve per row leaves α of the order of κ(A) u; the refinement E2 lowers it by orders of magnitude (7.5 · 10⁻³ → 3.1 · 10⁻⁶ at κ = 10¹⁴, order 20): measured, it certifies dense matrices up to κ ≈ 10¹⁶, where one solve per row stops near 10¹⁴.

A basis of a linear program. The right-hand side b = −K_N β_N of a basis is not made of f64 values. Pass A = B and, as [r], the enclosure of the first m rows of the square system of order n + m of xingo-simplex’s residual_certificates test (K z = 0, z_v = β_v for the nonbasic v), evaluated with the nonbasic variables set exactly to their bounds: those rows are then B z_B − b exactly, and Theorem E holds for the exact real b.

Cost. n calls of solve_transpose (2n with refine_rows), plus Σ_p Σ_{q∈Q_p} (nnz(a_{:q}) + 1) pairs of Dot2Err (about 25 flops each; up to twice as many with refinement) — n · nnz(A) at worst — and an O(n) scan per row for S_p. Memory O(n + nnz(A)): one compressed-column copy, a few vectors of length n, buffers of the length of the longest column. Measured (X0.3, a loaded machine): 10.8 s summed over the 93 optimal bases of Netlib with refinement, the largest (dfl001, m = 6 071) 3.7 s; on a sparse synthetic family n = 10⁴ in 21 s and 3 · 10⁴ in 271 s — quadratic in n, because each solve and each scan is O(n) with dense vectors.

What stays out. Bounds in the 2-norm (by σ_min; rejected by the measurements of X0.3); an explicit R; a componentwise criterion with a vector v ≠ 𝟙 (Perron, H-matrices: another pass of n solves); Krawczyk iteration; bounds through the LU factors with comparison matrices (they would need the factors of xingo-sparse, which are opaque); parallel rows; a bound for a subset of the components (α is global); interval A or b. The transposed system needs no function of its own: call again with Aᵀ and the FTRAN as the solve.

§Invariants

(V1) Residuals. residual(A, x, b)[i] ∋ a_iᵀx − b_i, and likewise residual_of_dd, residual_csc and activity (∋ a_iᵀx), for every row and every input; an unbounded interval when a hypothesis fails (C3). Checked against exact rationals. (V2) Well-formed. Every interval returned satisfies (I2) of Chapter 11.9 and is not empty (a debug_assert!). (V3) Never wider. Each row of residual_of_dd is contained in the enclosure of steps V1–V3 for the same pairs (by construction, the intersection of V7; a debug_assert!; an empty intersection, which only a defect could produce, falls back to the enclosure of V3). Checked against exact rationals, with the width ≤ 8u|s*| + 2⁻¹²⁸S + 2⁻¹⁰⁰⁰, and on a row built so that the tail bound β′ is needed to within a factor 1.7 (tests/data/tail_bound_row.txt). (P1) Monotone. PolishReport::residual_after ≤ PolishReport::residual_before whenever the latter is finite (a debug_assert!). (P2) Untouched on failure. With PolishStop::NotFinite and zero iterations, x is the input. (E1) Never false. ForwardErrorOutcome::Certified implies Theorem E for the stored data, whatever the closure (a wrong one can only prevent the certificate). Checked against exact rationals, with adversarial closures. (E2) Nonsingular. Certified implies A nonsingular; an exactly singular A is never certified (checked). (E3) Shape. Certified ⇔ ε finite ⇔ every ε_p finite; then 0 ≤ ε_p ≤ ε and 0 ≤ α < 1. Not certified ⇒ ε = +∞ and every ε_p = +∞ (a debug_assert!). (E4) Deterministic. The same bits for the same data and the same closure (K1, D5), if the closure is a function of its argument. The BTRAN of xingo_sparse::Lu is not, by design: it chooses between its hypersparse and its dense path by a moving average of the density of the previous results, so two equal calls can sum in different orders (on one Netlib basis, share1b, they returned other bits); the same sequence of calls gives the same bits. Each result is a theorem for its own R either way.

§References

Ogita, Rump & Oishi, “Accurate sum and dot product”, SIAM J. Sci. Comput. 26 (2005), Algorithm 5.8 and Corollary 5.9 (through Chapter 11.5, which adapts and proves them), and VecSum and SumK (their Algorithms 4.3 and 4.8, Lemma 4.2), the model of steps V4–V7 — cited from memory; the a posteriori bound of V6 and its proof are this chapter’s; Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed. (2002), ch. 12 (iterative refinement; §12.1 for the mixed-precision form) — cited from memory, the statement above is the qualitative one and nothing in the code depends on its constants; Rump, “Verification methods: rigorous results using floating-point arithmetic”, Acta Numerica 19 (2010) — the distinction between a verified residual and a verified solution, and (§10) the bound ‖I − RA‖ ≤ α < 1 ⇒ ‖x̃ − x*‖ ≤ ‖R(A x̃ − b)‖/(1 − α) for an approximate inverse R that Algorithm E applies one implicit row at a time (cited from memory, not reread; the constants and the proof of Theorem E are this chapter’s, from (K2), (V1) and (I1)–(I3) only). Before release the proof and the code of Algorithm E were reviewed by an independent reviewer (task X0.3, 262 000 adversarial cases of order at most 8 checked in exact arithmetic): no false bound; the review found the corner of (K2) fixed in Chapter 11.5 and the textual corrections of steps E2 and (o) above.

Structs§

ForwardErrorBound
The outcome of Algorithm E.
ForwardErrorOptions
The parameters of Algorithm E.
PolishOptions
The parameters of Algorithm P. No literal lives in the kernel: the defaults are here.
PolishReport
The outcome of Algorithm P.

Enums§

ForwardErrorOutcome
Why Algorithm E stopped.
PolishStop
Why Algorithm P stopped.
VerifyError
What went wrong before any arithmetic. (Display and core::error::Error are implemented.)

Constants§

FLOOR 🔒
φ = (3η/u)(1 + 8u), the underflow term of step V6: the floor of β in step C5 of Chapter 11.5, exactly (the product is an f64).
U 🔒
2⁻⁵³.

Functions§

activity
Row activities with bounds, for feasibility certificates: S_i ∋ a_iᵀx, to be tested with certainly_le(u_i + t) and certainly_ge(l_i − t).
dimension 🔒
Ok iff got == expected.
distilled 🔒
Steps V4–V7 for the pairs (p, q): R′ ∋ pᵀq, or None when a step keeps the enclosure of V3. w is a buffer.
enclosure 🔒
Step V3: the interval of r ± β.
forward_error_bound
Algorithm E: from r ∋ A x − b (from residual or residual_of_dd) and a transposed solve (c ← ≈ A⁻ᵀ c, f64), proves that A is nonsingular and bounds x − A⁻¹b (Theorem E of Chapter 11.10): if the result is certified, then for the b whose residual r encloses — precisely, for every x and b with A x − b ∈ r componentwise — ‖x − A⁻¹b‖∞ ≤ norm_inf and |x_p − (A⁻¹b)_p| ≤ componentwise[p], for the stored f64 values of A.
forward_error_rows 🔒
Steps E1–E7 for a square a and a nonempty [r] of the right length; Err((outcome, α, solves)) when there is no certificate.
kronecker 🔒
δ_pq.
norm_inf 🔒
‖v‖∞ of the leading components; NaN if a component is NaN.
norm_inf_bound
A rigorous upper bound of ‖R‖∞ = max_i mag(R_i) (+∞ if some R_i is unbounded; 0 for no rows). An empty R_i also gives +∞: no function of this module returns one, and an empty enclosure proves nothing (Chapter 11.9).
polish
Algorithm P. x enters as the approximate solution (trailing components zero for an f64 solution) and leaves polished; solve overwrites its argument s with ≈ A⁻¹ s in f64.
residual
Algorithm V for an f64 solution: R_i ∋ a_iᵀx − b_i (invariant V1 of Chapter 11.10), for the stored f64 values. A row whose bound cannot be established (overflow, a NaN or an infinity in the data) gets Interval::ENTIRE.
residual_csc
As residual for a column-compressed matrix (one scatter pass; O(nnz) extra memory for the row gather).
residual_dd
b − A x in double-double, not rigorous (step P1): each component within ≈ k u² relative to Σ|a_ij x_j| + |b_i|, k the number of entries of the row (kernels::dot_mixed, then one subtraction). Note the sign: the interval residuals of this module enclose A x − b.
residual_of_dd
Algorithm V for a double-double (polished) solution: R_i ∋ a_iᵀx − b_i for the exact values hi + lo of the components of x. Steps V4–V7 of Chapter 11.10 distil the residual as if it were summed in three times the working precision, so that the width follows a residual of double-double size: a few ulps of it plus ≈ 8N³u³ Σ_j |a_ij x_j| for N = 2k + 1 pairs, never wider than the Dot2Err enclosure of steps V1–V3 (invariant V3).
row_sets 🔒
Step E3, the sets: support ← S_p (the i with h_i ≠ 0 or ℓ_i ≠ 0) and cols ← Q_p (the columns stored in the rows of S_p, and p), each without repetition; mark is all false on entry and on exit.
rows 🔒
Algorithm V over the rows of a: fill(i, cols, vals, p, q) appends to the empty (p, q) the pairs of row i (step V1); with distil, steps V4–V7 narrow each row.
rows_converged 🔒
Step P2 (c): |RN(r_i)| ≤ t_i in every row, with t_i rounded against convergence (the chapter, “How step P2 (c) rounds”).
upper 🔒
An upper bound as computed, with a NaN read as +∞: it proves nothing (invariant C3 of Chapter 11), and f64::max and f64::min would drop it.
vec_sum 🔒
One pass of VecSum (step V5): replaces w by the errors of the cascade of 2Sum over it (one shorter) and returns the sum; None if a value produced is not finite (then nothing is claimed: (T1)).