Expand description
§Chapter 11.8 — Thresholds for double-double: the measurements behind Rule P
§Purpose
xingo_sparse::LuOptions::default() is calibrated for f64: some of
its thresholds are multiples of the machine epsilon in disguise. Handed
unchanged to Lu<DoubleDouble> they cap the accuracy of the factors at
that of f64 or reject matrices that double-double factorizes without
trouble. This chapter records which thresholds depend on the epsilon
and the measurements behind the rule that carries them to
double-double. The rule itself lives in xingo-sparse since its 0.4.0
(task L1.8, D-0113): Rule P of its Chapter 5.3,
LuOptions::for_scalar::<T>(), which Lu::<T>::default() uses, and
the defaults of Regularization<T> and Refinement<T> of its Chapter
5.14. Until then this crate carried the profile itself, as a hidden
and provisional constructor on DoubleDouble (removed in L1.8); nothing
of it is code here any more except the test that the generic rule
gives the values measured below.
§Notation
ε₆₄ = 2⁻⁵² and ε_dd = 2⁻¹⁰⁴ are the Real::EPSILON of the two
scalars; ρ = ε_dd / ε₆₄ = 2⁻⁵². The scaled residual of a solve B x = b of order n is ‖B x − b‖∞ / (n ε_dd (max|b_ij| ‖x‖∞ + ‖b‖∞)),
computed in double-double: O(1) for a backward-stable solve, O(1/ρ) ≈ 10¹⁵ for one that is only as accurate as f64.
§The thresholds of LuOptions
| field | default | depends on ε? | double-double |
|---|---|---|---|
drop_tol | 10⁻¹² (4 504 ε₆₄) | yes: “below rounding noise” | 10⁻¹² ρ ≈ 2.2·10⁻²⁸ |
abs_pivot_tol | 10⁻¹⁰ | yes: “too small to trust as a pivot” | 10⁻¹⁰ ρ ≈ 2.2·10⁻²⁶ |
update_stability_tol | 10⁻⁸ (≈ √ε₆₄) | yes: digits an update may lose | 10⁻⁸ ρ ≈ 2.2·10⁻²⁴ |
growth_limit | 10¹⁰ | in principle (growth · ε is the backward error) | unchanged |
rel_pivot_tol | 10⁻² | no: sparsity against growth | unchanged |
search_limit, fill_factor, refactor_interval, hyper_*_density | no: structure and cost | unchanged |
§Rule P (the profile)
P1. [Scale.] A threshold that is a magnitude below which a computed
quantity is taken for rounding noise — drop_tol, abs_pivot_tol,
update_stability_tol — is multiplied by ρ.
P2. [Keep.] Every other option keeps its default.
For f64 the rule is the identity (ρ = 1), so it is stated for any
scalar T as “multiply by ε_T / ε₆₄” — the generic form of
xingo-sparse (Rule P of its Chapter 5.3).
§Measurements (examples/dd_profile.rs, 2026-11-15)
All in Lu<DoubleDouble>, residuals computed in double-double.
drop_tol. With thef64default (10⁻¹²) the median scaled residual over 15 random bases was2.2·10¹³(order 300) and4.1·10¹⁵(order 800): the accuracy off64, sixteen digits thrown away. With0,2⁻¹⁰⁰,10⁻²⁹and10⁻¹² ρthe medians were between3.2and10.6with no order among them (the differences are the pivot sequences, which the pattern decides); with10⁻²⁴the median of the order-800 family rose to231. Dropping is still worth having: an entry that cancels exactly inf64leaves a residue of a fewε_ddin double-double, and withdrop_tol = 0those residues stay as fill (0.6–2 % more entries ofL + Uhere). On bases of small integers the tolerance made no difference at all (nothing tiny arises).abs_pivot_tol. With thef64default the Hilbert matrices of order 16, 20 and 24 are declared singular (deficiency 4, 6, 8), as is a basis with two columns10⁻¹¹apart and a matrix whose columns are graded over 12 decades. With10⁻¹⁰ ρall of them factorize: Hilbert 16 to an error of1.3·10⁻¹⁰in the solution (condition≈ 10²²), Hilbert 20 to1.2·10⁻⁴; Hilbert 24 (condition above1/ε_dd) is accepted and its solution is noise — the threshold is not a condition estimator, in either scalar. Columns10⁻²⁷apart, and columns graded over 30 decades, are singular under the profile too: it is absolute, in the units ofB, as the default is (scale first).update_stability_tol. 90 Forrest–Tomlin exchanges on a basis of order 150, every third with a pivotα_rof a chosen size. Forα_r = 10⁻²none of the three candidates below refused anything and the updated factor was at most 110 times less accurate than a fresh one. Forα_r = 10⁻⁶,10⁻¹⁰,10⁻¹⁴the updated factors were up to3.5·10⁹,3.4·10¹³,2.8·10¹³times less accurate under10⁻⁸and (the last one2.5·10¹³) under10⁻⁸ √ρ, which refused 0, 1, 1 updates, and2.1·10⁸,7.4·10¹²,2.1·10¹¹under10⁻⁸ ρ(which refused 1, 20, 13; median loss230,160,1.4against4 400,23 000,11). Henceρ, not√ρ— and a caveat: no tolerance bounds the loss (10⁻²⁸still let7.4·10¹²through). Task L1.8 traced the loss to the multipliers of the row eta, which no tolerance on the stability statistic sees, andxingo-sparse0.4.0 bounds them (step U4′ of its Chapter 5.5,LuOptions::update_multiplier_limit; D-0113).growth_limit. The largest growth seen was6.5·10⁷; no measurement speaks for changing the limit, so it stays.
§What is not in LuOptions
The same question for the KKT solver was measured here and is, since
xingo-sparse 0.4.0, the rule of the defaults of Regularization<T>
and Refinement<T> (its Chapter 5.14: shifts and bump × √ρ, pivot
tolerance and target × ρ):
Refinement::default() stops at a residual of 10⁻¹², the accuracy of
f64 (2.2·10⁻²⁸ = 10⁻¹² ρ was reached in 5–8 steps where it is
attainable); Regularization::default() (10⁻⁶, 10⁻⁸) leaves a plain
solve at 10⁻⁵–10⁰ and costs those steps, against 2–4 with the shifts
scaled by √ρ; the two thresholds of the pivoted path
(SupernodalOptions::zero_pivot_tol, pivot_threshold) made no
difference on the matrices tried.
§Invariants
(O1) LuOptions::for_scalar::<DoubleDouble>() differs from
LuOptions::default() in the three fields of step P1 only, each
exactly ρ times the default (a power of two: the product is
exact) — the values of the provisional profile this chapter
measured. Tested here; the generic statement is tested in
xingo-sparse.
§References
Chapter 5.3 of xingo-sparse (LuOptions: what each threshold tests;
Rule P)
and Chapter 5.5 (the stability test of the Forrest–Tomlin update);
Higham, Accuracy and Stability of Numerical Algorithms (2002), §9.3
(growth and backward error of Gaussian elimination); D-0109 (the
reservation of L2.2a that this chapter answers).