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, ®).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, ®).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, ®),
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, ®),
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}