xingo_extprec/profile.rs
1//! # Chapter 11.8 — Thresholds for double-double: the measurements behind Rule P
2//!
3//! ## Purpose
4//! `xingo_sparse::LuOptions::default()` is calibrated for `f64`: some of
5//! its thresholds are multiples of the machine epsilon in disguise. Handed
6//! unchanged to `Lu<DoubleDouble>` they cap the accuracy of the factors at
7//! that of `f64` or reject matrices that double-double factorizes without
8//! trouble. This chapter records which thresholds depend on the epsilon
9//! and the measurements behind the rule that carries them to
10//! double-double. The rule itself lives in `xingo-sparse` since its 0.4.0
11//! (task L1.8, D-0113): Rule P of its Chapter 5.3,
12//! `LuOptions::for_scalar::<T>()`, which `Lu::<T>::default()` uses, and
13//! the defaults of `Regularization<T>` and `Refinement<T>` of its Chapter
14//! 5.14. Until then this crate carried the profile itself, as a hidden
15//! and provisional constructor on `DoubleDouble` (removed in L1.8); nothing
16//! of it is code here any more except the test that the generic rule
17//! gives the values measured below.
18//!
19//! ## Notation
20//! `ε₆₄ = 2⁻⁵²` and `ε_dd = 2⁻¹⁰⁴` are the `Real::EPSILON` of the two
21//! scalars; `ρ = ε_dd / ε₆₄ = 2⁻⁵²`. The *scaled residual* of a solve `B x
22//! = b` of order `n` is `‖B x − b‖∞ / (n ε_dd (max|b_ij| ‖x‖∞ + ‖b‖∞))`,
23//! computed in double-double: `O(1)` for a backward-stable solve, `O(1/ρ)
24//! ≈ 10¹⁵` for one that is only as accurate as `f64`.
25//!
26//! ## The thresholds of `LuOptions`
27//! | field | default | depends on `ε`? | double-double |
28//! |---|---|---|---|
29//! | `drop_tol` | `10⁻¹²` (`4 504 ε₆₄`) | yes: "below rounding noise" | `10⁻¹² ρ ≈ 2.2·10⁻²⁸` |
30//! | `abs_pivot_tol` | `10⁻¹⁰` | yes: "too small to trust as a pivot" | `10⁻¹⁰ ρ ≈ 2.2·10⁻²⁶` |
31//! | `update_stability_tol` | `10⁻⁸` (`≈ √ε₆₄`) | yes: digits an update may lose | `10⁻⁸ ρ ≈ 2.2·10⁻²⁴` |
32//! | `growth_limit` | `10¹⁰` | in principle (`growth · ε` is the backward error) | unchanged |
33//! | `rel_pivot_tol` | `10⁻²` | no: sparsity against growth | unchanged |
34//! | `search_limit`, `fill_factor`, `refactor_interval`, `hyper_*_density` | | no: structure and cost | unchanged |
35//!
36//! ## Rule P (the profile)
37//! P1. \[Scale.\] A threshold that is a magnitude below which a *computed*
38//! quantity is taken for rounding noise — `drop_tol`, `abs_pivot_tol`,
39//! `update_stability_tol` — is multiplied by `ρ`.
40//! P2. \[Keep.\] Every other option keeps its default.
41//!
42//! For `f64` the rule is the identity (`ρ = 1`), so it is stated for any
43//! scalar `T` as "multiply by `ε_T / ε₆₄`" — the generic form of
44//! `xingo-sparse` (Rule P of its Chapter 5.3).
45//!
46//! ## Measurements (`examples/dd_profile.rs`, 2026-11-15)
47//! All in `Lu<DoubleDouble>`, residuals computed in double-double.
48//!
49//! * **`drop_tol`.** With the `f64` default (`10⁻¹²`) the median scaled
50//! residual over 15 random bases was `2.2·10¹³` (order 300) and
51//! `4.1·10¹⁵` (order 800): the accuracy of `f64`, sixteen digits thrown
52//! away. With `0`, `2⁻¹⁰⁰`, `10⁻²⁹` and `10⁻¹² ρ` the medians were between
53//! `3.2` and `10.6` with no order among them (the differences are the
54//! pivot sequences, which the pattern decides); with `10⁻²⁴` the median
55//! of the order-800 family rose to `231`. Dropping is still worth
56//! having: an entry that cancels exactly in `f64` leaves a residue of a
57//! few `ε_dd` in double-double, and with `drop_tol = 0` those residues
58//! stay as fill (0.6–2 % more entries of `L + U` here). On bases of small
59//! integers the tolerance made no difference at all (nothing tiny
60//! arises).
61//! * **`abs_pivot_tol`.** With the `f64` default the Hilbert matrices of
62//! order 16, 20 and 24 are declared singular (deficiency 4, 6, 8), as is
63//! a basis with two columns `10⁻¹¹` apart and a matrix whose columns are
64//! graded over 12 decades. With `10⁻¹⁰ ρ` all of them factorize: Hilbert
65//! 16 to an error of `1.3·10⁻¹⁰` in the solution (condition `≈ 10²²`),
66//! Hilbert 20 to `1.2·10⁻⁴`; Hilbert 24 (condition above `1/ε_dd`) is
67//! accepted and its solution is noise — the threshold is not a condition
68//! estimator, in either scalar. Columns `10⁻²⁷` apart, and columns graded
69//! over 30 decades, are singular under the profile too: it is absolute,
70//! in the units of `B`, as the default is (scale first).
71//! * **`update_stability_tol`.** 90 Forrest–Tomlin exchanges on a basis of
72//! order 150, every third with a pivot `α_r` of a chosen size. For
73//! `α_r = 10⁻²` none of the three candidates below refused anything and
74//! the updated factor was at most 110 times less accurate than a fresh
75//! one. For `α_r = 10⁻⁶`,
76//! `10⁻¹⁰`, `10⁻¹⁴` the updated factors were up to `3.5·10⁹`,
77//! `3.4·10¹³`, `2.8·10¹³` times less accurate under `10⁻⁸` **and** (the
78//! last one `2.5·10¹³`) under `10⁻⁸ √ρ`, which refused 0, 1, 1 updates, and `2.1·10⁸`,
79//! `7.4·10¹²`, `2.1·10¹¹` under `10⁻⁸ ρ` (which refused 1, 20, 13;
80//! median loss `230`, `160`, `1.4` against `4 400`, `23 000`, `11`).
81//! Hence `ρ`, not `√ρ` — and a caveat: **no tolerance bounds the loss**
82//! (`10⁻²⁸` still let `7.4·10¹²` through). Task L1.8 traced the loss to
83//! the multipliers of the row eta, which no tolerance on the stability
84//! statistic sees, and `xingo-sparse` 0.4.0 bounds them (step U4′ of its
85//! Chapter 5.5, `LuOptions::update_multiplier_limit`; D-0113).
86//! * **`growth_limit`.** The largest growth seen was `6.5·10⁷`; no
87//! measurement speaks for changing the limit, so it stays.
88//!
89//! ## What is not in `LuOptions`
90//! The same question for the KKT solver was measured here and is, since
91//! `xingo-sparse` 0.4.0, the rule of the defaults of `Regularization<T>`
92//! and `Refinement<T>` (its Chapter 5.14: shifts and bump × `√ρ`, pivot
93//! tolerance and target × `ρ`):
94//! `Refinement::default()` stops at a residual of `10⁻¹²`, the accuracy of
95//! `f64` (`2.2·10⁻²⁸ = 10⁻¹² ρ` was reached in 5–8 steps where it is
96//! attainable); `Regularization::default()` (`10⁻⁶`, `10⁻⁸`) leaves a plain
97//! solve at `10⁻⁵`–`10⁰` and costs those steps, against 2–4 with the shifts
98//! scaled by `√ρ`; the two thresholds of the pivoted path
99//! (`SupernodalOptions::zero_pivot_tol`, `pivot_threshold`) made no
100//! difference on the matrices tried.
101//!
102//! ## Invariants
103//! (O1) `LuOptions::for_scalar::<DoubleDouble>()` differs from
104//! `LuOptions::default()` in the three fields of step P1 only, each
105//! exactly `ρ` times the default (a power of two: the product is
106//! exact) — the values of the provisional profile this chapter
107//! measured. Tested here; the generic statement is tested in
108//! `xingo-sparse`.
109//!
110//! ## References
111//! Chapter 5.3 of `xingo-sparse` (`LuOptions`: what each threshold tests;
112//! Rule P)
113//! and Chapter 5.5 (the stability test of the Forrest–Tomlin update);
114//! Higham, *Accuracy and Stability of Numerical Algorithms* (2002), §9.3
115//! (growth and backward error of Gaussian elimination); D-0109 (the
116//! reservation of L2.2a that this chapter answers).
117
118#[cfg(test)]
119#[allow(clippy::float_cmp)] // the scalings are exact
120mod tests {
121 use xingo_sparse::{Lu, LuFactor, LuOptions, Refinement, Regularization};
122
123 use crate::dd::DoubleDouble;
124
125 /// Invariant (O1): Rule P of `xingo-sparse` gives the profile measured
126 /// in this chapter (`ρ = 2⁻⁵²` on the three noise thresholds).
127 #[test]
128 fn rule_p_gives_the_measured_profile() {
129 let d = LuOptions::default();
130 let p = LuOptions::for_scalar::<DoubleDouble>();
131 let rho = f64::EPSILON;
132 assert_eq!(DoubleDouble::EPSILON.hi() / f64::EPSILON, rho);
133 assert_eq!(p.drop_tol, 1e-12 * rho);
134 assert_eq!(p.abs_pivot_tol, 1e-10 * rho);
135 assert_eq!(p.update_stability_tol, 1e-8 * rho);
136 assert_eq!(
137 LuOptions {
138 drop_tol: d.drop_tol,
139 abs_pivot_tol: d.abs_pivot_tol,
140 update_stability_tol: d.update_stability_tol,
141 ..p
142 },
143 d
144 );
145 assert_eq!(*Lu::<DoubleDouble>::default().options(), p);
146 // The "dd reg." profile of the KKT table above.
147 let r = Regularization::<DoubleDouble>::default();
148 let s = rho.sqrt();
149 assert_eq!(r.primal, DoubleDouble::from_f64(1e-6 * s));
150 assert_eq!(r.dual, DoubleDouble::from_f64(1e-8 * s));
151 assert_eq!(r.pivot_tol, Some(DoubleDouble::from_f64(1e-13 * rho)));
152 assert_eq!(r.bump, DoubleDouble::from_f64(2e-7 * s));
153 let f = Refinement::<DoubleDouble>::default();
154 assert_eq!(f.target_residual, DoubleDouble::from_f64(1e-12 * rho));
155 assert_eq!(f.max_iters, 10);
156 }
157}