Skip to main content

xingo_sparse/
kkt.rs

1//! # Chapter 5.14 — KKT systems: analyze once, factorize many
2//!
3//! *New with task L1.5 (PLAN.md trilha L; the contract's §5.7).*
4//!
5//! ## Purpose
6//! At every iteration a primal-dual interior-point method solves a linear
7//! system whose matrix has a *fixed pattern* and *changing values*: the
8//! normal equations `A D Aᵀ` or the augmented (KKT) system
9//! `[−D, Aᵀ; A, 0]`, where the diagonal `D > 0` spreads over many orders
10//! of magnitude as the iterates approach the boundary (Wright 1997, ch.
11//! 11). The interface below is the shape of CHOLMOD (Chen, Davis, Hager &
12//! Rajamanickam 2008): a *symbolic* phase that depends on the pattern only
13//! (ordering, elimination tree, structure of the factor) is done once, a
14//! *numeric* phase is repeated for every new set of values, and a *solve*
15//! phase uses the factor. On top of it sit two things that every backend
16//! shares and that therefore live here, not in a backend:
17//!
18//! * the **regularization policy** (Altman & Gondzio 1999): which static
19//!   shifts `ρ`, `δ` enter which diagonal block, which sign each pivot must
20//!   have, which pivots a backend may bump, and the inertia check (S6);
21//! * **iterative refinement** against the matrix the caller really wants
22//!   solved ([`KktSolver::solve_refined`], a provided method), which keeps
23//!   its best iterate (S7).
24//!
25//! ## Notation
26//! `K ∈ R^{N×N}` symmetric, given by its **lower triangle** in a
27//! [`CscMatrix`] (entries `i ≥ j`; CHOLMOD's `stype < 0`). A matrix that
28//! stores both triangles is accepted when its pattern is symmetric: the
29//! entries above the diagonal are then ignored. Two forms ([`KktForm`]):
30//!
31//! * `NormalEquations`: `K = A D Aᵀ` (`N = m`), positive (semi)definite;
32//! * `Augmented { n_primal: n, n_dual: m }`: `K = [−D, Aᵀ; A, 0]`
33//!   (`N = n + m`), the `n` primal unknowns first.
34//!
35//! A [`Regularization`] `(ρ, δ, τ, β, scale)` = (`primal`, `dual`,
36//! `pivot_tol`, `bump`, `scale`) defines the matrix the backend
37//! factorizes. With `S = diag(s)` the symmetric equilibration of `K`
38//! (step K2′ below; powers of two) and `Σ = diag(−ρ I_n, δ I_m)` for the
39//! augmented system (`Σ = δ I_m` for the normal equations),
40//! ```text
41//!   K_reg = K + S⁻¹ Σ S⁻¹    (ShiftScale::Equilibrated, the default),
42//!   K_reg = K + Σ            (ShiftScale::Absolute),
43//! ```
44//! so the default shifts are taken *in the equilibrated matrix*
45//! `K̃ = S K S`, whose rows have their largest entry near 1: `δ = 10⁻⁸` is
46//! then relative to the magnitude of each row, whatever the spread of
47//! `D`. The *pivot signs* are `σ_k = −1` for the primal rows, `+1` for the
48//! dual rows (all `+1` for the normal equations). The *inertia* of a symmetric
49//! matrix is the triple ([`Inertia`]) of the numbers of positive, negative
50//! and zero eigenvalues; by Sylvester's law it equals the count of
51//! positive, negative and zero pivots of any `P K Pᵀ = L Δ Lᵀ` with `Δ`
52//! diagonal, and, for `Δ` block diagonal with `1×1` and `2×2` blocks,
53//! the sum of the inertias of the blocks. The *relative residual* of `x`
54//! is `res(x) = ‖K x − b‖_∞ / (1 + ‖b‖_∞)`.
55//!
56//! ## Why the regularized augmented system needs no pivoting
57//! With `D > 0`, `ρ > 0` and `δ > 0`, `K_reg` is *quasi-definite*: its
58//! `(1,1)` block is negative definite and its `(2,2)` block positive
59//! definite. Vanderbei (1995) proved that every symmetric permutation of a
60//! quasi-definite matrix has an `LDLᵀ` factorization with diagonal `Δ`,
61//! the first block's pivots negative and the second's positive; Gill,
62//! Saunders & Shinnerl (1996) bound its stability by the size of the
63//! regularization. So the ordering can be chosen for sparsity alone, at
64//! analysis time — the property that makes "analyze once" possible for the
65//! augmented system — and the inertia is known in advance: `(m, n, 0)`.
66//! Without regularization (`ρ = 0` or `δ = 0`) this guarantee is lost, and
67//! a backend needs `2×2` pivots (Bunch & Kaufman 1977) or dynamic
68//! regularization to factorize.
69//!
70//! *On the sign convention.* The contract's (S6) writes the expected
71//! inertia of the augmented system as `(n, m, 0)` for the matrix
72//! `[−D − ρI, Aᵀ; A, δI]`; for that matrix the `n` primal pivots are
73//! *negative* and the `m` dual pivots *positive*, so with the field order
74//! `(positive, negative, zero)` of [`Inertia`] the triple is
75//! `{ positive: m, negative: n, zero: 0 }` — which is what this chapter
76//! checks (`n` primal and `m` dual eigenvalues, each block with its own
77//! sign; listed for ratification in L1.5).
78//!
79//! ## Algorithm K (the regularization policy shared by every backend)
80//! K1. [Validate.] `K` satisfies (S1); it is square, of order `N` equal to
81//!     the form's (`n + m` for the augmented system); its lower triangle
82//!     lies inside the pattern given to the analysis (missing entries are
83//!     zeros: an IPM value that became exactly zero leaves the CSC
84//!     pattern, (C3) of Chapter 5.8).
85//! K1′. [Finite input.] Every stored value of the lower triangle of `K`
86//!     is finite ([`KktError::Structure`] otherwise): a NaN or an infinity
87//!     in `K` would otherwise surface as a NaN solution.
88//! K2. [Assemble.] The lower triangle of `K` on the analyzed pattern, which
89//!     has a full diagonal (a dual diagonal entry absent from `K` is `0`).
90//! K2′. [Symmetric equilibration (Ruiz 2001).] Scale `K` to
91//!     `K̃ = S K S`, `S = diag(s)` with powers of two: start from
92//!     `s = 1`; in each pass compute, for every row `i` of the *scaled*
93//!     matrix (both triangles), `r_i = max_j |k̃_ij|` and multiply `s_i` by
94//!     `⌊1/√r_i⌉₂` (rows without entries keep `s_i`); stop after a pass
95//!     that changes no `s_i` — exact, the factors being powers of two — or
96//!     after [`EQUILIBRATION_PASSES`] passes. Every row of `K̃` then has
97//!     its largest entry in `[2^{-1}, 2^{1}]` roughly, whatever the spread
98//!     of `D`. The scaling is a congruence, so the inertia of `K̃` is that
99//!     of `K` (Sylvester). Being by powers of two it is exact, and an
100//!     `LDLᵀ` without pivoting *commutes* with it: the factor of `K̃` is
101//!     `(S L S⁻¹)(S Δ S)(S L S⁻¹)ᵀ` bit for bit, barring overflow and
102//!     underflow. So K2′ by itself changes exactly two things: the
103//!     thresholds `τ`, `β` of K3 become *relative* to the magnitude of
104//!     each row, and the intermediate values stay in range.
105//! K2″. [Static regularization.] Add the shifts on the diagonal of `K̃`:
106//!     `Σ` itself with [`ShiftScale::Equilibrated`] (`K̃_reg = K̃ + Σ`),
107//!     `S Σ S` with [`ShiftScale::Absolute`] (`K̃_reg = S (K + Σ) S`): `−ρ`
108//!     on the primal diagonal and `+δ` on the dual one (normal equations:
109//!     `+δ` everywhere; `ρ` does not apply, the caller folds it into
110//!     `D`). The backend factorizes `K̃_reg` and solves with `S F̃⁻¹ S`;
111//!     `S⁻¹ K̃_reg S⁻¹` is the `K_reg` of the notation above.
112//! K3. [Dynamic regularization.] If `τ = pivot_tol` is `Some`, the backend
113//!     replaces every pivot `d_k` with `σ_k d_k ≤ τ` (too small, or of the
114//!     wrong sign) by `σ_k β` while it eliminates — the dynamic part of
115//!     Altman & Gondzio's (1999) primal-dual regularization, in the form
116//!     faer's `LdltRegularization` applies — and counts the bumped pivots. Bumping
117//!     needs the sign `σ_k`, which only the form knows — the policy is
118//!     here; the elimination loop that applies it is the backend's.
119//! K3′. [Finite factor (S10).] Every stored value of the factor is
120//!     finite; otherwise the call fails with [`KktError::NotFinite`] at
121//!     the first column (original numbering) holding a NaN or an infinity
122//!     — an overflow of the elimination is reported, never handed to the
123//!     solves (where it would become a NaN solution).
124//! K4. [Inertia (S6).] From the pivots of the factor, count the inertia.
125//!     If it is not `(N, 0, 0)` (normal) or `(m, n, 0)` (augmented),
126//!     return [`KktError::WrongInertia`]. With `τ = Some`, every pivot has
127//!     the sign `σ_k` by K3, so the check cannot fail: the factor is that
128//!     of a perturbation of `K_reg` with the right inertia, and refinement
129//!     (Algorithm F) measures how far it is from `K`.
130//!
131//! ## Choosing the regularization
132//! Three facts, measured on the 558 Netlib systems of L1.5/L1.5b (93 LPs ×
133//! normal and augmented × the start, middle and end regimes of `D`),
134//! decide the default.
135//!
136//! 1. *A shift must be above the rounding level of its row.* A shift
137//!    `δ < ε_T · max|k_ij|` changes nothing in floating point. At the end
138//!    of an interior-point method `D` spreads to `10^{±10}` and
139//!    `max|K| ≈ 10^{10}`, so the absolute `ρ = δ = 10⁻⁸` of L1.5 failed on
140//!    32 of the 558 systems (zero pivots after overflow, or NaN
141//!    solutions). One shift relative to the whole matrix
142//!    ([`Regularization::relative_to`]`(k, 10⁻⁸)`, `δ ≈ 10²` there)
143//!    factorizes all 558, but perturbs the rows of small magnitude so much
144//!    that refinement against the unregularized `K` stalls (418 of 558 at
145//!    or below `10⁻¹⁰` after 50 classical steps). Shifts taken in the
146//!    equilibrated matrix (step K2″, [`ShiftScale::Equilibrated`]) are
147//!    relative *row by row*.
148//! 2. *The product `ρδ` must be well above the unit roundoff.* Eliminating
149//!    a primal pivot of size `~ρ` adds terms of size `~1/ρ` to the dual
150//!    block, whose pivots must stay above `δ`: with `ρ = δ = 10⁻⁸` in the
151//!    equilibrated matrix (`ρδ = 10⁻¹⁶ < ε`) nine augmented systems of the
152//!    end regime still got pivots of the wrong sign; with `ρδ ≥ 10⁻¹⁴` none
153//!    did (the stability analysis of quasi-definite factorizations of Gill,
154//!    Saunders & Shinnerl 1996 bounds the growth by the shifts).
155//! 3. *The normal equations see only `δ`*, and every unit of `δ` slows the
156//!    refinement on their small eigenvalues: `δ = 10⁻⁶` left 46 systems
157//!    above `10⁻¹⁰` after ten steps, `δ = 10⁻⁸` none (with Algorithm F's
158//!    GMRES).
159//!
160//! Hence the default `ρ = 10⁻⁶`, `δ = 10⁻⁸`, equilibrated: all 558 systems
161//! with the right inertia, no bump, and a residual against the
162//! unregularized `K` at or below `10⁻¹⁰` after the ten steps of
163//! [`Refinement::default`] (L1.5b, D1–D3; the bumping of K3 is the safety
164//! net, not the mechanism). An interior-point method that wants other
165//! values passes them; [`ShiftScale::Absolute`] keeps shifts in the
166//! caller's units.
167//!
168//! ## Algorithm F (Refinement by preconditioned GMRES, with the best iterate; (S7))
169//! Given a factor `F ≈ K_reg`, the matrix `K` to be solved (the
170//! *unregularized* one, or `K_reg` itself — whichever the caller passes),
171//! `b` and a [`Refinement`] `(t_max, target)` = (`max_iters`,
172//! `target_residual`), where `t_max` bounds the solves with `F` after the
173//! first one:
174//! F1. `x ← F⁻¹ b`; `r ← b − K x`; `ρ ← res(x)`; `x* ← x`, `ρ* ← ρ`;
175//!     `t ← 0`.
176//! F2. [Done?] If `ρ* ≤ target`, `ρ` is not finite, or `t = t_max`, go to
177//!     F6.
178//! F3. [Arnoldi cycle, right preconditioned (Saad 2003, §9.3.2).] `x ← x*`,
179//!     `r ← b − K x` (the residual of the best iterate), `β ← ‖r‖₂`,
180//!     `v₁ ← r/β`, `g ← β e₁`, `m ← t_max − t`. For `j = 1, 2, …, m`:
181//!     `z_j ← F⁻¹ v_j`, `t ← t + 1`; `w ← K z_j`; modified Gram–Schmidt
182//!     `h_ij ← ⟨w, v_i⟩`, `w ← w − h_ij v_i` for `i ≤ j`;
183//!     `h_{j+1,j} ← ‖w‖₂`; apply the previous Givens rotations to column
184//!     `j` of `H`, compute the rotation that annihilates `h_{j+1,j}` and
185//!     apply it to `g`. Leave the loop with `k = j` when `h_{j+1,j} = 0`
186//!     (the Krylov space is invariant: the solution is in it), when
187//!     `|g_{j+1}| ≤ target·(1 + ‖b‖_∞)` (in exact arithmetic `|g_{j+1}|`
188//!     is the 2-norm of the residual, which bounds its ∞-norm), or when
189//!     `j = m`.
190//! F4. [Update.] Solve the `k × k` upper triangular system `R y = g_{1:k}`
191//!     (the rotated `H`); `x ← x* + Σ_j y_j z_j`; `r ← b − K x`;
192//!     `ρ ← res(x)`. If `ρ < ρ*`, set `x* ← x`, `ρ* ← ρ`.
193//! F5. Go to F2 (a new cycle restarts from `x*`).
194//! F6. Return `x*` with `iters = t`, `residual = ρ*` and
195//!     `converged = (ρ* ≤ target)`.
196//!
197//! *Why GMRES and not the classical iteration.* The classical refinement
198//! `x ← x + F⁻¹ r` of L1.5 contracts the error by the factor
199//! `‖I − F⁻¹ K‖ = ‖F⁻¹ (K_reg − K)‖` per step; on the eigenvectors of `K`
200//! whose eigenvalues are not much larger than the shifts — the nearly
201//! rank-deficient `A D Aᵀ` of the middle of an interior-point method, or
202//! an augmented system with `D` spread to `10^{±4}` — that factor is close
203//! to 1, and ten steps left 15 of the 558 Netlib systems of L1.5b above
204//! `10⁻¹⁰` against the unregularized `K`. Right-preconditioned GMRES
205//! minimizes `‖b − K x‖₂` over the same affine Krylov space
206//! `x₀ + span{F⁻¹r₀, (F⁻¹K) F⁻¹r₀, …}` that holds the classical
207//! iterates, so in exact arithmetic it is never worse, and the few
208//! eigenvalues of `F⁻¹ K` far from 1 — one per small eigenvalue of `K`,
209//! the regularization being a small perturbation elsewhere — cost one
210//! step each. This is GMRES preconditioned by a perturbed (statically
211//! pivoted, here statically regularized) `LDLᵀ`, analyzed by Arioli,
212//! Duff, Gratton & Pralet (2007), and GMRES-based iterative refinement
213//! (Carson & Higham 2017). One cycle with all the budget is the normal
214//! case; F5 restarts only when the estimate `|g_{k+1}|` and the computed
215//! residual disagree (rounding) or the budget allows another cycle after
216//! a breakdown.
217//!
218//! *Memory.* A cycle of `m` steps keeps `m + 1` Arnoldi vectors `v_j` and
219//! `m` preconditioned vectors `z_j` (so F4 needs no further solve), plus
220//! `H` and the rotations: `(2m + 3) N + O(m²)` scalars, held by a
221//! [`RefineWorkspace`] that [`KktSolver::solve_refined_with`] reuses
222//! across calls — after the first call with a given order and budget,
223//! refinement allocates nothing (Chapter 5.15 for the solves themselves).
224//!
225//! The residual is computed with the stored lower triangle of `K`
226//! (`y_i += k_ij x_j` and, for `i ≠ j`, `y_j += k_ij x_i`), in the working
227//! precision of `T` — fixed-precision refinement, which brings the
228//! componentwise backward error of a backward-stable factorization down to
229//! the order of the unit roundoff (Skeel 1980; Higham 2002, ch. 12); with
230//! a regularized factor it also removes the bias of the shifts (Altman &
231//! Gondzio 1999, §6). When `K` is singular but `b` is consistent the
232//! iteration still converges in the residual.
233//!
234//! ## Invariants
235//! (K1) The pattern given to [`KktSolver::analyze`] is square and either
236//!      lower triangular or structurally symmetric
237//!      ([`KktError::NotSymmetric`] otherwise).
238//! (S6) (the contract's) [`KktSolver::factorize`] returns the inertia of
239//!      the factor it computed; it is `(N, 0, 0)` for the normal equations
240//!      and `(m, n, 0)` = `{positive: m, negative: n, zero: 0}` for the
241//!      augmented system, or the call fails with
242//!      [`KktError::WrongInertia`]. Asserted on every successful
243//!      factorization in debug builds.
244//! (S7) (the contract's) [`KktSolver::solve_refined`] never returns a
245//!      residual larger than that of its first solve: it keeps the best
246//!      iterate (step F4). Asserted in debug builds.
247//! (S10) A factor returned by [`KktSolver::factorize`] holds only finite
248//!      values (step K3′); [`KktSolver::solve_refined`] reports a
249//!      non-finite solution explicitly: its `residual` is NaN or infinite
250//!      exactly when the returned `x` has a non-finite entry, and then
251//!      `converged = false` (the input `K`, `b` being finite).
252//!
253//! ## References
254//! Chen, Davis, Hager & Rajamanickam, "Algorithm 887: CHOLMOD, supernodal
255//! sparse Cholesky factorization and update/downdate", ACM TOMS 35(3),
256//! 2008 (the analyze/factorize/solve shape, the lower-triangle input, the
257//! supernodal/simplicial selection by flops per `nnz(L)` — read, not
258//! copied); Altman & Gondzio, "Regularized symmetric indefinite systems in
259//! interior point methods for linear and quadratic optimization", Optim.
260//! Methods Softw. 11–12, 1999; Vanderbei, "Symmetric quasidefinite
261//! matrices", SIAM J. Optim. 5(1), 1995; Gill, Saunders & Shinnerl, "On
262//! the stability of Cholesky factorization for symmetric quasidefinite
263//! systems", SIAM J. Matrix Anal. Appl. 17(1), 1996; Wright,
264//! *Primal-Dual Interior-Point Methods*, SIAM 1997, ch. 11; Bunch &
265//! Kaufman, "Some stable methods for calculating inertia and solving
266//! symmetric linear systems", Math. Comp. 31, 1977; Skeel, "Iterative
267//! refinement implies numerical stability for Gaussian elimination", Math.
268//! Comp. 35, 1980; Higham, *Accuracy and Stability of Numerical
269//! Algorithms*, 2nd ed. 2002, ch. 11–12; Ruiz, "A scaling algorithm to
270//! equilibrate both rows and columns norms in matrices", RAL-TR-2001-034,
271//! 2001 (symmetric variant, rounded to powers of two here); Stellato et al., "OSQP: an
272//! operator splitting solver for quadratic programs", Math. Prog. Comp.
273//! 12, 2020 (quasi-definite `LDLᵀ` without pivoting in an optimization
274//! solver); Saad, *Iterative Methods for Sparse Linear Systems*, 2nd ed.,
275//! SIAM 2003, §6.5 and §9.3 (GMRES, right preconditioning, Givens
276//! rotations); Arioli, Duff, Gratton & Pralet, "A note on GMRES
277//! preconditioned by a perturbed `LDLᵀ` decomposition with static
278//! pivoting", SIAM J. Sci. Comput. 29(5), 2007; Carson & Higham, "A new
279//! analysis of iterative refinement and its application to accurate
280//! solution of ill-conditioned sparse linear systems", SIAM J. Sci.
281//! Comput. 39(6), 2017; Saunders & Tomlin, "Solving regularized linear
282//! programs using barrier methods and KKT systems", SOL 96-4, 1996 (the
283//! product `ρδ` above the rounding level for a stable quasi-definite
284//! factorization).
285
286use crate::real::{Real, is_exact_zero, is_nan, le, lt};
287use crate::{CscMatrix, KktError, Ordering, Pattern, SparseError};
288
289/// Inertia `(positive, negative, zero)` of a symmetric factorization: the
290/// numbers of positive, negative and zero pivots (eigenvalues, by
291/// Sylvester's law).
292#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
293pub struct Inertia {
294    /// Positive pivots.
295    pub positive: usize,
296    /// Negative pivots.
297    pub negative: usize,
298    /// Zero pivots.
299    pub zero: usize,
300}
301
302/// Where the static shifts `ρ`, `δ` of a [`Regularization`] are applied
303/// (step K2″ of Algorithm K).
304#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
305pub enum ShiftScale {
306    /// On the diagonal of the equilibrated matrix `K̃ = S K S` (step K2′),
307    /// whose rows have their largest entry near 1: the shifts are
308    /// relative to the magnitude of each row, `K_reg = K + S⁻¹ Σ S⁻¹`.
309    /// The default.
310    #[default]
311    Equilibrated,
312    /// On the diagonal of `K` itself, in the caller's units:
313    /// `K_reg = K + Σ`.
314    Absolute,
315}
316
317/// Regularization of a quasi-definite KKT matrix (Altman & Gondzio 1999;
318/// Algorithm K).
319#[derive(Clone, Copy, Debug, PartialEq)]
320pub struct Regularization<T: Real = f64> {
321    /// `ρ ≥ 0`, added to the primal block (which becomes `−D − ρI`, in
322    /// the units [`Regularization::scale`] says); ignored for the normal
323    /// equations.
324    pub primal: T,
325    /// `δ ≥ 0`, added to the dual block (`δI`), or to the whole diagonal
326    /// of the normal equations (`A D Aᵀ + δI`), in the units
327    /// [`Regularization::scale`] says.
328    pub dual: T,
329    /// Below this magnitude (or with the wrong sign) a pivot of the
330    /// equilibrated matrix is bumped to `±bump` with the sign the inertia
331    /// expects (dynamic regularization, step K3); `None` disables it.
332    pub pivot_tol: Option<T>,
333    /// The magnitude `β > 0` of a bumped pivot (of the equilibrated
334    /// matrix).
335    pub bump: T,
336    /// Whether `ρ`, `δ` are taken in the equilibrated matrix (the default)
337    /// or in `K` itself (step K2″).
338    pub scale: ShiftScale,
339}
340
341impl<T: Real> Default for Regularization<T> {
342    /// `ρ = 10⁻⁶`, `δ = 10⁻⁸` *in the equilibrated matrix*
343    /// ([`ShiftScale::Equilibrated`]: relative to each row), and pivots of
344    /// the wrong sign or of magnitude at most `τ = 10⁻¹³` bumped to
345    /// `±β = ±2·10⁻⁷`. `ρδ = 10⁻¹⁴`, about 50 units of roundoff, keeps the
346    /// regularized augmented matrix numerically quasi-definite; `δ`
347    /// alone, small, is what the normal equations see (Chapter 5.14,
348    /// "Choosing the regularization", measured in L1.5b). `τ`, `β` are of
349    /// the order of the defaults of current interior-point codes
350    /// (Clarabel's documented dynamic regularization; not tuned here).
351    fn default() -> Self {
352        Self {
353            primal: T::from_f64(1e-6),
354            dual: T::from_f64(1e-8),
355            pivot_tol: Some(T::from_f64(1e-13)),
356            bump: T::from_f64(2e-7),
357            scale: ShiftScale::Equilibrated,
358        }
359    }
360}
361
362impl<T: Real> Regularization<T> {
363    /// No regularization at all: `ρ = δ = 0`, no bumping (the factorization
364    /// then fails on a zero pivot, or with the wrong inertia).
365    #[must_use]
366    pub fn none() -> Self {
367        Self {
368            primal: T::ZERO,
369            dual: T::ZERO,
370            pivot_tol: None,
371            bump: T::ZERO,
372            scale: ShiftScale::Equilibrated,
373        }
374    }
375
376    /// Absolute static shifts relative to the largest entry of `k`:
377    /// `ρ = δ = factor · max|k_ij|` with [`ShiftScale::Absolute`], and the
378    /// dynamic part of [`Regularization::default`] (the L1.5 variant).
379    ///
380    /// One shift for the whole matrix: at the end of an interior-point
381    /// method, where `max|k_ij| ≈ 10^{10}`, `factor = 10⁻⁸` gives
382    /// `δ ≈ 10²`, a large perturbation of the rows of small magnitude —
383    /// refinement against the unregularized `K` then converges slowly
384    /// (Chapter 5.14, "Choosing the regularization"). The default
385    /// ([`ShiftScale::Equilibrated`]) is relative row by row instead.
386    #[must_use]
387    pub fn relative_to(k: &CscMatrix<T>, factor: T) -> Self {
388        let big = inf_norm(&k.val);
389        Self {
390            primal: factor * big,
391            dual: factor * big,
392            scale: ShiftScale::Absolute,
393            ..Self::default()
394        }
395    }
396
397    /// `ρ > 0` and `δ > 0`: the regularized augmented matrix is
398    /// quasi-definite (it factorizes without pivoting, in any order).
399    pub fn is_quasi_definite(&self) -> bool {
400        lt(T::ZERO, self.primal) && lt(T::ZERO, self.dual)
401    }
402}
403
404/// Iterative refinement parameters (Algorithm F).
405#[derive(Clone, Copy, Debug, PartialEq)]
406pub struct Refinement<T: Real = f64> {
407    /// Refinement steps after the first solve.
408    pub max_iters: usize,
409    /// Stop when `‖K x − b‖_∞ / (1 + ‖b‖_∞)` is at or below this.
410    pub target_residual: T,
411}
412
413impl<T: Real> Default for Refinement<T> {
414    /// Ten steps, target `10⁻¹²`.
415    fn default() -> Self {
416        Self {
417            max_iters: 10,
418            target_residual: T::from_f64(1e-12),
419        }
420    }
421}
422
423/// What refinement achieved (S7).
424#[derive(Clone, Copy, Debug, PartialEq)]
425pub struct RefineReport<T: Real = f64> {
426    /// Refinement steps taken (solves after the first).
427    pub iters: usize,
428    /// `‖K x − b‖_∞ / (1 + ‖b‖_∞)` of the returned `x`.
429    pub residual: T,
430    /// `residual ≤ target_residual`.
431    pub converged: bool,
432}
433
434/// Which system the interior-point method hands over.
435#[derive(Clone, Copy, Debug, PartialEq, Eq)]
436pub enum KktForm {
437    /// `A D Aᵀ + δI`, positive definite.
438    NormalEquations,
439    /// `[−D − ρI, Aᵀ; A, δI]`, quasi-definite; the `n_primal` primal rows
440    /// come first.
441    Augmented {
442        /// `n`, the order of the `(1,1)` block.
443        n_primal: usize,
444        /// `m`, the order of the `(2,2)` block.
445        n_dual: usize,
446    },
447}
448
449impl KktForm {
450    /// The inertia (S6) requires of a factor of order `n`.
451    pub fn expected_inertia(self, n: usize) -> Inertia {
452        match self {
453            Self::NormalEquations => Inertia {
454                positive: n,
455                negative: 0,
456                zero: 0,
457            },
458            Self::Augmented { n_primal, n_dual } => Inertia {
459                positive: n_dual,
460                negative: n_primal,
461                zero: 0,
462            },
463        }
464    }
465}
466
467/// Analyze/factorize/solve of symmetric systems with a fixed pattern (the
468/// CHOLMOD shape, read, not copied). Regularization (its policy,
469/// Algorithm K) and refinement (Algorithm F) are shared by every backend.
470///
471/// ```
472/// use xingo_sparse::{
473///     Amd, Col, CscMatrix, KktForm, KktSolver, Refinement, Regularization, Row, SupernodalLdl,
474/// };
475/// // K = [−D, Aᵀ; A, 0] with D = diag(1, 2), A = [1 1]: lower triangle.
476/// let k = CscMatrix::from_triplets(3, 3, &[
477///     (Row(0), Col(0), -1.0), (Row(2), Col(0), 1.0),
478///     (Row(1), Col(1), -2.0), (Row(2), Col(1), 1.0),
479/// ])
480/// .unwrap();
481/// let form = KktForm::Augmented { n_primal: 2, n_dual: 1 };
482/// let solver = SupernodalLdl::<f64>::default(); // recommended; FaerLdl is the alternative
483/// let sym = solver.analyze(&k.pattern(), form, &Amd::default()).unwrap();
484/// let (num, inertia) = solver.factorize(&sym, &k, Regularization::default()).unwrap();
485/// assert_eq!(inertia, form.expected_inertia(3)); // (S6): 1 positive, 2 negative
486/// let b = [1.0, 0.0, 3.0];
487/// let mut x = [0.0; 3];
488/// let report = solver.solve_refined(&num, &k, &b, &mut x, Refinement::default());
489/// assert!(report.converged && report.residual <= 1e-12);
490/// ```
491pub trait KktSolver<T: Real> {
492    /// The result of the symbolic phase.
493    type Symbolic;
494    /// The result of the numeric phase.
495    type Numeric;
496
497    /// Symbolic phase on the lower triangle of `pattern` (plus a full
498    /// diagonal) with the given ordering; done once per pattern.
499    fn analyze(
500        &self,
501        pattern: &Pattern,
502        form: KktForm,
503        ordering: &dyn Ordering,
504    ) -> Result<Self::Symbolic, KktError>;
505
506    /// Numeric phase on the lower triangle of `k` (inside the analyzed
507    /// pattern) with regularization (Algorithm K); returns the factor and
508    /// its inertia (S6).
509    fn factorize(
510        &self,
511        symbolic: &Self::Symbolic,
512        k: &CscMatrix<T>,
513        reg: Regularization<T>,
514    ) -> Result<(Self::Numeric, Inertia), KktError>;
515
516    /// `x ← F⁻¹ x` in place, dense, with `F` the regularized factor.
517    ///
518    /// # Panics
519    /// If `x.len()` is not the order of the factor.
520    fn solve(&self, numeric: &Self::Numeric, x: &mut [T]);
521
522    /// Solve followed by iterative refinement against `k` (Algorithm F);
523    /// keeps the best iterate (S7). `k` is the matrix to be solved — the
524    /// unregularized one the factor approximates, or any other with the
525    /// same order; only its lower triangle is read. `x` is overwritten.
526    /// Allocates its work vectors; [`KktSolver::solve_refined_with`]
527    /// reuses them.
528    ///
529    /// # Panics
530    /// If `b`, `x` and `k` do not have the order of the factor.
531    fn solve_refined(
532        &self,
533        numeric: &Self::Numeric,
534        k: &CscMatrix<T>,
535        b: &[T],
536        x: &mut [T],
537        refinement: Refinement<T>,
538    ) -> RefineReport<T> {
539        let mut work = RefineWorkspace::new();
540        self.solve_refined_with(numeric, k, b, x, refinement, &mut work)
541    }
542
543    /// [`KktSolver::solve_refined`] with caller-owned work vectors: once
544    /// `work` has served a call with the same order and budget, the
545    /// refinement allocates nothing.
546    ///
547    /// # Panics
548    /// If `b`, `x` and `k` do not have the order of the factor.
549    #[allow(clippy::too_many_lines)] // one step of Algorithm F per block, as in the chapter
550    fn solve_refined_with(
551        &self,
552        numeric: &Self::Numeric,
553        k: &CscMatrix<T>,
554        b: &[T],
555        x: &mut [T],
556        refinement: Refinement<T>,
557        work: &mut RefineWorkspace<T>,
558    ) -> RefineReport<T> {
559        let n = b.len();
560        assert_eq!(x.len(), n, "solve_refined: x has the wrong length");
561        assert!(
562            k.n_rows == n && k.n_cols() == n,
563            "solve_refined: k has the wrong order"
564        );
565        let budget = refinement.max_iters;
566        work.reserve(n, budget);
567        let scale = T::ONE + inf_norm(b);
568        let tol = refinement.target_residual * scale;
569        // F1.
570        x.copy_from_slice(b);
571        self.solve(numeric, x);
572        let RefineWorkspace {
573            r,
574            cur,
575            v,
576            z,
577            h,
578            g,
579            cs,
580            sn,
581            y,
582        } = work;
583        residual(k, x, b, r);
584        let first = inf_norm(r) / scale;
585        let mut best = first;
586        let mut t = 0;
587        // `r` holds b − K x* at the top of every cycle.
588        loop {
589            // F2.
590            if !best.is_finite() || le(best, refinement.target_residual, T::ZERO) || t >= budget {
591                break;
592            }
593            // F3.
594            let m = budget - t;
595            let beta = norm2(r);
596            if !beta.is_finite() || is_exact_zero(beta) {
597                break;
598            }
599            for (vi, &ri) in v[..n].iter_mut().zip(r.iter()) {
600                *vi = ri / beta;
601            }
602            g.fill(T::ZERO);
603            g[0] = beta;
604            let mut steps = 0;
605            for j in 0..m {
606                let (zj, vj) = (&mut z[j * n..(j + 1) * n], &v[j * n..(j + 1) * n]);
607                zj.copy_from_slice(vj);
608                self.solve(numeric, zj);
609                t += 1;
610                steps = j + 1;
611                let (done, rest) = v.split_at_mut((j + 1) * n);
612                let w = &mut rest[..n];
613                sym_lower_matvec(k, &z[j * n..(j + 1) * n], w);
614                // Column j of H, (m + 1) rows, column-major.
615                let col = &mut h[j * (m + 1)..(j + 1) * (m + 1)];
616                for i in 0..=j {
617                    let vi = &done[i * n..(i + 1) * n];
618                    let hij = dot(w, vi);
619                    col[i] = hij;
620                    for (wk, &vk) in w.iter_mut().zip(vi) {
621                        *wk -= hij * vk;
622                    }
623                }
624                let hnext = norm2(w);
625                col[j + 1] = hnext;
626                if !hnext.is_finite() {
627                    steps = j;
628                    break;
629                }
630                // Previous rotations on column j.
631                for i in 0..j {
632                    let (a, c) = (col[i], col[i + 1]);
633                    col[i] = cs[i] * a + sn[i] * c;
634                    col[i + 1] = cs[i] * c - sn[i] * a;
635                }
636                // New rotation annihilating h_{j+1,j}.
637                let (a, c) = (col[j], col[j + 1]);
638                let rr = norm2(&[a, c]);
639                if is_exact_zero(rr) {
640                    // R singular in this column: drop the step.
641                    steps = j;
642                    break;
643                }
644                cs[j] = a / rr;
645                sn[j] = c / rr;
646                col[j] = rr;
647                col[j + 1] = T::ZERO;
648                g[j + 1] = -sn[j] * g[j];
649                g[j] *= cs[j];
650                if is_exact_zero(hnext) || le(g[j + 1].abs(), tol, T::ZERO) {
651                    break;
652                }
653                for wk in w.iter_mut() {
654                    *wk = *wk / hnext;
655                }
656            }
657            if steps == 0 {
658                break;
659            }
660            // F4: back substitution R y = g.
661            for i in (0..steps).rev() {
662                let mut acc = g[i];
663                for l in i + 1..steps {
664                    acc -= h[l * (m + 1) + i] * y[l];
665                }
666                y[i] = acc / h[i * (m + 1) + i];
667            }
668            cur.copy_from_slice(x);
669            for (l, &yl) in y[..steps].iter().enumerate() {
670                for (c, &zl) in cur.iter_mut().zip(&z[l * n..(l + 1) * n]) {
671                    *c += yl * zl;
672                }
673            }
674            residual(k, cur, b, r);
675            let res = inf_norm(r) / scale;
676            if res.is_finite() && lt(res, best) {
677                // `r` is the residual of the new x*.
678                x.copy_from_slice(cur);
679                best = res;
680            } else {
681                // F5 would restart from the same x*, whose cycle is the
682                // one just done (deterministic): stop.
683                break;
684            }
685        }
686        // F6.
687        debug_assert!(
688            !best.is_finite() || !first.is_finite() || le(best, first, T::ZERO),
689            "(S7): the returned residual exceeds the first one"
690        );
691        RefineReport {
692            iters: t,
693            residual: best,
694            converged: best.is_finite() && le(best, refinement.target_residual, T::ZERO),
695        }
696    }
697
698    /// Nonzeros of the factor (for the IPM log).
699    fn nnz_factor(&self, numeric: &Self::Numeric) -> usize;
700
701    /// A short name for logs and tables.
702    fn name(&self) -> &'static str;
703}
704
705/// `‖v‖_∞` (`0` for an empty vector; NaN if an entry is NaN — `max`
706/// alone would hide it).
707pub(crate) fn inf_norm<T: Real>(v: &[T]) -> T {
708    let mut m = T::ZERO;
709    for &x in v {
710        if is_nan(x) {
711            return x;
712        }
713        m = m.max(x.abs());
714    }
715    m
716}
717
718/// `‖v‖₂`, scaled against overflow (NaN propagates).
719fn norm2<T: Real>(v: &[T]) -> T {
720    let big = inf_norm(v);
721    if !big.is_finite() || is_exact_zero(big) {
722        return big;
723    }
724    let mut s = T::ZERO;
725    for &x in v {
726        let q = x / big;
727        s += q * q;
728    }
729    big * s.sqrt()
730}
731
732/// `⟨u, v⟩`.
733fn dot<T: Real>(u: &[T], v: &[T]) -> T {
734    let mut s = T::ZERO;
735    for (&a, &b) in u.iter().zip(v) {
736        s += a * b;
737    }
738    s
739}
740
741/// Work vectors of Algorithm F, reusable across calls of
742/// [`KktSolver::solve_refined_with`]: `(2m + 3) N + O(m²)` scalars for a
743/// budget of `m = max_iters` solves and order `N`. Grows on demand, never
744/// shrinks.
745#[derive(Clone, Debug, Default)]
746pub struct RefineWorkspace<T: Real = f64> {
747    r: Vec<T>,
748    cur: Vec<T>,
749    v: Vec<T>,
750    z: Vec<T>,
751    h: Vec<T>,
752    g: Vec<T>,
753    cs: Vec<T>,
754    sn: Vec<T>,
755    y: Vec<T>,
756}
757
758impl<T: Real> RefineWorkspace<T> {
759    /// An empty workspace (it grows at the first call).
760    #[must_use]
761    pub fn new() -> Self {
762        Self {
763            r: Vec::new(),
764            cur: Vec::new(),
765            v: Vec::new(),
766            z: Vec::new(),
767            h: Vec::new(),
768            g: Vec::new(),
769            cs: Vec::new(),
770            sn: Vec::new(),
771            y: Vec::new(),
772        }
773    }
774
775    /// Sizes the vectors for order `n` and budget `m` (allocates only when
776    /// they grow).
777    fn reserve(&mut self, n: usize, m: usize) {
778        fn fit<T: Real>(v: &mut Vec<T>, len: usize) {
779            if v.len() != len {
780                v.resize(len, T::ZERO);
781            }
782        }
783        fit(&mut self.r, n);
784        fit(&mut self.cur, n);
785        fit(&mut self.v, (m + 1) * n);
786        fit(&mut self.z, m * n);
787        fit(&mut self.h, (m + 1) * m);
788        fit(&mut self.g, m + 1);
789        fit(&mut self.cs, m);
790        fit(&mut self.sn, m);
791        fit(&mut self.y, m);
792    }
793}
794
795/// `y ← K x` with `K` given by the lower triangle of `k` (entries above
796/// the diagonal ignored).
797pub(crate) fn sym_lower_matvec<T: Real>(k: &CscMatrix<T>, x: &[T], y: &mut [T]) {
798    y.fill(T::ZERO);
799    for (j, &xj) in x.iter().enumerate() {
800        for p in k.col_ptr[j]..k.col_ptr[j + 1] {
801            let i = k.row_idx[p] as usize;
802            if i < j {
803                continue;
804            }
805            let v = k.val[p];
806            y[i] += v * xj;
807            if i != j {
808                y[j] += v * x[i];
809            }
810        }
811    }
812}
813
814/// `r ← b − K x` (lower triangle of `k`).
815fn residual<T: Real>(k: &CscMatrix<T>, x: &[T], b: &[T], r: &mut [T]) {
816    sym_lower_matvec(k, x, r);
817    for (ri, &bi) in r.iter_mut().zip(b) {
818        *ri = bi - *ri;
819    }
820}
821
822/// The lower triangle of a symmetric pattern plus a full diagonal, as the
823/// symbolic phase of every backend consumes it (step K1 for the pattern,
824/// invariant (K1)). The order `N` is checked against the form.
825pub(crate) fn lower_with_diagonal(pattern: &Pattern, form: KktForm) -> Result<Pattern, KktError> {
826    pattern.check_invariants()?;
827    let n = pattern.n_cols();
828    if pattern.n_rows != n {
829        return Err(KktError::NotSymmetric);
830    }
831    if let KktForm::Augmented { n_primal, n_dual } = form
832        && n_primal + n_dual != n
833    {
834        return Err(KktError::Structure(SparseError::Dimension {
835            what: "KKT order (n_primal + n_dual)",
836            expected: n_primal + n_dual,
837            found: n,
838        }));
839    }
840    let has_upper = (0..n).any(|j| pattern.col(j).first().is_some_and(|&i| (i as usize) < j));
841    if has_upper && pattern.transpose() != *pattern {
842        return Err(KktError::NotSymmetric);
843    }
844    let mut col_ptr = Vec::with_capacity(n + 1);
845    let mut row_idx = Vec::with_capacity(pattern.nnz() / 2 + n);
846    col_ptr.push(0);
847    for j in 0..n {
848        let rows = pattern.col(j);
849        let start = rows.partition_point(|&i| (i as usize) < j);
850        let below = &rows[start..];
851        if below.first() != Some(&crate::perm::idx32(j)) {
852            row_idx.push(crate::perm::idx32(j));
853        }
854        row_idx.extend_from_slice(below);
855        col_ptr.push(row_idx.len());
856    }
857    let l = Pattern {
858        n_rows: n,
859        col_ptr,
860        row_idx,
861    };
862    debug_assert_eq!(l.check_invariants(), Ok(()));
863    Ok(l)
864}
865
866/// The regularization is usable: `ρ, δ, β ≥ 0` finite, and with dynamic
867/// regularization `τ > 0` and `β > 0`.
868pub(crate) fn check_regularization<T: Real>(reg: &Regularization<T>) -> Result<(), KktError> {
869    for (what, x) in [
870        ("primal regularization", reg.primal),
871        ("dual regularization", reg.dual),
872        ("bump", reg.bump),
873    ] {
874        if !x.is_finite() || lt(x, T::ZERO) {
875            return Err(KktError::Structure(SparseError::InvalidValue {
876                what,
877                index: 0,
878                value: x.to_f64(),
879            }));
880        }
881    }
882    if let Some(tau) = reg.pivot_tol
883        && (!tau.is_finite() || !lt(T::ZERO, tau) || !lt(T::ZERO, reg.bump))
884    {
885        return Err(KktError::Structure(SparseError::InvalidValue {
886            what: "pivot_tol and bump (both must be positive)",
887            index: 0,
888            value: tau.to_f64(),
889        }));
890    }
891    Ok(())
892}
893
894/// The pivot signs `σ_k` of step K3: `−1` on the primal rows, `+1` on the
895/// dual rows (all `+1` for the normal equations).
896pub(crate) fn pivot_signs(form: KktForm, n: usize) -> Vec<i8> {
897    match form {
898        KktForm::NormalEquations => vec![1; n],
899        KktForm::Augmented { n_primal, .. } => {
900            (0..n).map(|k| if k < n_primal { -1 } else { 1 }).collect()
901        }
902    }
903}
904
905/// Steps K1′–K2″: scatters the lower triangle of `k` into the values of
906/// the analyzed lower pattern `l` (which has a full diagonal), equilibrates
907/// it (K2′) and adds the static shifts (K2″); returns the values of
908/// `K̃_reg` and the scaling `s`. Fails (K1, K1′) if `k` does not satisfy
909/// (S1), has the wrong order, has a lower entry outside `l`, or a
910/// non-finite lower entry.
911pub(crate) fn assemble_regularized<T: Real>(
912    l: &Pattern,
913    form: KktForm,
914    k: &CscMatrix<T>,
915    reg: &Regularization<T>,
916) -> Result<(Vec<T>, Vec<T>), KktError> {
917    let mut val = assemble(l, k)?;
918    let s = equilibrate_symmetric(l, &mut val);
919    for (j, &sj) in s.iter().enumerate() {
920        let shift = match form {
921            KktForm::NormalEquations => reg.dual,
922            KktForm::Augmented { n_primal, .. } => {
923                if j < n_primal {
924                    -reg.primal
925                } else {
926                    reg.dual
927                }
928            }
929        };
930        if !is_exact_zero(shift) {
931            // The diagonal is the first entry of column j of l.
932            let p = l.col_ptr[j];
933            val[p] += match reg.scale {
934                ShiftScale::Equilibrated => shift,
935                ShiftScale::Absolute => shift * sj * sj,
936            };
937        }
938    }
939    Ok((val, s))
940}
941
942/// Steps K1′–K2: the lower triangle of `k` on the analyzed pattern `l`.
943fn assemble<T: Real>(l: &Pattern, k: &CscMatrix<T>) -> Result<Vec<T>, KktError> {
944    k.check_invariants()?;
945    let n = l.n_cols();
946    if k.n_rows != n || k.n_cols() != n {
947        return Err(KktError::Structure(SparseError::Dimension {
948            what: "KKT matrix order (as analyzed)",
949            expected: n,
950            found: k.n_rows.max(k.n_cols()),
951        }));
952    }
953    let mut val = vec![T::ZERO; l.nnz()];
954    for j in 0..n {
955        let lrows = l.col(j);
956        let base = l.col_ptr[j];
957        let mut q = 0;
958        for p in k.col_ptr[j]..k.col_ptr[j + 1] {
959            let i = k.row_idx[p];
960            if (i as usize) < j {
961                continue;
962            }
963            // Both lists are increasing: a merge.
964            while q < lrows.len() && lrows[q] < i {
965                q += 1;
966            }
967            if q == lrows.len() || lrows[q] != i {
968                return Err(KktError::Structure(SparseError::Malformed(format!(
969                    "KKT entry ({i}, {j}) is outside the analyzed pattern"
970                ))));
971            }
972            // K1′.
973            if !k.val[p].is_finite() {
974                return Err(KktError::Structure(SparseError::InvalidValue {
975                    what: "KKT matrix entry (not finite)",
976                    index: p,
977                    value: k.val[p].to_f64(),
978                }));
979            }
980            val[base + q] = k.val[p];
981        }
982        // The diagonal is the first entry of column j of l.
983        debug_assert_eq!(lrows[0] as usize, j);
984    }
985    Ok(val)
986}
987
988/// Step K4 over a list of `1×1` pivots and `2×2` blocks `(a, b, c)` =
989/// `[a b; b c]`: the inertia by Sylvester's law.
990pub(crate) fn count_inertia<T: Real>(
991    ones: impl Iterator<Item = T>,
992    twos: impl Iterator<Item = (T, T, T)>,
993) -> Inertia {
994    let mut s = Inertia::default();
995    let mut one = |d: T| {
996        if lt(T::ZERO, d) {
997            s.positive += 1;
998        } else if lt(d, T::ZERO) {
999            s.negative += 1;
1000        } else {
1001            s.zero += 1;
1002        }
1003    };
1004    for d in ones {
1005        one(d);
1006    }
1007    for (a, b, c) in twos {
1008        // det < 0: one eigenvalue of each sign; det > 0: both of the sign
1009        // of the trace; det = 0: one zero, the other of the sign of the
1010        // trace.
1011        let det = a * c - b * b;
1012        if lt(det, T::ZERO) {
1013            one(T::ONE);
1014            one(-T::ONE);
1015        } else if lt(T::ZERO, det) {
1016            one(a + c);
1017            one(a + c);
1018        } else {
1019            one(T::ZERO);
1020            one(a + c);
1021        }
1022    }
1023    s
1024}
1025
1026/// Most passes of the symmetric equilibration (step K2′). A cap, not a
1027/// threshold: with power-of-two factors the iteration stops by itself
1028/// when no factor changes, which happens after a few passes in practice
1029/// (Ruiz 2001 reports convergence of the infinity-norm iteration to
1030/// within a factor 2 in a handful of steps).
1031pub const EQUILIBRATION_PASSES: usize = 20;
1032
1033/// Step K2′: symmetric equilibration of the lower pattern `l` with values
1034/// `val` (full diagonal present), in place; returns `s` (powers of two).
1035pub(crate) fn equilibrate_symmetric<T: Real>(l: &Pattern, val: &mut [T]) -> Vec<T> {
1036    let n = l.n_cols();
1037    let mut s = vec![T::ONE; n];
1038    let mut rmax = vec![T::ZERO; n];
1039    let mut step = vec![T::ONE; n];
1040    for _ in 0..EQUILIBRATION_PASSES {
1041        rmax.fill(T::ZERO);
1042        for j in 0..n {
1043            let range = l.col_ptr[j]..l.col_ptr[j + 1];
1044            for (&i, &x) in l.row_idx[range.clone()].iter().zip(&val[range]) {
1045                let i = i as usize;
1046                let v = x.abs();
1047                rmax[i] = rmax[i].max(v);
1048                rmax[j] = rmax[j].max(v);
1049            }
1050        }
1051        let mut changed = false;
1052        for i in 0..n {
1053            step[i] = if rmax[i].is_finite() && lt(T::ZERO, rmax[i]) {
1054                pow2_round(rmax[i].sqrt().recip())
1055            } else {
1056                T::ONE
1057            };
1058            changed |= !is_exact_zero(step[i] - T::ONE);
1059        }
1060        if !changed {
1061            break;
1062        }
1063        for j in 0..n {
1064            let range = l.col_ptr[j]..l.col_ptr[j + 1];
1065            for (&i, x) in l.row_idx[range.clone()].iter().zip(&mut val[range]) {
1066                *x = *x * step[i as usize] * step[j];
1067            }
1068        }
1069        for (si, &t) in s.iter_mut().zip(&step) {
1070            *si *= t;
1071        }
1072    }
1073    s
1074}
1075
1076/// `⌊x⌉₂ = 2^{round(log₂ x)}` for a finite `x > 0`, computed in `f64`
1077/// (a power of two is exact in every `Real`).
1078fn pow2_round<T: Real>(x: T) -> T {
1079    T::from_f64(x.to_f64().log2().round().exp2())
1080}
1081
1082/// Step K4: the (S6) check.
1083pub(crate) fn check_inertia(found: Inertia, expected: Inertia) -> Result<Inertia, KktError> {
1084    if found == expected {
1085        Ok(found)
1086    } else {
1087        Err(KktError::WrongInertia { found, expected })
1088    }
1089}
1090
1091#[cfg(test)]
1092// Exact equality is the property under test here (the assembly and the
1093// scaling are products and sums of powers of two, bit for bit); clippy 1.90
1094// flags it, 1.99 does not.
1095#[allow(clippy::float_cmp)]
1096mod tests {
1097    use super::*;
1098    use crate::{Col, Row};
1099
1100    #[test]
1101    fn lower_with_diagonal_accepts_lower_and_symmetric_patterns() {
1102        let lower = CscMatrix::from_triplets(3, 3, &[(Row(2), Col(0), 1.0), (Row(1), Col(1), 2.0)])
1103            .unwrap();
1104        let l = lower_with_diagonal(&lower.pattern(), KktForm::NormalEquations).unwrap();
1105        assert_eq!(l.col_ptr, vec![0, 2, 3, 4]);
1106        assert_eq!(l.row_idx, vec![0, 2, 1, 2]);
1107        let full = CscMatrix::from_triplets(3, 3, &[(Row(2), Col(0), 1.0), (Row(0), Col(2), 1.0)])
1108            .unwrap();
1109        assert_eq!(
1110            lower_with_diagonal(&full.pattern(), KktForm::NormalEquations).unwrap(),
1111            l.clone()
1112        );
1113        let skew = CscMatrix::from_triplets(3, 3, &[(Row(2), Col(0), 1.0), (Row(0), Col(1), 1.0)])
1114            .unwrap();
1115        assert_eq!(
1116            lower_with_diagonal(&skew.pattern(), KktForm::NormalEquations),
1117            Err(KktError::NotSymmetric)
1118        );
1119        let rect = CscMatrix::<f64>::zeros(2, 3);
1120        assert_eq!(
1121            lower_with_diagonal(&rect.pattern(), KktForm::NormalEquations),
1122            Err(KktError::NotSymmetric)
1123        );
1124        assert!(matches!(
1125            lower_with_diagonal(
1126                &lower.pattern(),
1127                KktForm::Augmented {
1128                    n_primal: 1,
1129                    n_dual: 1
1130                }
1131            ),
1132            Err(KktError::Structure(_))
1133        ));
1134    }
1135
1136    #[test]
1137    fn inertia_counts_follow_sylvester() {
1138        let s = count_inertia(
1139            [1.0, -2.0, 0.0].into_iter(),
1140            [(0.0, 1.0, 0.0), (2.0, 1.0, 3.0), (-1.0, 0.5, -1.0)].into_iter(),
1141        );
1142        assert_eq!(
1143            s,
1144            Inertia {
1145                positive: 4,
1146                negative: 4,
1147                zero: 1
1148            }
1149        );
1150        let expected = KktForm::Augmented {
1151            n_primal: 2,
1152            n_dual: 3,
1153        }
1154        .expected_inertia(5);
1155        assert_eq!(expected.positive, 3);
1156        assert_eq!(expected.negative, 2);
1157        assert!(check_inertia(s, expected).is_err());
1158    }
1159
1160    #[test]
1161    fn assembly_adds_the_shifts_and_rejects_foreign_entries() {
1162        let k = CscMatrix::from_triplets(
1163            3,
1164            3,
1165            &[
1166                (Row(0), Col(0), -1.0),
1167                (Row(2), Col(0), 1.0),
1168                (Row(1), Col(1), -2.0),
1169            ],
1170        )
1171        .unwrap();
1172        let form = KktForm::Augmented {
1173            n_primal: 2,
1174            n_dual: 1,
1175        };
1176        let l = lower_with_diagonal(&k.pattern(), form).unwrap();
1177        let mut reg = Regularization::<f64> {
1178            primal: 0.5,
1179            dual: 0.25,
1180            pivot_tol: None,
1181            bump: 0.0,
1182            scale: ShiftScale::Absolute,
1183        };
1184        // S⁻¹ K̃_reg S⁻¹ = K + Σ exactly (powers of two), whatever S.
1185        let unscale = |(v, s): (Vec<f64>, Vec<f64>)| -> Vec<f64> {
1186            let mut u = Vec::new();
1187            for j in 0..l.n_cols() {
1188                for p in l.col_ptr[j]..l.col_ptr[j + 1] {
1189                    u.push(v[p] / (s[l.row_idx[p] as usize] * s[j]));
1190                }
1191            }
1192            u
1193        };
1194        let v = assemble_regularized(&l, form, &k, &reg).unwrap();
1195        assert!(v.1.iter().all(|&x| x > 0.0 && x.log2().fract() == 0.0));
1196        assert_eq!(unscale(v), vec![-1.5, 1.0, -2.5, 0.25]);
1197        // Equilibrated: K + S⁻¹ Σ S⁻¹.
1198        reg.scale = ShiftScale::Equilibrated;
1199        let (v, s) = assemble_regularized(&l, form, &k, &reg).unwrap();
1200        let u = unscale((v, s.clone()));
1201        assert_eq!(u[0], -1.0 - 0.5 / (s[0] * s[0]));
1202        assert_eq!(u[1], 1.0);
1203        assert_eq!(u[2], -2.0 - 0.5 / (s[1] * s[1]));
1204        assert_eq!(u[3], 0.25 / (s[2] * s[2]));
1205        // A non-finite entry is refused (K1′).
1206        let mut nan = k.clone();
1207        nan.val[1] = f64::NAN;
1208        assert!(matches!(
1209            assemble_regularized(&l, form, &nan, &reg),
1210            Err(KktError::Structure(_))
1211        ));
1212        let other = CscMatrix::from_triplets(3, 3, &[(Row(2), Col(1), 1.0)]).unwrap();
1213        assert!(matches!(
1214            assemble_regularized(&l, form, &other, &reg),
1215            Err(KktError::Structure(_))
1216        ));
1217    }
1218
1219    #[test]
1220    fn symmetric_matvec_reads_the_lower_triangle_only() {
1221        let k = CscMatrix::from_triplets(
1222            2,
1223            2,
1224            &[
1225                (Row(0), Col(0), 2.0),
1226                (Row(1), Col(0), 3.0),
1227                (Row(0), Col(1), 99.0),
1228                (Row(1), Col(1), 4.0),
1229            ],
1230        )
1231        .unwrap();
1232        let mut y = [0.0; 2];
1233        sym_lower_matvec(&k, &[1.0, 1.0], &mut y);
1234        assert_eq!(y, [5.0, 7.0]);
1235    }
1236}