Skip to main content

xingo_sparse/
supernodal.rs

1//! # Chapter 5.17 — `SupernodalLdl`: the own supernodal `LDLᵀ`
2//!
3//! *New with task L1.6a (PLAN.md trilha L; the contract's §5.7, decision
4//! D10 and D-0098). Part 1 (L1.6a): `1×1` pivots for the two regularized
5//! systems. Part 2 (L1.6b): Algorithm M, the `LBLᵀ` with Bunch–Kaufman
6//! `1×1`/`2×2` pivots inside each supernode and delayed pivots, for the
7//! unregularized augmented system.*
8//!
9//! ## Purpose
10//! [`SupernodalLdl`] implements [`KktSolver`] with no dependency: a
11//! supernodal `LDLᵀ` of `P K̃_reg Pᵀ` written here, generic in the scalar
12//! `T: Real`, with the dense arithmetic of its blocks delegated to a
13//! [`DenseKernel`] (`NaiveDense` always, `FaerDense` with the `faer`
14//! feature, Chapter 5.16). What it shares with every backend is the
15//! trait's: the ordering (any [`Ordering`], our [`crate::Amd`] by default),
16//! the regularization policy and the inertia check (Algorithm K of Chapter
17//! 5.14), the refinement (Algorithm F). What is new here is the symbolic
18//! phase (elimination tree, relaxed supernodes, the row pattern of every
19//! supernode and the scatter map of `K`), the numeric phase (left-looking
20//! supernodal elimination with the pivot bumping of step K3 and an exact
21//! count of the bumped pivots of both signs) and the solves, which allocate
22//! nothing.
23//!
24//! *Why left-looking.* CHOLMOD (Chen, Davis, Hager & Rajamanickam 2008,
25//! §2.3) and faer 0.24 (read, not copied) both factorize supernode by
26//! supernode in postorder, each one receiving the updates of its
27//! descendants before it is factorized ("left-looking"); the alternative,
28//! multifrontal, carries a stack of dense frontal matrices whose peak
29//! memory can exceed the factor's by a large factor on wide trees (Liu
30//! 1992), while left-looking needs only the factor and three scratch
31//! blocks. With the same supernodes the two do the same flops; the choice
32//! is memory and simplicity, and the CHOLMOD paper reports no systematic
33//! speed advantage of either on its test set.
34//!
35//! ## Notation
36//! As in Chapters 5.14–5.15: `K` of order `N` by its lower triangle, `L₀`
37//! the analyzed lower pattern with a full diagonal, `π` the ordering
38//! ([`Perm`], `fwd[k]` = the row eliminated `k`-th), `σ_k` the pivot signs,
39//! `(ρ, δ, τ, β)` the regularization, `K̃_reg = S K S + Σ` the equilibrated
40//! regularized matrix of step K2″ whose factor `P K̃_reg Pᵀ = L Δ Lᵀ` is
41//! computed, `L` unit lower triangular, `Δ = diag(d_k)`. Columns are in
42//! the *permuted* numbering `0..N` unless said otherwise. The elimination
43//! tree has `parent[j]` (Chapter 5.9, Algorithm E) and column counts `c_j`
44//! (entries of column `j` of `L`, diagonal included).
45//!
46//! A *supernode* `s` is a run of consecutive columns `[s₀, s₁)` whose
47//! columns of `L` have nested patterns: the pattern of column `j ∈ s`
48//! below the diagonal block is the same set `R_s` of `deg(s) = c_{s₁−1} − 1`
49//! rows, all `≥ s₁`. Its block of `L` is stored dense, column-major, as a
50//! [`DenseBlock`] of `nrows(s) = ncols(s) + deg(s)` rows and
51//! `ncols(s) = s₁ − s₀` columns: row `i < ncols(s)` is column `s₀ + i`,
52//! row `ncols(s) + q` is the row `R_s[q]`; the diagonal of the block holds
53//! `Δ` (the unit diagonal of `L` is implicit) and the strict upper triangle
54//! of the diagonal block is never read. A *fundamental* supernode has
55//! exactly nested patterns; a *relaxed* one merges a child into its parent
56//! at the price of explicit zeros (entries stored where the fundamental
57//! structure has none).
58//!
59//! ## Algorithm A (Analyze)
60//! A1. `L₀ ←` the lower triangle of the pattern plus a full diagonal
61//!     (invariant (K1) of Chapter 5.14; [`KktError::NotSymmetric`] or
62//!     [`KktError::Structure`] otherwise); `G ← L₀ + L₀ᵀ`.
63//! A2. `π ← ordering.order(G, Symmetric)` (its length checked).
64//! A2′. `π ←` the postorder of the elimination tree of `π` with the
65//!     heaviest child last (Algorithm P of Chapter 5.9): every subtree is
66//!     a run of consecutive columns, so every chain of only children is a
67//!     candidate supernode, and the largest child sits right before its
68//!     parent, where step A4 can merge it.
69//! A3. `(parent, c) ←` Algorithm E on `G` under `π` (the tree and the
70//!     column counts); `nchild[j]` the number of children of `j`.
71//! A3′. [Switch.] `φ = Σ_j c_j + Σ_j c_j(c_j+1)/2` (the divisions and
72//!     multiply-subtracts of the `LDLᵀ`) and `ℓ = Σ_j c_j`; if
73//!     `φ ≤ supernodal_switch · ℓ` ([`SupernodalOptions`], default 40 as
74//!     CHOLMOD's `supernodal_switch` and faer's `AUTO`) the matrix is
75//!     *simplicial*: A5 keeps the fundamental supernodes and Algorithm N
76//!     takes the simplicial path everywhere — on such matrices dense
77//!     blocks only add explicit zeros and copies (measured in L1.6a:
78//!     fit2p's augmented system, 16 525 columns in 13 500 supernodes,
79//!     factorized 2× slower with relaxed blocks than column by column).
80//! A4. [Fundamental supernodes.] Column `j` continues the supernode of
81//!     `j − 1` iff `parent[j − 1] = j`, `nchild[j] = 1` and
82//!     `c_{j−1} = c_j + 1` (Liu, Ng & Peyton 1993); otherwise it starts a
83//!     new one. Each fundamental supernode `f` has `size(f)` columns and
84//!     `deg(f) = c_{last} − 1`; its parent in the *supernodal* tree is the
85//!     supernode of `parent[last]`.
86//! A5. [Relaxed amalgamation.] Walk the fundamental supernodes in order,
87//!     keeping a *group* that starts as `{f}` and whose top is `f`. The
88//!     group (of `size` columns, top degree `deg(f)`, `zeros` explicit
89//!     zeros so far) is merged into `f + 1` when `f + 1` is the parent of
90//!     `f` — the only child adjacent to it, by A2′ — and the rule below
91//!     accepts; the group then continues with top `f + 1`. Otherwise the
92//!     group is closed as one supernode and a new group starts at `f + 1`.
93//!     Merging adds `z_new = size · (size(f+1) + deg(f+1) − deg(f))`
94//!     zeros (every column of the child gains the rows of the parent's
95//!     block it does not have; the child's pattern is contained in the
96//!     parent's columns and pattern, so the difference is never negative),
97//!     for a merged supernode of `w = size + size(f+1)` columns and
98//!     `e = w(w+1)/2 + deg(f+1) · w` stored entries in its lower part. With
99//!     `relax_zeros = r` ([`SupernodalOptions`]), the merge is accepted
100//!     iff `r > 0` and one of: `z_new = 0` (nothing is lost); `w ≤ r`
101//!     (small supernodes always merge: CHOLMOD's `nrelax[0]`, faer's
102//!     first cutoff); or `(zeros + z_new) / e ≤ ζ(w)` with
103//!     `ζ = 0.8` for `w ≤ 16`, `0.1` for `w ≤ 48`, `0.05` beyond
104//!     (CHOLMOD's `nrelax[1..]`/`zrelax` defaults, which faer uses too;
105//!     [`RELAX_CUTOFFS`], compared in integers). `r = 0` keeps the
106//!     fundamental supernodes. The rule is faer's (read, not copied), so
107//!     the stored factor of this chapter is the same size as faer's under
108//!     the same permutation — a stated acceptance criterion of L1.6a.
109//! A6. [Patterns.] For every supernode `s` in order, `R_s` is the union,
110//!     restricted to rows `≥ s₁`, of the rows of `G` in the columns of `s`
111//!     and of the patterns `R_c` of its children `c` in the supernodal
112//!     tree (the children come first in postorder); sorted increasing.
113//!     Invariant (L2): `|R_s| = c_{s₁−1} − 1`.
114//! A7. [Descendants.] For every supernode `d` and every maximal run of
115//!     consecutive rows `R_d[a..b)` that fall in the columns of one
116//!     supernode `s`, record `(d, a, b)` in the list of `s`: the updates
117//!     `s` receives in Algorithm N come from exactly these `d`, with
118//!     `R_d[a..b)` the columns of `s` they touch and `R_d[a..]` the rows.
119//! A8. [Scatter map.] For every entry `p` of `L₀` (original indices
120//!     `(i, j)`), the supernode of `min(inv[i], inv[j])` and the offset of
121//!     the permuted entry in its block: the numeric phase scatters the
122//!     values of `K̃_reg` with one indexed store each.
123//! A9. [Sizes.] `nnz_l = Σ_s nrows(s) · ncols(s)`, the stored length of
124//!     the factor (dense blocks, their explicit zeros and the unused strict
125//!     upper triangles of the diagonal blocks included — the convention of
126//!     [`crate::FaerSymbolic::nnz_factor`], (F2), so the two backends are
127//!     comparable). Invariant (L3): the lower parts of the blocks,
128//!     `Σ_s (ncols(s)(ncols(s)+1)/2 + deg(s) · ncols(s))`, equal `Σ_j c_j`
129//!     ([`Pattern::cholesky_nnz`]) plus the zeros counted in A5.
130//!
131//! ## Algorithm N (Numeric factorization, left-looking supernodal)
132//! N1. `v ←` the values of `K` on `L₀` (steps K1′–K2 of Chapter 5.14),
133//!     equilibrated (K2′), plus the static shifts (K2″): `v` holds `K̃_reg`.
134//! N2. Allocate the blocks of `L` (zeros) and scatter `v` into them by the
135//!     map of A8. The pivot signs in permuted order are `σ_{fwd[k]}`.
136//! N3. For `s = 0, 1, …` (postorder: every descendant before `s`):
137//!     N3a. [Map.] `loc[s₀ + i] ← i` for the columns of `s`,
138//!          `loc[R_s[q]] ← ncols(s) + q` for its pattern rows.
139//!     N3b. [Updates.] For every `(d, a, b)` in the list of `s` (A7),
140//!          Algorithm U: `L_s ← L_s − L_d[a.., :] Δ_d L_d[a..b, :]ᵀ` on the
141//!          rows and columns `loc` says, lower part only.
142//!     N3c. [Factor.] Algorithm D on the block of `s`: the diagonal block
143//!          `A₁₁ = L₁₁ Δ_s L₁₁ᵀ` with the bumping of step K3 under the
144//!          signs `σ` of its columns, then `L₂₁ ← A₂₁ L₁₁⁻ᵀ Δ_s⁻¹` for the
145//!          rows of `R_s`. A zero pivot without dynamic regularization is
146//!          [`KktError::ZeroPivot`] at the original row `fwd[k]`; a pivot
147//!          that is not finite is [`KktError::NotFinite`] there (an
148//!          overflow of the elimination is never bumped).
149//!     N3d. [Unmap.] Reset `loc` for the rows touched in N3a.
150//! N4. [Unscale.] The factor computed is that of `P K̃_reg Pᵀ`, `K̃ =
151//!     S K S`. Since `K_reg = S⁻¹ K̃_reg S⁻¹ = (S⁻¹ L S)(S⁻¹ Δ S⁻¹)(S⁻¹ L
152//!     S)ᵀ`, the stored blocks become `L̂ = S⁻¹ L S` (`l̂_ij = l_ij s_j /
153//!     s_i`, unit diagonal kept) and `Δ̂ = S⁻¹ Δ S⁻¹` (`d̂_k = d_k /
154//!     s_k²`) — exact, the scales being powers of two — so that the
155//!     solves work in the caller's units with no scaling pass (the
156//!     equilibration is kept, [`NumericLdl::scale`], to read the pivots
157//!     of the equilibrated matrix back: `d_k = d̂_k s_k²`).
158//! N5. (S10) Every stored value of `L̂` and `Δ̂` is finite, or the call
159//!     fails with [`KktError::NotFinite`] at the original row of the first
160//!     column holding a NaN or an infinity (step K3′).
161//! N6. (S6) The inertia is the count of signs of `Δ̂` (= of `Δ`, step K4;
162//!     [`KktError::WrongInertia`] unless it is the form's). With
163//!     `τ = Some`, every pivot has its sign `σ_k` by construction and the
164//!     check cannot fail. The factor also allocates its work vector for
165//!     Algorithm S (`N` scalars).
166//!
167//! A supernode with fewer than `min_supernode_cols` columns
168//! ([`SupernodalOptions`]) takes the *simplicial path*: steps N3b and N3c
169//! run column by column with plain loops (the same arithmetic, in the same
170//! order as the kernel path up to the rounding of the sums), and so does
171//! an update whose descendant `d` has fewer than `min_supernode_cols`
172//! columns — a dense kernel on a block one to seven columns wide costs
173//! more in copies than it saves. Above the threshold the kernel path
174//! gathers the operands into scratch blocks and calls `gemm_sub` and
175//! `trsm_lower` ([`DenseKernel`]). The storage is the same on both paths.
176//!
177//! ## Algorithm U (Update of `s` by a descendant `d`)
178//! With `R_d[a..b)` the rows of `d` inside the columns of `s`, `n_m = b − a`,
179//! `n_r = |R_d| − a` (the rows of `d` from `a` on: they lie in `s`'s
180//! columns or in `R_s`, by A6):
181//! U1. `A ← L_d[a.., :]` (`n_r × ncols(d)`), `B ← L_d[a..b, :] Δ_d`
182//!     (`n_m × ncols(d)`, the columns scaled by `d_k`), gathered into
183//!     scratch blocks (the rows of a column-major block are strided, and a
184//!     [`DenseBlock`] has no stride: the gather is the price of the
185//!     kernel interface).
186//! U2. `C ← 0` (`n_r × n_m`); `C ← C − A Bᵀ` by `gemm_sub`.
187//! U3. [Scatter.] For `j < n_m` and `i ≥ j`: `L_s[loc(R_d[a+i]),
188//!     R_d[a+j] − s₀] += c_ij` — the lower part of the update, since
189//!     `R_d` is sorted so that `i ≥ j` is row at or below column.
190//! Simplicial path: for `k < ncols(d)`, `j ∈ [a, b)`, `i ∈ [j, |R_d|)`:
191//! `L_s[loc(R_d[i]), R_d[j] − s₀] −= l_{d,ik} · (d_k l_{d,jk})`, column `k`
192//! of `L_d` read once, contiguous.
193//!
194//! ## Algorithm D (Dense `LDLᵀ` of a supernode block, with bumping)
195//! On the block `A` of `s` (`n_r` rows, `n_c` columns), panels of
196//! [`PANEL`] columns `[p, q)`:
197//! D1. [Tile.] Columns `p..q`, rows `p..q`, by the scalar right-looking
198//!     elimination: for `k = p, …, q − 1`: `d_k ← a_kk`; if `d_k` is not
199//!     finite, fail (N3c); if `τ = Some` and `σ_k d_k ≤ τ`, `d_k ← σ_k β`
200//!     and count the bump (step K3); if `τ = None` and `d_k = 0`, fail
201//!     (zero pivot); `l_ik ← a_ik / d_k` for `k < i < q`; `a_ij ← a_ij −
202//!     l_ik d_k l_jk` for `k < j ≤ i < q`.
203//! D2. [Panel below the tile.] If `q < n_r`: `L₂₁ ← A₂₁ L̃⁻ᵀ` with `L̃ =
204//!     L₁₁ Δ₁` (the unit lower tile with its columns scaled by the pivots:
205//!     lower triangular with diagonal `d_k`), by `trsm_lower(L̃, A₂₁,
206//!     transpose)`: row `i` of `A₂₁` solves `L̃ x = a_i`, i.e.
207//!     `l_ik = (a_ik − Σ_{j<k} l_ij d_j l_kj) / d_k` — the formula of D1
208//!     for the rows below the tile, with the sums in the kernel's order.
209//! D3. [Trailing update.] If `q < n_c`: for the remaining columns, in
210//!     panels `[c, c + w)`: `A[c.., c..c+w] ← A[c.., c..c+w] − W[c−q..,
211//!     :] L₂₁[c−q..c−q+w, :]ᵀ` with `W = L₂₁ Δ₁`, by `gemm_sub` on
212//!     gathered blocks — the lower trapezoid of the trailing matrix, one
213//!     panel at a time (the strict upper triangle of each `w × w` diagonal
214//!     tile is computed and discarded: `w² ncols` wasted flops per panel
215//!     against `n_r w ncols` useful ones).
216//! For `n_c ≤ PANEL` there is one tile and no trailing update: the whole
217//! supernode is D1 on its diagonal block and D2 for its pattern rows. The
218//! simplicial path runs D1 with `q = n_r` on all the rows and `n_c`
219//! columns (no panels, no kernel).
220//!
221//! ## Algorithm M (`LBLᵀ` of the unregularized augmented system)
222//! *Task L1.6b.* An augmented system without regularization (`ρ = 0` or
223//! `δ = 0`, and `τ = None`: the rule of Chapter 5.15, step N2) is
224//! indefinite but not quasi-definite: its dual diagonal is zero, so a dual
225//! column that is a leaf of the elimination tree has a pivot that is
226//! exactly zero, and a column whose rows depend on the pivots already
227//! taken inside its supernode has one that is zero up to rounding. The two
228//! regularized systems take Algorithm N as before (they are quasi-definite
229//! — Vanderbei 1995 — and need no pivoting; that path is untouched, bit
230//! for bit); the unregularized augmented one takes this algorithm, which
231//! replaces steps N3b–N3c and the solve.
232//!
233//! The pivoting is *intranodal* — the candidates for a pivot are the
234//! columns of the supernode being factorized, the "fully summed" variables
235//! of the multifrontal method, whose columns the block holds complete —
236//! and the search is Bunch–Kaufman's (Algorithm B of Chapter 5.16,
237//! [`DenseKernel::sytrf`]) on the diagonal block. A column that cannot be
238//! pivoted there is *delayed* to the parent supernode (Duff & Reid 1983;
239//! MA57, Duff 2004), where its remaining entries lie in any case ((L1):
240//! the pattern of a child is contained in the columns and the pattern of
241//! its parent), and tries again with more candidates; a column delayed
242//! out of a root is a zero pivot of a singular matrix,
243//! [`KktError::ZeroPivot`]. The structure of Algorithm A does not change:
244//! a delayed column adds one column and one row to the block of the
245//! parent (explicit zeros where it has no entry) and leaves its row of
246//! `L` behind in the block it came from.
247//!
248//! For `s = 0, 1, …` in postorder, with `nc` columns and `deg = |R_s|`:
249//! M1. [Receive.] The `nd` columns delayed into `s` by its children (step
250//!     M5) are appended to its columns: the block becomes
251//!     `(nc + nd + deg) × (nc + nd)`, the own entries keep their places
252//!     (the pattern rows move down by `nd`), and each delayed column `k`
253//!     brings its diagonal, its entries at the columns delayed after it by
254//!     the same block (cross terms) and its entries at the pattern rows of
255//!     that block, scattered by `loc`. A delayed column needs no update
256//!     from the descendants of `s`: it arrives with the updates of its own
257//!     subtree and of the pivots of the block that delayed it.
258//! M2. [Updates.] Step N3b with Algorithm U, where `B ← L_d[a..b, :] B_d`
259//!     has `B_d` block diagonal: for a `2×2` block `E = [e₁₁ e₂₁; e₂₁ e₂₂]`
260//!     at the columns `k, k+1` of `d`, `B[:, k] = e₁₁ l_k + e₂₁ l_{k+1}` and
261//!     `B[:, k+1] = e₂₁ l_k + e₂₂ l_{k+1}`; the rows of `d` are read past
262//!     its own delayed rows (M6). The largest update any descendant makes
263//!     to the diagonal of a column of `s` is kept as that column's
264//!     reference scale for M3.
265//! M3. [Pivot.] With `A₁₁` the diagonal block of the `w = nc + nd` active
266//!     columns: `P A₁₁ Pᵀ = L₁₁ B₁ L₁₁ᵀ` by `sytrf` on a copy. A `1×1`
267//!     pivot `d` with `|d| ≤ ζ m_j`, or a `2×2` block whose three entries
268//!     are all `≤ ζ max(m_j, m_{j'})` (`ζ` = [`SupernodalOptions::zero_pivot_tol`],
269//!     default `10⁻¹⁴`: a relative test, so that a pivot that is zero up to
270//!     the rounding of the sum that produced it is caught, and a pivot
271//!     that is merely small — the `10⁻¹⁰` of a primal column at the end
272//!     of an interior-point method — is kept, as in Algorithm N), is a
273//!     *zero pivot*: its columns are removed from the active set and M3 is
274//!     repeated on the rest (a zero column of the Schur complement
275//!     contributes nothing to the other pivots: the repetition only drops
276//!     it). `w = 1` is the direct case, `d = a₀₀` against the scale it
277//!     carries. Without a parent, a zero pivot is [`KktError::ZeroPivot`]
278//!     at the original row of its column: nothing is left to pair it with,
279//!     and the matrix is singular to working precision (measured on the
280//!     Netlib systems: taking such a pivot instead gave factors with the
281//!     expected inertia and residuals of `10¹⁵`, a silent failure); a pivot
282//!     that is not finite is [`KktError::NotFinite`] there. The reference scale `m_j`
283//!     is the largest term of the sums that produced the pivot — its
284//!     diagonal as the block holds it and the largest update a descendant
285//!     made to it (M2: a dual column coupled only to pairs below it
286//!     receives updates that cancel to rounding noise, and the noise
287//!     must not pass for a pivot); for a column delayed into
288//!     this block, the scale it was flagged with where it came from and
289//!     the terms of the Schur complement step M5 formed for it (a
290//!     carried diagonal that is already rounding noise must not be judged
291//!     against itself); and the terms `l_jk b_k l_jk` of the pivots `k`
292//!     before it in the block. Measured on the random systems of the
293//!     tests: without the carried scale a dual leaf whose diagonal arrived
294//!     as `3·10⁻¹⁶` was taken as a pivot and the factor was wrong by
295//!     `10⁻²`. The scale is a bound on the rounding noise of the sum, not
296//!     an uncertainty propagated through the pivots: a version that let a
297//!     pivot hand its own scale to what it updates compounded the scales
298//!     to `10⁶⁵` on stair (Netlib) and flagged a pivot of `1.27` as zero;
299//!     the one case that needed the propagation — a pivot of `5·10⁻¹⁹`
300//!     beside terms of `10⁻¹⁸`, the residue of a `2×2` block with one
301//!     noise diagonal — is caught by the growth test of M4 instead.
302//! M4. [Rows.] The rows below the diagonal block — the `nz` columns
303//!     removed in M3, as rows, then `R_s` — are gathered in the order of
304//!     `P` and solved: `U ← A₂₁ L₁₁⁻ᵀ` by `trsm_lower` against the unit
305//!     `L₁₁` (its diagonal written as ones, the slots of `e₂₁` as zeros),
306//!     then `L₂₁ ← U B₁⁻¹` column by column: `/ d` for a `1×1` pivot,
307//!     `[x y] E⁻¹` for a `2×2` one. [Growth.] A pivot whose column of
308//!     `L₂₁` has an entry above `1/u` (`u` =
309//!     [`SupernodalOptions::pivot_threshold`], default `10⁻⁸`) is removed
310//!     like a zero pivot and M3 repeats without it: the row of the large
311//!     entry is a candidate partner in the parent, where it is fully
312//!     summed — the threshold partial pivoting of MA57 among the fully
313//!     summed variables, with Ipopt's lax `u`. Without it a pivot small
314//!     inside its block but not zero (a `2×2` block with a small `e₂₁`,
315//!     stable by Bunch–Kaufman's test on the block alone) made `L₂₁` grow
316//!     to `10⁷` and every pivot below it rounding noise (ganges, Netlib:
317//!     a pivot of `0.70` with an error of `0.07`); `u = 10⁻²` (MA57's
318//!     default) delays so much in the middle of an interior-point method
319//!     that one Netlib system (woodw, augmented) did not finish in six
320//!     minutes, and `u = 10⁻⁴` sits in between (tables in the decision
321//!     log).
322//! M5. [Delay.] Each removed column `k` goes to the parent with its
323//!     reference scale — raised to `|a_kk|` and to the largest term of
324//!     `l_k · u_k`: the pivots the block took *after* `k` was flagged may
325//!     cancel in that sum (two singleton rows of `A` on one column: the
326//!     second, flagged with an exact zero and scale `0`, got `b² − (ab)²/a²
327//!     = 4·10⁻¹⁶` from the pivots of the first and was taken at the root
328//!     with the expected inertia; 0.3.1) —
329//!     and its Schur complement after the active pivots: `a_kk − l_k · u_k`, the cross
330//!     terms `a_{k'k} − l_{k'} · u_k` with the removed columns `k'` after
331//!     it, and `a_{rk} − l_r · u_k` for `r ∈ R_s` (`l` the rows of `L₂₁`,
332//!     `u` the rows of `U`: `l_r B₁ l_kᵀ = l_r · u_k`). Its row `l_k` stays
333//!     in the block of `s` for the solve.
334//! M6. [Record.] The block of `s` is `(w' + nz + deg) × w'` (`w' = w − nz`
335//!     pivots in the order of `P`, then the `nz` delayed rows, then
336//!     `R_s`): `L₁₁` with `B₁` on its diagonal and `e₂₁` at `(k+1, k)` —
337//!     the slot where `L` has an implicit zero, the convention of
338//!     [`DenseKernel::sytrf`] — and `L₂₁` below. The pivots take the next
339//!     `w'` positions of the *pivot order*: `fwd′`, `diag` and `pivot_2x2`
340//!     (`true` on both columns of a `2×2` block) are indexed by it, and
341//!     `pos[j]` records where the analyzed column `j` was eliminated.
342//! Then steps N4–N6 as before (`e₂₁` is an entry of `Δ`: `ê₂₁ = e₂₁ /
343//! (s_k s_{k+1})`; the inertia counts `+1 −1` for a `2×2` block with
344//! `det E < 0`, step K4), and the rows of every block are remapped by
345//! `pos` for the solve. [`NumericLdl::perm`] is `fwd′`,
346//! [`NumericLdl::supernodes`] the block boundaries in pivot order,
347//! [`NumericLdl::rows`] the rows of a block below its diagonal block,
348//! [`NumericLdl::delayed`] the number of delays.
349//!
350//! The simplicial structure takes the same steps: a supernode of one
351//! column is the direct case of M3, and its pivot is zero iff exactly
352//! zero — then it is delayed, never ignored (the simplicial `LBLᵀ` of faer
353//! accepts a zero pivot in silence and its solve returns infinities,
354//! D-0094; here the unregularized factorization of a nonsingular matrix
355//! either succeeds or fails with the row named). Why the leaf is not merged
356//! with its parent in the symbolic phase instead: the symbolic phase does
357//! not know the regularization, the regularized systems would pay the
358//! explicit zeros, and a leaf is adjacent to its parent only when it is
359//! the heaviest child; the numeric delay costs one row and one column of
360//! a block per delayed pivot, only when it happens.
361//!
362//! *Growth and the end of an interior-point method.* The threshold test
363//! of M4 delays every primal pivot below `u` relative to its column — near
364//! the end of the method, where `D` reaches `10⁻¹⁰`, that is half of them,
365//! and the delays pile up at the root (up to 15 352 in one Netlib system).
366//! There the unregularized augmented system is singular to working
367//! precision anyway (κ > 10¹² in 93 of 93 Netlib systems of the end
368//! regime, by the scipy oracle of L1.5), and the regularized path, which
369//! lives with the growth and whose refinement handles it (Chapter 5.14,
370//! L1.5b), is the one to use. The refinement of Algorithm F is the
371//! safeguard here too, and (S10) still refuses a factor with an infinity.
372//!
373//! ## Algorithm S (Solve)
374//! `y ← P x` gathered into the factor's work vector (`y_k = x_{fwd[k]}`;
375//! a second thread solving with the same factor at the same moment uses
376//! a temporary vector instead of waiting — the mutex of task L1.5b, D6;
377//! an in-place permutation by cycles was measured first and rejected:
378//! following a cycle is a chain of dependent loads, twice slower than the
379//! gather on the 16 525 unknowns of fit2p's augmented system). Then,
380//! supernode by supernode:
381//! S1. [Forward, `L̂ y = y`.] For `s` in order, for each column `j` of
382//!     `s`: `y_i ← y_i − l̂_ij y_j` for the rows `i` of the diagonal block
383//!     below `j` (a contiguous `axpy`) and for the rows `R_s` (a scatter;
384//!     column `j` of the block read once).
385//! S2. [Diagonal.] `y_k ← y_k / d̂_k`.
386//! S3. [Backward, `L̂ᵀ y = y`.] For `s` in reverse order and `j` from the
387//!     last column of `s` down: `y_j ← y_j − Σ_{i>j in s} l̂_ij y_i −
388//!     Σ_q l̂_{R_s[q], j} y_{R_s[q]}`: two dot products with the same
389//!     column, each summed in four independent partial sums (a single
390//!     accumulator makes the sweep latency-bound: 2× slower on maros-r7's
391//!     normal equations, measured in L1.6a) and combined in a fixed order.
392//! A supernode of one column takes the plain loops of a column-oriented
393//! simplicial solve. Finally `x_{fwd[k]} ← y_k`. Nothing is allocated
394//! while the work vector is free (invariant (L5)); the factor is read only.
395//!
396//! ## Algorithm S′ (Solve with the `LBLᵀ` factor)
397//! Algorithm S with: `y ← P′ x` by `fwd′`; the blocks walked by their
398//! pivot ranges and their remapped rows (delayed rows, then `R_s`); in S1
399//! and S3 the slot `(k+1, k)` of a `2×2` block is skipped (it holds
400//! `e₂₁`, not an entry of `L`); S2 runs block by block right after S1 (the
401//! pivots of a block are final once its forward step is done), and a
402//! `2×2` block solves `E [y_k; y_{k+1}] = [b_k; b_{k+1}]` by Cramer's rule.
403//! Nothing is allocated (L5); the pivot pairs never cross a block (L8).
404//!
405//! ## Invariants
406//! (L1) The supernodes partition `0..N` into runs in increasing order;
407//!      `R_s` is sorted, its rows are `≥ s₁`, and every row of `R_s` lies
408//!      in the columns of an ancestor of `s`.
409//! (L2) `|R_s| = c_{s₁−1} − 1` (the pattern of the last column, Liu 1990).
410//! (L3) `Σ_s (ncols(ncols+1)/2 + deg · ncols) = Σ_j c_j + zeros(A5)`:
411//!      the stored lower parts are the structural factor plus the counted
412//!      zeros of the relaxation; with `relax_zeros = 0`, exactly
413//!      [`Pattern::cholesky_nnz`].
414//! (L4) Every `(d, a, b)` of A7 has `d < s`, `R_d[a..b) ⊆ [s₀, s₁)` and
415//!      `R_d[b..] ⊆ R_s`.
416//! (L5) [`KktSolver::solve`] allocates nothing (its work vector belongs to
417//!      the factor) and reads the factor only.
418//! (L6) The factorization is a deterministic function of its inputs:
419//!      no threads, no hashing, the same operations in the same order —
420//!      two factorizations of the same matrix are equal bit for bit.
421//! (L7) In the `LBLᵀ` path the pivot ranges of the blocks partition `0..N`,
422//!      `fwd′` is a permutation, and every analyzed column is eliminated
423//!      exactly once (`pos` is a permutation of `0..N`).
424//! (L8) A `2×2` block lies inside one block of pivots (intranodal):
425//!      `pivot_2x2[k] = true` comes in pairs `(k, k+1)`, `k+1` in the same
426//!      block.
427//! (L9) A delayed column is received by the parent supernode of the block
428//!      that delayed it and nowhere else; its row of `L` stays in that
429//!      block.
430//! (S6), (S10) as in Chapter 5.14, checked in steps N4–N5 and asserted in
431//!      debug builds. [`SymbolicLdl::check_invariants`] checks (L1)–(L4);
432//!      the L1.6a harness checks (L5) with a counting allocator (0
433//!      allocations in a second solve and in a refined solve with a reused
434//!      workspace), the tests check (L6) by comparing two factors.
435//!
436//! ## What was read
437//! CHOLMOD (Chen, Davis, Hager & Rajamanickam 2008: §2.2 analyze, §2.3
438//! the supernodal left-looking numeric phase and its relaxed amalgamation
439//! parameters `nrelax`, `zrelax`); faer 0.24.4
440//! `sparse::linalg::cholesky::supernodal` (the fundamental-supernode test,
441//! the merge rule on adjacent children, the storage of a supernode as one
442//! column-major block with `Δ` on its diagonal, the per-supernode row
443//! structure that drives the left-looking updates) and `amd::postorder`;
444//! Liu, Ng & Peyton 1993 (supernodes), Ng & Peyton 1993 (left-looking
445//! supernodal), Liu 1992 (multifrontal memory) — read, not copied.
446//!
447//! For Algorithm M (L1.6b): Duff & Reid 1983 (delayed pivots in the
448//! multifrontal method), Duff 2004 (MA57: the threshold test among the
449//! fully summed variables, the treatment of delays), Vanderbei 1995
450//! (quasi-definite matrices factorize with `1×1` pivots in any order:
451//! why the regularized path needs none), faer 0.24.4
452//! `linalg::cholesky::bunch_kaufman::factor` (read to confirm that a
453//! column with no off-diagonal entry is taken as a `1×1` pivot without
454//! elimination, which is what M3 relies on from `sytrf`) — read, not
455//! copied.
456//!
457//! ## References
458//! See Chapter 5.14; Chen, Davis, Hager & Rajamanickam, "Algorithm 887:
459//! CHOLMOD", ACM TOMS 35(3), 2008; Liu, Ng & Peyton, "On finding
460//! supernodes for sparse matrix computations", SIAM J. Matrix Anal. Appl.
461//! 14(1), 1993; Ng & Peyton, "Block sparse Cholesky algorithms on advanced
462//! uniprocessor computers", SIAM J. Sci. Comput. 14(5), 1993; Liu, "The
463//! multifrontal method for sparse matrix solution: theory and practice",
464//! SIAM Review 34(1), 1992; Liu, "The role of elimination trees in sparse
465//! factorization", SIAM J. Matrix Anal. Appl. 11(1), 1990; Davis, *Direct
466//! Methods for Sparse Linear Systems* (2006), ch. 4; Ashcraft & Grimes,
467//! "The influence of relaxed supernode partitions on the multifrontal
468//! method", ACM TOMS 15(4), 1989 (relaxed amalgamation); Duff & Reid, "The
469//! multifrontal solution of indefinite sparse symmetric linear systems",
470//! ACM TOMS 9(3), 1983; Duff, "MA57 — a code for the solution of sparse
471//! symmetric definite and indefinite systems", ACM TOMS 30(2), 2004;
472//! Vanderbei, "Symmetric quasi-definite matrices", SIAM J. Optim. 5(1),
473//! 1995; Bunch & Kaufman, "Some stable methods for calculating inertia
474//! and solving symmetric linear systems", Math. Comp. 31, 1977.
475
476use core::marker::PhantomData;
477use std::sync::{Arc, Mutex};
478
479use crate::factor::count_f64;
480use crate::kkt::{
481    assemble_regularized, check_inertia, check_regularization, count_inertia, lower_with_diagonal,
482    pivot_signs,
483};
484use crate::perm::{etree_counts, idx32};
485use crate::real::{Real, is_exact_zero, le, le_exact, lt};
486use crate::{
487    CscMatrix, DenseBlock, DenseKernel, Inertia, KktError, KktForm, KktSolver, NaiveDense,
488    Ordering, OrderingTarget, Pattern, Perm, Regularization, SparseError,
489};
490
491/// "No node".
492const NONE: u32 = u32::MAX;
493
494/// Panel width of Algorithm D (a blocking size for the dense kernels, not
495/// a numerical threshold).
496pub const PANEL: usize = 32;
497
498/// Step A5: the largest fraction of explicit zeros a relaxed supernode of
499/// at most the given number of columns may hold, in per mille — CHOLMOD's
500/// `nrelax[1..3]`/`zrelax` defaults (`16: 0.8`, `48: 0.1`, else `0.05`),
501/// which faer 0.24 uses too. The first cutoff (always merge up to
502/// `relax_zeros` columns) is [`SupernodalOptions::relax_zeros`].
503pub const RELAX_CUTOFFS: [(usize, usize); 3] = [(16, 800), (48, 100), (usize::MAX, 50)];
504
505/// Options of the supernodal factorization (steps A5 and N3).
506#[derive(Clone, Copy, Debug, PartialEq)]
507pub struct SupernodalOptions {
508    /// Relaxed amalgamation (step A5): a child supernode is merged into
509    /// its parent whenever the merged supernode has at most this many
510    /// columns, and beyond that when the fraction of explicit zeros it
511    /// adds stays under CHOLMOD's cutoffs ([`RELAX_CUTOFFS`]); `0` keeps
512    /// the fundamental supernodes (no explicit zero). Default `4`
513    /// (CHOLMOD's `nrelax[0]`).
514    pub relax_zeros: usize,
515    /// Below this many columns a supernode is handled by the simplicial
516    /// path (column by column, plain loops) instead of the dense kernel;
517    /// an update by a descendant narrower than this takes the plain loops
518    /// too. Default `8`.
519    pub min_supernode_cols: usize,
520    /// The simplicial/supernodal switch (step A3′): when the flop count of
521    /// the factorization per stored entry of `L`, `(Σ_j c_j + Σ_j
522    /// c_j(c_j+1)/2) / Σ_j c_j`, is at most this, the matrix is too sparse
523    /// for dense blocks to pay: the fundamental supernodes are kept (no
524    /// relaxation, no explicit zero) and every supernode takes the
525    /// simplicial path. `0` forces the supernodal structure, `∞` the
526    /// simplicial one. Default `40` (CHOLMOD's `supernodal_switch`, faer's
527    /// `AUTO`).
528    pub supernodal_switch: f64,
529    /// `LBLᵀ` path only (Algorithm M, step M3): a pivot whose magnitude is
530    /// at most this fraction of the largest entry of its column in the
531    /// diagonal block of its supernode is a zero pivot and is delayed to
532    /// the parent supernode (a `2×2` block: its determinant against the
533    /// product of the two columns' largest entries). Relative, so that a
534    /// pivot that is zero up to rounding is caught and a merely small one
535    /// is kept. Default `10⁻¹⁴`.
536    pub zero_pivot_tol: f64,
537    /// `LBLᵀ` path only (Algorithm M, step M4): the threshold `u` of the
538    /// growth test. A pivot whose column of `L` below the diagonal block
539    /// has an entry above `1/u` is delayed to the parent supernode, where
540    /// the large entry's row is a candidate partner (the threshold partial
541    /// pivoting of MA57 among the fully summed variables). Default `10⁻⁸`
542    /// (Ipopt's setting for MA57 on interior-point systems: it stops the
543    /// growth that turns the pivots below into rounding noise and leaves
544    /// the merely small pivots of a barrier method alone).
545    pub pivot_threshold: f64,
546}
547
548impl Default for SupernodalOptions {
549    fn default() -> Self {
550        Self {
551            relax_zeros: 4,
552            min_supernode_cols: 8,
553            supernodal_switch: 40.0,
554            zero_pivot_tol: 1e-14,
555            pivot_threshold: 1e-8,
556        }
557    }
558}
559
560/// What the solves need of the symbolic phase, shared by the symbolic and
561/// the numeric objects (an `Arc`: a [`NumericLdl`] solves after its
562/// [`SymbolicLdl`] is dropped, and never with another one's structure).
563#[derive(Debug)]
564struct Structure {
565    n: usize,
566    /// `π` (step A2′): `fwd[k]` the original row eliminated `k`-th.
567    perm: Perm,
568    /// Supernode boundaries (`n_supernodes + 1` entries).
569    supernodes: Vec<u32>,
570    /// `R_s` for every supernode, CSR.
571    row_ptr: Vec<usize>,
572    row_idx: Vec<u32>,
573}
574
575impl Structure {
576    #[inline]
577    fn n_supernodes(&self) -> usize {
578        self.supernodes.len() - 1
579    }
580
581    #[inline]
582    fn cols(&self, s: usize) -> (usize, usize) {
583        (self.supernodes[s] as usize, self.supernodes[s + 1] as usize)
584    }
585
586    #[inline]
587    fn pattern(&self, s: usize) -> &[u32] {
588        &self.row_idx[self.row_ptr[s]..self.row_ptr[s + 1]]
589    }
590}
591
592/// The symbolic factor of [`SupernodalLdl`] (Algorithm A): permutation,
593/// elimination tree, supernode partition and the row pattern of every
594/// supernode, plus (private) the scatter map of `K` and the descendant
595/// lists of the left-looking numeric phase.
596#[derive(Clone, Debug)]
597pub struct SymbolicLdl {
598    /// The fill-reducing permutation used (`fwd[k]` = the original row
599    /// eliminated `k`-th): the ordering's, postordered (step A2′).
600    pub perm: Perm,
601    /// Parent of each column (permuted numbering) in the elimination tree;
602    /// `u32::MAX` for a root.
603    pub etree: Vec<u32>,
604    /// Supernode boundaries over the permuted columns: supernode `s` is
605    /// the columns `supernodes[s]..supernodes[s + 1]` (`n_supernodes + 1`
606    /// entries).
607    pub supernodes: Vec<u32>,
608    /// Row pattern `R_s` of each supernode (the rows below its diagonal
609    /// block, permuted numbering, increasing): `row_idx[row_ptr[s]..row_ptr[s + 1]]`.
610    pub row_ptr: Vec<usize>,
611    /// See [`SymbolicLdl::row_ptr`].
612    pub row_idx: Vec<u32>,
613    /// Stored length of the factor: `Σ_s nrows(s) · ncols(s)` (step A9).
614    pub nnz_l: usize,
615    /// The form the pattern was analyzed for.
616    pub form: KktForm,
617    /// `L₀` (step A1), the pattern the numeric phase assembles on.
618    lower: Pattern,
619    /// Step A8: for entry `p` of `lower`, its supernode and the offset in
620    /// the block.
621    sc_super: Vec<u32>,
622    sc_off: Vec<usize>,
623    /// Step A7: the `(d, a, b)` of every supernode, CSR by `s`.
624    upd_ptr: Vec<usize>,
625    upd_d: Vec<u32>,
626    upd_from: Vec<u32>,
627    upd_to: Vec<u32>,
628    /// The explicit zeros counted in step A5 (invariant (L3)).
629    relax_zeros: usize,
630    /// The column counts `c_j` of Algorithm E (invariant (L3)).
631    counts: Vec<usize>,
632    /// Step A3′: the simplicial structure was chosen.
633    simplicial: bool,
634    shared: Arc<Structure>,
635}
636
637impl SymbolicLdl {
638    /// Number of supernodes.
639    pub fn n_supernodes(&self) -> usize {
640        self.shared.n_supernodes()
641    }
642
643    /// `true` if the switch of step A3′ chose the simplicial structure
644    /// (fundamental supernodes, plain loops), `false` for the supernodal
645    /// one (relaxed supernodes, dense kernels).
646    pub fn is_simplicial(&self) -> bool {
647        self.simplicial
648    }
649
650    /// The explicit zeros the relaxed amalgamation added to the lower
651    /// parts of the blocks (step A5): `0` with `relax_zeros = 0`.
652    pub fn relaxation_zeros(&self) -> usize {
653        self.relax_zeros
654    }
655
656    /// Checks invariants (L1)–(L4).
657    #[allow(clippy::too_many_lines)] // the four invariants in one place
658    pub fn check_invariants(&self) -> Result<(), SparseError> {
659        let st = &self.shared;
660        let n = st.n;
661        let ns = st.n_supernodes();
662        let bad = |what: String| SparseError::Malformed(what);
663        if self.perm.len() != n || st.perm != self.perm {
664            return Err(bad("(L1): permutation and structure disagree".into()));
665        }
666        self.perm.check_invariants()?;
667        if st.supernodes.len() != self.supernodes.len()
668            || st.supernodes != self.supernodes
669            || st.row_ptr != self.row_ptr
670            || st.row_idx != self.row_idx
671        {
672            return Err(bad("(L1): public fields and structure disagree".into()));
673        }
674        if st.supernodes.first() != Some(&0) || st.supernodes.last().map(|&x| x as usize) != Some(n)
675        {
676            return Err(bad("(L1): supernodes do not cover 0..N".into()));
677        }
678        let mut super_of = vec![NONE; n];
679        let mut lower_stored = 0_usize;
680        let mut stored = 0_usize;
681        for s in 0..ns {
682            let (s0, s1) = st.cols(s);
683            if s1 <= s0 {
684                return Err(bad(format!("(L1): supernode {s} is empty or decreasing")));
685            }
686            super_of[s0..s1].fill(idx32(s));
687            let pat = st.pattern(s);
688            for (q, &r) in pat.iter().enumerate() {
689                if (r as usize) < s1 || (q > 0 && pat[q - 1] >= r) {
690                    return Err(bad(format!(
691                        "(L1): pattern of supernode {s} not sorted above it"
692                    )));
693                }
694            }
695            // (L2)
696            if pat.len() + 1 != self.counts[s1 - 1] {
697                return Err(bad(format!(
698                    "(L2): supernode {s} has {} rows, column count says {}",
699                    pat.len(),
700                    self.counts[s1 - 1] - 1
701                )));
702            }
703            let nc = s1 - s0;
704            lower_stored += nc * (nc + 1) / 2 + pat.len() * nc;
705            stored += (nc + pat.len()) * nc;
706        }
707        // (L1): rows of R_s in ancestors of s.
708        for s in 0..ns {
709            let (_, s1) = st.cols(s);
710            let mut anc = self.etree[s1 - 1];
711            let mut pat = st.pattern(s).iter().peekable();
712            while let Some(&&r) = pat.peek() {
713                if anc == NONE {
714                    return Err(bad(format!(
715                        "(L1): row {r} of supernode {s} is in no ancestor"
716                    )));
717                }
718                let a = super_of[anc as usize] as usize;
719                let (a0, a1) = st.cols(a);
720                while let Some(&&r) = pat.peek() {
721                    if (r as usize) < a1 {
722                        if (r as usize) < a0 {
723                            return Err(bad(format!(
724                                "(L1): row {r} of supernode {s} is in no ancestor"
725                            )));
726                        }
727                        pat.next();
728                    } else {
729                        break;
730                    }
731                }
732                anc = self.etree[a1 - 1];
733            }
734        }
735        // (L3)
736        let structural: usize = self.counts.iter().sum();
737        if lower_stored != structural + self.relax_zeros || stored != self.nnz_l {
738            return Err(bad(format!(
739                "(L3): stored lower {lower_stored} ≠ structural {structural} + zeros {}",
740                self.relax_zeros
741            )));
742        }
743        // (L4)
744        for s in 0..ns {
745            let (s0, s1) = st.cols(s);
746            for u in self.upd_ptr[s]..self.upd_ptr[s + 1] {
747                let d = self.upd_d[u] as usize;
748                let (a, b) = (self.upd_from[u] as usize, self.upd_to[u] as usize);
749                let pd = st.pattern(d);
750                let pat_s = st.pattern(s);
751                if d >= s
752                    || a >= b
753                    || b > pd.len()
754                    || pd[a..b]
755                        .iter()
756                        .any(|&r| (r as usize) < s0 || (r as usize) >= s1)
757                    || pd[b..].iter().any(|&r| pat_s.binary_search(&r).is_err())
758                {
759                    return Err(bad(format!(
760                        "(L4): update ({d}, {a}, {b}) of supernode {s}"
761                    )));
762                }
763            }
764        }
765        Ok(())
766    }
767}
768
769/// The numeric factor of [`SupernodalLdl`]: `P K_reg Pᵀ = L̂ Δ̂ L̂ᵀ` with
770/// `L̂` by blocks (column-major, `Δ̂` on the diagonal, the unit diagonal of
771/// `L̂` implicit), in the caller's units (step N4). For the `LDLᵀ` of
772/// Algorithm N (both regularized systems) `Δ̂` is diagonal, the blocks are
773/// the symbolic supernodes and `P` is [`SymbolicLdl::perm`]. For the
774/// `LBLᵀ` of Algorithm M (the unregularized augmented system) `Δ̂` has
775/// `2×2` blocks — `pivot_2x2` true on both their columns, `e₂₁` stored in
776/// the block at the slot `(k + 1, k)` where `L̂` has an implicit zero —,
777/// `P` is the pivot order [`NumericLdl::perm`], and the blocks' pivot
778/// ranges and rows are [`NumericLdl::supernodes`] and [`NumericLdl::rows`]
779/// (delayed pivots move columns between blocks).
780#[derive(Clone, Debug)]
781pub struct NumericLdl<T: Real = f64> {
782    /// One block per supernode: `nrows(s) × ncols(s)`, column-major.
783    pub blocks: Vec<DenseBlock<T>>,
784    /// `Δ̂` in pivot order (`diag[k]` = the pivot of permuted column `k`,
785    /// in the caller's units: step N4).
786    pub diag: Vec<T>,
787    /// `2×2` pivot marks, in pivot order: `true` on both columns of a
788    /// `2×2` block (`LBLᵀ`); all `false` for `LDLᵀ`.
789    pub pivot_2x2: Vec<bool>,
790    /// The inertia of the factor (S6).
791    pub inertia: Inertia,
792    /// Pivots that dynamic regularization bumped (step K3), of both signs,
793    /// counted as they are bumped.
794    pub bumped: usize,
795    /// `s` of step K2′ (powers of two), original numbering.
796    scale: Vec<T>,
797    shared: Arc<Structure>,
798    /// The work vector of Algorithm S (`N` scalars), allocated by the
799    /// factorization.
800    scratch: SolveScratch<T>,
801    /// `Some` for an `LBLᵀ` factor (Algorithm M).
802    lblt: Option<Lblt>,
803}
804
805/// The work vector of [`KktSolver::solve`], allocated once by the
806/// factorization; a mutex so that a shared factor stays `Sync` (a second
807/// thread solving with the same factor at the same moment gets a
808/// temporary vector instead of waiting).
809struct SolveScratch<T>(Mutex<Vec<T>>);
810
811impl<T: Clone> Clone for SolveScratch<T> {
812    fn clone(&self) -> Self {
813        let v = match self.0.lock() {
814            Ok(g) => g.clone(),
815            Err(poisoned) => poisoned.into_inner().clone(),
816        };
817        Self(Mutex::new(v))
818    }
819}
820
821impl<T> core::fmt::Debug for SolveScratch<T> {
822    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
823        f.write_str("SolveScratch")
824    }
825}
826
827impl<T: Real> NumericLdl<T> {
828    /// The order `N` of the factor.
829    pub fn order(&self) -> usize {
830        self.shared.n
831    }
832
833    /// Number of supernodes.
834    pub fn n_supernodes(&self) -> usize {
835        self.shared.n_supernodes()
836    }
837
838    /// The permutation of the factor (`fwd[k]` = the original row of pivot
839    /// `k`): the symbolic one (step A2′) for `LDLᵀ`, the pivot order `fwd′`
840    /// of Algorithm M for `LBLᵀ`.
841    pub fn perm(&self) -> &Perm {
842        match &self.lblt {
843            Some(l) => &l.perm,
844            None => &self.shared.perm,
845        }
846    }
847
848    /// `true` for an `LBLᵀ` factor (Algorithm M: `2×2` pivots and delayed
849    /// pivots possible — the unregularized augmented system), `false` for
850    /// the `LDLᵀ` of Algorithm N.
851    pub fn is_pivoted(&self) -> bool {
852        self.lblt.is_some()
853    }
854
855    /// Pivots delayed to a parent supernode in Algorithm M (step M5),
856    /// counted once per delay; `0` for `LDLᵀ`.
857    pub fn delayed(&self) -> usize {
858        self.lblt.as_ref().map_or(0, |l| l.delayed)
859    }
860
861    /// The blocks' boundaries in pivot order (`n_supernodes + 1` entries):
862    /// `blocks[s]` holds the pivots `supernodes()[s]..supernodes()[s + 1]`.
863    /// The symbolic supernodes for `LDLᵀ`; with delayed pivots a block may
864    /// hold more or fewer columns than its supernode.
865    pub fn supernodes(&self) -> &[u32] {
866        match &self.lblt {
867            Some(l) => &l.starts,
868            None => &self.shared.supernodes,
869        }
870    }
871
872    /// The rows of `blocks[s]` below its diagonal block, in pivot order:
873    /// row `ncols + q` of the block is the pivot `rows(s)[q]` (for `LBLᵀ`,
874    /// the delayed rows of the block come first, then its pattern).
875    pub fn rows(&self, s: usize) -> &[u32] {
876        match &self.lblt {
877            Some(l) => &l.row_idx[l.row_ptr[s]..l.row_ptr[s + 1]],
878            None => self.shared.pattern(s),
879        }
880    }
881
882    /// The equilibration `s` of step K2′ (powers of two, original
883    /// numbering): the stored factor is of `P K_reg Pᵀ`, the pivots of the
884    /// equilibrated matrix being `d_k · s_{fwd[k]}²`.
885    pub fn scale(&self) -> &[T] {
886        &self.scale
887    }
888}
889
890/// Our own supernodal `LDLᵀ` (D10; Chapter 5.17): analyze (ordering,
891/// elimination tree, relaxed supernodes, pattern of `L`), factorize
892/// (left-looking supernodal with the dense kernel `K` on the diagonal and
893/// update blocks, pivot bumping with the expected signs, regularization
894/// policy of Chapter 5.14), solve (block forward/diagonal/backward sweeps
895/// without allocation). Generic in the scalar `T`; `K` is [`NaiveDense`]
896/// by default and `FaerDense` with the `faer` feature.
897///
898/// ```
899/// use xingo_sparse::{Amd, Col, CscMatrix, KktForm, KktSolver, Refinement, Regularization, Row, SupernodalLdl};
900/// // K = [−D, Aᵀ; A, 0] with D = diag(1, 2), A = [1 1]: lower triangle.
901/// let k = CscMatrix::from_triplets(3, 3, &[
902///     (Row(0), Col(0), -1.0), (Row(2), Col(0), 1.0),
903///     (Row(1), Col(1), -2.0), (Row(2), Col(1), 1.0),
904/// ])
905/// .unwrap();
906/// let form = KktForm::Augmented { n_primal: 2, n_dual: 1 };
907/// let solver = SupernodalLdl::<f64>::default(); // NaiveDense kernels, no dependency
908/// let sym = solver.analyze(&k.pattern(), form, &Amd::default()).unwrap();
909/// let (num, inertia) = solver.factorize(&sym, &k, Regularization::default()).unwrap();
910/// assert_eq!(inertia, form.expected_inertia(3)); // (S6): 1 positive, 2 negative
911/// let b = [1.0, 0.0, 3.0];
912/// let mut x = [0.0; 3];
913/// let report = solver.solve_refined(&num, &k, &b, &mut x, Refinement::default());
914/// assert!(report.converged && report.residual <= 1e-12);
915/// ```
916#[derive(Clone, Copy, Debug)]
917pub struct SupernodalLdl<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
918    /// Amalgamation and path-selection options.
919    pub opts: SupernodalOptions,
920    kernel: K,
921    _t: PhantomData<T>,
922}
923
924impl<T: Real, K: DenseKernel<T> + Default> Default for SupernodalLdl<T, K> {
925    fn default() -> Self {
926        Self::new(K::default(), SupernodalOptions::default())
927    }
928}
929
930impl<T: Real, K: DenseKernel<T>> SupernodalLdl<T, K> {
931    /// A solver with the given dense kernel and options.
932    pub fn new(kernel: K, opts: SupernodalOptions) -> Self {
933        Self {
934            opts,
935            kernel,
936            _t: PhantomData,
937        }
938    }
939
940    /// The dense kernel.
941    pub fn kernel(&self) -> &K {
942        &self.kernel
943    }
944}
945
946/// Step A5: accept the merge of a child group into its parent supernode?
947fn accept_merge(
948    relax_zeros: usize,
949    child_size: usize,
950    child_degree: usize,
951    child_zeros: usize,
952    parent_size: usize,
953    parent_degree: usize,
954) -> Option<usize> {
955    if relax_zeros == 0 {
956        return None;
957    }
958    let extra = (parent_size + parent_degree)
959        .checked_sub(child_degree)
960        .expect("(L1): a child's pattern lies in its parent's columns and pattern");
961    let new_zeros = child_size * extra;
962    let total = child_zeros + new_zeros;
963    let w = child_size + parent_size;
964    if new_zeros == 0 || w <= relax_zeros {
965        return Some(total);
966    }
967    let entries = w * (w + 1) / 2 + parent_degree * w;
968    let permille = RELAX_CUTOFFS
969        .iter()
970        .find(|&&(cols, _)| w <= cols)
971        .map_or(0, |&(_, z)| z);
972    (total * 1000 <= permille * entries).then_some(total)
973}
974
975/// Scratch blocks of Algorithms U and D, reused across supernodes (grown,
976/// never shrunk, inside one factorization).
977struct Scratch<T: Real> {
978    a: DenseBlock<T>,
979    b: DenseBlock<T>,
980    c: DenseBlock<T>,
981    d: DenseBlock<T>,
982}
983
984impl<T: Real> Scratch<T> {
985    fn new() -> Self {
986        Self {
987            a: DenseBlock::zeros(0, 0),
988            b: DenseBlock::zeros(0, 0),
989            c: DenseBlock::zeros(0, 0),
990            d: DenseBlock::zeros(0, 0),
991        }
992    }
993}
994
995/// Sizes `blk` as `rows × cols` (new entries zero, old ones kept: the
996/// caller overwrites what it reads).
997fn fit<T: Real>(blk: &mut DenseBlock<T>, rows: usize, cols: usize) {
998    blk.rows = rows;
999    blk.cols = cols;
1000    blk.data.resize(rows * cols, T::ZERO);
1001}
1002
1003/// A pivot failure inside a supernode, at a local column.
1004enum PivotError {
1005    Zero(usize),
1006    NotFinite(usize),
1007}
1008
1009/// Step D1's pivot: the value to store as `d_k`, bumped if asked (step K3).
1010/// `Err(true)`: exactly zero without bumping; `Err(false)`: not finite.
1011#[inline]
1012fn pivot<T: Real>(d: T, sigma: i8, tau: Option<T>, beta: T, bumped: &mut usize) -> Result<T, bool> {
1013    if !d.is_finite() {
1014        return Err(false);
1015    }
1016    let sd = if sigma < 0 { -d } else { d };
1017    match tau {
1018        Some(t) => {
1019            if le(sd, t, T::ZERO) {
1020                *bumped += 1;
1021                return Ok(if sigma < 0 { -beta } else { beta });
1022            }
1023        }
1024        None => {
1025            if is_exact_zero(d) {
1026                return Err(true);
1027            }
1028        }
1029    }
1030    Ok(d)
1031}
1032
1033/// Step D1 on the block `a`: columns `p..q`, rows up to `rows_end` (`q`
1034/// for a tile, `a.rows` for the simplicial path), the trailing columns
1035/// `k + 1..q` updated. `signs[k]`, `diag[k]` are indexed by the block's
1036/// column.
1037#[allow(clippy::too_many_arguments)] // the pieces of step D1, as in the chapter
1038fn ldl_scalar<T: Real>(
1039    a: &mut DenseBlock<T>,
1040    p: usize,
1041    q: usize,
1042    rows_end: usize,
1043    signs: &[i8],
1044    tau: Option<T>,
1045    beta: T,
1046    diag: &mut [T],
1047    bumped: &mut usize,
1048) -> Result<(), PivotError> {
1049    let nr = a.rows;
1050    let data = &mut a.data;
1051    for k in p..q {
1052        let ck = k * nr;
1053        let d = match pivot(data[ck + k], signs[k], tau, beta, bumped) {
1054            Ok(d) => d,
1055            Err(true) => return Err(PivotError::Zero(k)),
1056            Err(false) => return Err(PivotError::NotFinite(k)),
1057        };
1058        data[ck + k] = d;
1059        diag[k] = d;
1060        for x in &mut data[ck + k + 1..ck + rows_end] {
1061            *x = *x / d;
1062        }
1063        for j in k + 1..q {
1064            let t = data[ck + j] * d;
1065            let cj = j * nr;
1066            // a_ij -= l_ik (d l_jk) for i in j..rows_end.
1067            let (lo, hi) = data.split_at_mut(cj);
1068            let lk = &lo[ck + j..ck + rows_end];
1069            let aj = &mut hi[j..rows_end];
1070            for (x, &l) in aj.iter_mut().zip(lk) {
1071                *x -= l * t;
1072            }
1073        }
1074    }
1075    Ok(())
1076}
1077
1078/// Copies rows `r0..r1` of column `col` of the block `a` (leading dimension
1079/// `a.rows`) into `dst`.
1080#[inline]
1081fn gather_col<T: Real>(a: &DenseBlock<T>, col: usize, r0: usize, r1: usize, dst: &mut [T]) {
1082    dst.copy_from_slice(&a.data[r0 + col * a.rows..r1 + col * a.rows]);
1083}
1084
1085/// Writes `src` into rows `r0..r1` of column `col` of the block `a`.
1086#[inline]
1087fn scatter_col<T: Real>(a: &mut DenseBlock<T>, col: usize, r0: usize, r1: usize, src: &[T]) {
1088    a.data[r0 + col * a.rows..r1 + col * a.rows].copy_from_slice(src);
1089}
1090
1091/// Algorithm D on the block of one supernode (`signs`, `diag` indexed by
1092/// the block's columns).
1093#[allow(clippy::too_many_arguments)] // steps D1–D3 in one place
1094fn factor_block<T: Real, K: DenseKernel<T>>(
1095    a: &mut DenseBlock<T>,
1096    signs: &[i8],
1097    tau: Option<T>,
1098    beta: T,
1099    diag: &mut [T],
1100    bumped: &mut usize,
1101    kernel_path: bool,
1102    ws: &mut Scratch<T>,
1103    kernel: &K,
1104) -> Result<(), PivotError> {
1105    let (nr, nc) = (a.rows, a.cols);
1106    if !kernel_path {
1107        return ldl_scalar(a, 0, nc, nr, signs, tau, beta, diag, bumped);
1108    }
1109    let mut p = 0;
1110    while p < nc {
1111        let q = (p + PANEL).min(nc);
1112        let w = q - p;
1113        // D1.
1114        ldl_scalar(a, p, q, q, signs, tau, beta, diag, bumped)?;
1115        if q < nr {
1116            // D2: L̃ = L₁₁ Δ₁ (lower, diagonal d_k), A₂₁ gathered, solved, written back.
1117            let tile = &mut ws.b;
1118            fit(tile, w, w);
1119            tile.data.fill(T::ZERO);
1120            for j in 0..w {
1121                let d = diag[p + j];
1122                tile.data[j + j * w] = d;
1123                for i in j + 1..w {
1124                    tile.data[i + j * w] = a.data[(p + i) + (p + j) * nr] * d;
1125                }
1126            }
1127            let m = nr - q;
1128            let below = &mut ws.a;
1129            fit(below, m, w);
1130            for j in 0..w {
1131                gather_col(a, p + j, q, nr, &mut below.data[j * m..(j + 1) * m]);
1132            }
1133            kernel.trsm_lower(tile, below, true);
1134            for j in 0..w {
1135                scatter_col(a, p + j, q, nr, &below.data[j * m..(j + 1) * m]);
1136            }
1137            if q < nc {
1138                // D3: W = L₂₁ Δ₁ (the rows q..nr), then the trailing block by panels.
1139                let wblk = &mut ws.b;
1140                fit(wblk, m, w);
1141                for j in 0..w {
1142                    let d = diag[p + j];
1143                    for (x, &l) in wblk.data[j * m..(j + 1) * m]
1144                        .iter_mut()
1145                        .zip(&a.data[q + (p + j) * nr..(p + j + 1) * nr])
1146                    {
1147                        *x = l * d;
1148                    }
1149                }
1150                let mut c0 = q;
1151                while c0 < nc {
1152                    let c1 = (c0 + PANEL).min(nc);
1153                    let wc = c1 - c0;
1154                    let rows = nr - c0;
1155                    // A ← W[c0 − q.., :] (rows × w).
1156                    let ablk = &mut ws.a;
1157                    fit(ablk, rows, w);
1158                    for j in 0..w {
1159                        ablk.data[j * rows..(j + 1) * rows]
1160                            .copy_from_slice(&wblk.data[(c0 - q) + j * m..(j + 1) * m]);
1161                    }
1162                    // B ← L₂₁[c0 − q..c1 − q, :] (wc × w), from the block itself.
1163                    let bblk = &mut ws.c;
1164                    fit(bblk, wc, w);
1165                    for j in 0..w {
1166                        gather_col(a, p + j, c0, c1, &mut bblk.data[j * wc..(j + 1) * wc]);
1167                    }
1168                    // C ← A[c0.., c0..c1] (rows × wc), updated, written back.
1169                    let cblk = &mut ws.d;
1170                    fit(cblk, rows, wc);
1171                    for j in 0..wc {
1172                        gather_col(a, c0 + j, c0, nr, &mut cblk.data[j * rows..(j + 1) * rows]);
1173                    }
1174                    kernel.gemm_sub(ablk, bblk, cblk);
1175                    for j in 0..wc {
1176                        scatter_col(a, c0 + j, c0, nr, &cblk.data[j * rows..(j + 1) * rows]);
1177                    }
1178                    c0 = c1;
1179                }
1180            }
1181        }
1182        p = q;
1183    }
1184    Ok(())
1185}
1186
1187/// Algorithm U, kernel path: `L_s ← L_s − L_d[a.., :] Δ_d L_d[a..b, :]ᵀ`
1188/// (lower part), `loc` mapping permuted rows to the rows of `s`'s block.
1189#[allow(clippy::too_many_arguments)] // steps U1–U3
1190fn update_kernel<T: Real, K: DenseKernel<T>>(
1191    ld: &DenseBlock<T>,
1192    dd: &[T],
1193    pat_d: &[u32],
1194    a: usize,
1195    b: usize,
1196    ls: &mut DenseBlock<T>,
1197    s0: usize,
1198    loc: &[u32],
1199    ws: &mut Scratch<T>,
1200    kernel: &K,
1201) {
1202    let (nrd, ncd) = (ld.rows, ld.cols);
1203    let e = nrd - ncd;
1204    let (nm, nr) = (b - a, e - a);
1205    // U1.
1206    let ab = &mut ws.a;
1207    fit(ab, nr, ncd);
1208    for k in 0..ncd {
1209        gather_col(ld, k, ncd + a, nrd, &mut ab.data[k * nr..(k + 1) * nr]);
1210    }
1211    let bb = &mut ws.b;
1212    fit(bb, nm, ncd);
1213    for (k, &dk) in dd.iter().enumerate() {
1214        for (x, &l) in bb.data[k * nm..(k + 1) * nm]
1215            .iter_mut()
1216            .zip(&ld.data[k * nrd + ncd + a..k * nrd + ncd + b])
1217        {
1218            *x = l * dk;
1219        }
1220    }
1221    // U2.
1222    let cb = &mut ws.c;
1223    fit(cb, nr, nm);
1224    cb.data.fill(T::ZERO);
1225    kernel.gemm_sub(ab, bb, cb);
1226    // U3.
1227    let nrs = ls.rows;
1228    for j in 0..nm {
1229        let cj = pat_d[a + j] as usize - s0;
1230        let col = &cb.data[j * nr..(j + 1) * nr];
1231        let dst = &mut ls.data[cj * nrs..(cj + 1) * nrs];
1232        for i in j..nr {
1233            dst[loc[pat_d[a + i] as usize] as usize] += col[i];
1234        }
1235    }
1236}
1237
1238/// Algorithm U, simplicial path (plain loops, column `k` of `L_d` read
1239/// once).
1240#[allow(clippy::too_many_arguments)] // the same operands as the kernel path
1241fn update_scalar<T: Real>(
1242    ld: &DenseBlock<T>,
1243    dd: &[T],
1244    pat_d: &[u32],
1245    a: usize,
1246    b: usize,
1247    ls: &mut DenseBlock<T>,
1248    s0: usize,
1249    loc: &[u32],
1250) {
1251    let (nrd, ncd) = (ld.rows, ld.cols);
1252    let e = nrd - ncd;
1253    let nrs = ls.rows;
1254    for (k, &dk) in dd.iter().enumerate() {
1255        let col = &ld.data[k * nrd + ncd..(k + 1) * nrd];
1256        for j in a..b {
1257            let t = col[j] * dk;
1258            let cj = pat_d[j] as usize - s0;
1259            let dst = &mut ls.data[cj * nrs..(cj + 1) * nrs];
1260            for i in j..e {
1261                dst[loc[pat_d[i] as usize] as usize] -= col[i] * t;
1262            }
1263        }
1264    }
1265}
1266
1267/// `Σ a_i b_i` with four independent partial sums (the dependent chain of a
1268/// single accumulator bounds the backward sweep of Algorithm S by the
1269/// latency of the fused multiply-add, not by memory); the order of the
1270/// additions is fixed, so the result is deterministic.
1271#[inline]
1272fn dot<T: Real>(a: &[T], b: &[T]) -> T {
1273    let mut acc = [T::ZERO; 4];
1274    let (ca, ra) = a.as_chunks::<4>();
1275    let (cb, rb) = b.as_chunks::<4>();
1276    for (pa, pb) in ca.iter().zip(cb) {
1277        for k in 0..4 {
1278            acc[k] += pa[k] * pb[k];
1279        }
1280    }
1281    let mut tail = T::ZERO;
1282    for (&p, &q) in ra.iter().zip(rb) {
1283        tail += p * q;
1284    }
1285    (acc[0] + acc[1]) + (acc[2] + acc[3]) + tail
1286}
1287
1288/// `Σ_q l_q x_{idx[q] − base}`, as [`dot`] with a gathered second operand.
1289#[inline]
1290fn gather_dot<T: Real>(l: &[T], idx: &[u32], x: &[T], base: usize) -> T {
1291    let mut acc = [T::ZERO; 4];
1292    let (cl, rl) = l.as_chunks::<4>();
1293    let (ci, ri) = idx.as_chunks::<4>();
1294    for (pl, pi) in cl.iter().zip(ci) {
1295        for k in 0..4 {
1296            acc[k] += pl[k] * x[pi[k] as usize - base];
1297        }
1298    }
1299    let mut tail = T::ZERO;
1300    for (&p, &i) in rl.iter().zip(ri) {
1301        tail += p * x[i as usize - base];
1302    }
1303    (acc[0] + acc[1]) + (acc[2] + acc[3]) + tail
1304}
1305
1306/// What the solves of Algorithm S′ need of an `LBLᵀ` factor beyond the
1307/// shared structure (step M6).
1308#[derive(Clone, Debug)]
1309struct Lblt {
1310    /// `fwd′`: the pivot order (`fwd′[k]` = the original row of pivot `k`).
1311    perm: Perm,
1312    /// Pivot ranges of the blocks (`n_supernodes + 1` entries).
1313    starts: Vec<u32>,
1314    /// The rows of every block below its diagonal block (its delayed rows,
1315    /// then `R_s`), in pivot order; CSR by block.
1316    row_ptr: Vec<usize>,
1317    row_idx: Vec<u32>,
1318    /// `true` at the first column of every `2×2` block.
1319    first: Vec<bool>,
1320    /// Delays of step M5.
1321    delayed: usize,
1322}
1323
1324/// A column delayed from a block to its parent (step M5).
1325struct DelayedCol<T> {
1326    /// The analyzed column.
1327    sym: u32,
1328    /// Its Schur complement diagonal.
1329    diag: T,
1330    /// The reference scale of that diagonal (step M3): the largest term of
1331    /// the sums that produced it, carried along so that the parent judges
1332    /// the pivot against the magnitudes that made it, not against its own.
1333    scale: T,
1334    /// Cross terms with the columns delayed after it from the same block.
1335    cross: Vec<T>,
1336    /// Its entries at the pattern rows of the block that delayed it.
1337    pattern: Vec<T>,
1338    /// That block.
1339    src: u32,
1340}
1341
1342/// Work arrays of steps M3–M6, reused across supernodes.
1343struct PivotWork<T: Real> {
1344    tile: DenseBlock<T>,
1345    unit: DenseBlock<T>,
1346    panel: DenseBlock<T>,
1347    next: DenseBlock<T>,
1348    u: Vec<T>,
1349    m: Vec<T>,
1350    perm: Perm,
1351    two: Vec<bool>,
1352    active: Vec<usize>,
1353    removed: Vec<(usize, T)>,
1354    bad: Vec<usize>,
1355    cols: Vec<u32>,
1356    refs: Vec<T>,
1357}
1358
1359impl<T: Real> PivotWork<T> {
1360    fn new() -> Self {
1361        Self {
1362            tile: DenseBlock::zeros(0, 0),
1363            unit: DenseBlock::zeros(0, 0),
1364            panel: DenseBlock::zeros(0, 0),
1365            next: DenseBlock::zeros(0, 0),
1366            u: Vec::new(),
1367            m: Vec::new(),
1368            perm: Perm::identity(0),
1369            two: Vec::new(),
1370            active: Vec::new(),
1371            removed: Vec::new(),
1372            bad: Vec::new(),
1373            cols: Vec::new(),
1374            refs: Vec::new(),
1375        }
1376    }
1377}
1378
1379/// `Σ_i x_i y_i` over two strided rows of column-major blocks (step M5).
1380#[inline]
1381fn strided_dot<T: Real>(
1382    x: &[T],
1383    x0: usize,
1384    xs: usize,
1385    y: &[T],
1386    y0: usize,
1387    ys: usize,
1388    len: usize,
1389) -> T {
1390    let mut acc = T::ZERO;
1391    for i in 0..len {
1392        acc += x[x0 + i * xs] * y[y0 + i * ys];
1393    }
1394    acc
1395}
1396
1397/// `max_i |x_i y_i|` over two strided rows of column-major blocks: the
1398/// largest term of the sum [`strided_dot`] forms (step M5).
1399#[inline]
1400fn strided_term_max<T: Real>(
1401    x: &[T],
1402    x0: usize,
1403    xs: usize,
1404    y: &[T],
1405    y0: usize,
1406    ys: usize,
1407    len: usize,
1408) -> T {
1409    let mut big = T::ZERO;
1410    for i in 0..len {
1411        big = big.max((x[x0 + i * xs] * y[y0 + i * ys]).abs());
1412    }
1413    big
1414}
1415
1416/// Steps M3–M6 on the block `a` of one supernode: `w` active columns
1417/// (rows `0..w` their diagonal block, rows `w..` the pattern rows `R_s`),
1418/// `cols` their analyzed columns (`w` entries). On success `a` is the
1419/// block of step M6 (`w'` pivots in pivot order, then the delayed rows,
1420/// then `R_s`), `cols` holds the `w'` pivots in pivot order, `diag` and
1421/// `two` (`w'` entries written) the pivots and the `2×2` marks, and the
1422/// removed columns are returned for the parent (`src` left for the
1423/// caller); with `root`, a zero pivot is an error instead. `refs` (`w`
1424/// entries) are the reference
1425/// scales the columns bring (`0` for the supernode's own columns, the
1426/// carried scale of a delayed one). Errors name a local column of the
1427/// block as it was on entry.
1428#[allow(clippy::too_many_arguments, clippy::too_many_lines)] // steps M3–M6 in one place
1429fn pivot_block<T: Real, K: DenseKernel<T>>(
1430    a: &mut DenseBlock<T>,
1431    w: usize,
1432    cols: &mut Vec<u32>,
1433    refs: &[T],
1434    zero_tol: T,
1435    growth_cap: T,
1436    root: bool,
1437    diag: &mut [T],
1438    two: &mut [bool],
1439    pw: &mut PivotWork<T>,
1440    kernel: &K,
1441) -> Result<Vec<DelayedCol<T>>, PivotError> {
1442    let nr0 = a.rows;
1443    let deg = nr0 - w;
1444    // The lower-triangle entry (i, j) of the diagonal block.
1445    let at = |a: &DenseBlock<T>, i: usize, j: usize| -> T {
1446        if i >= j {
1447            a.data[i + j * nr0]
1448        } else {
1449            a.data[j + i * nr0]
1450        }
1451    };
1452    // The one-column block: the direct case of M3 and M4 in place, with
1453    // no scratch — the common case of the simplicial structure (16 512
1454    // such blocks in fit2p's augmented system). The general path below
1455    // takes over when the pivot is zero or would make `L` grow.
1456    if w == 1 {
1457        let d = a.data[0];
1458        if !d.is_finite() {
1459            return Err(PivotError::NotFinite(0));
1460        }
1461        let scale = refs[0].max(d.abs());
1462        if !le_exact(d.abs(), zero_tol * scale)
1463            && !a.data[1..].iter().any(|&x| {
1464                let q = x / d;
1465                !q.is_finite() || lt(growth_cap, q.abs())
1466            })
1467        {
1468            for x in &mut a.data[1..] {
1469                *x = *x / d;
1470            }
1471            diag[0] = d;
1472            two[0] = false;
1473            return Ok(Vec::new());
1474        }
1475    }
1476    pw.active.clear();
1477    pw.active.extend(0..w);
1478    pw.removed.clear();
1479    // M3 and M4, repeated while a pivot is delayed.
1480    loop {
1481        let wa = pw.active.len();
1482        pw.m.clear();
1483        pw.m.resize(wa, T::ZERO);
1484        if wa == 0 {
1485            fit(&mut pw.tile, 0, 0);
1486            pw.perm = Perm::identity(0);
1487            pw.two.clear();
1488        } else if wa == 1 {
1489            let j = pw.active[0];
1490            let d = a.data[j + j * nr0];
1491            if !d.is_finite() {
1492                return Err(PivotError::NotFinite(j));
1493            }
1494            let scale = refs[j].max(d.abs());
1495            pw.m[0] = scale;
1496            if le_exact(d.abs(), zero_tol * scale) {
1497                if root {
1498                    return Err(PivotError::Zero(j));
1499                }
1500                pw.removed.push((j, scale));
1501                pw.active.clear();
1502                continue;
1503            }
1504            fit(&mut pw.tile, 1, 1);
1505            pw.tile.data[0] = d;
1506            pw.perm = Perm::identity(1);
1507            pw.two.clear();
1508            pw.two.push(false);
1509        } else {
1510            let tile = &mut pw.tile;
1511            fit(tile, wa, wa);
1512            tile.data.fill(T::ZERO);
1513            for (jj, &j) in pw.active.iter().enumerate() {
1514                for (ii, &i) in pw.active.iter().enumerate().skip(jj) {
1515                    // `active` is increasing: i ≥ j, the lower triangle.
1516                    tile.data[ii + jj * wa] = a.data[i + j * nr0];
1517                }
1518            }
1519            kernel
1520                .sytrf(tile, &mut pw.perm, &mut pw.two)
1521                .expect("sytrf on a square tile");
1522            // The reference scale `m_i` of pivot i (step M3): its diagonal as
1523            // the block holds it, the scale it carries, and the terms
1524            // `l_ij b_j l_ij` of the pivots before it.
1525            for (i, r) in pw.m.iter_mut().enumerate() {
1526                let p = pw.active[pw.perm.fwd[i] as usize];
1527                *r = a.data[p + p * nr0].abs().max(refs[p]);
1528            }
1529            {
1530                let mut j = 0;
1531                while j < wa {
1532                    let pair = pw.two[j];
1533                    let e11 = tile.data[j + j * wa].abs();
1534                    let (e21, e22) = if pair {
1535                        (
1536                            tile.data[j + 1 + j * wa].abs(),
1537                            tile.data[j + 1 + (j + 1) * wa].abs(),
1538                        )
1539                    } else {
1540                        (T::ZERO, T::ZERO)
1541                    };
1542                    for i in j + 1 + usize::from(pair)..wa {
1543                        let x = tile.data[i + j * wa].abs();
1544                        let mut t = x * x * e11;
1545                        if pair {
1546                            let y = tile.data[i + (j + 1) * wa].abs();
1547                            t = t.max(x * y * e21).max(y * y * e22);
1548                        }
1549                        pw.m[i] = pw.m[i].max(t);
1550                    }
1551                    j += 1 + usize::from(pair);
1552                }
1553            }
1554            pw.bad.clear();
1555            pw.refs.clear();
1556            pw.refs.resize(wa, T::ZERO);
1557            let mut i = 0;
1558            while i < wa {
1559                let p = pw.perm.fwd[i] as usize;
1560                if pw.two[i] {
1561                    let q = pw.perm.fwd[i + 1] as usize;
1562                    let (e11, e21, e22) = (
1563                        tile.data[i + i * wa],
1564                        tile.data[i + 1 + i * wa],
1565                        tile.data[i + 1 + (i + 1) * wa],
1566                    );
1567                    if !(e11.is_finite() && e21.is_finite() && e22.is_finite()) {
1568                        return Err(PivotError::NotFinite(pw.active[p]));
1569                    }
1570                    let big = e11.abs().max(e21.abs()).max(e22.abs());
1571                    if le_exact(big, zero_tol * pw.m[i].max(pw.m[i + 1])) {
1572                        pw.bad.push(p);
1573                        pw.bad.push(q);
1574                        pw.refs[p] = pw.m[i].max(pw.m[i + 1]);
1575                        pw.refs[q] = pw.refs[p];
1576                    }
1577                    i += 2;
1578                } else {
1579                    let d = tile.data[i + i * wa];
1580                    if !d.is_finite() {
1581                        return Err(PivotError::NotFinite(pw.active[p]));
1582                    }
1583                    if le_exact(d.abs(), zero_tol * pw.m[i]) {
1584                        pw.bad.push(p);
1585                        pw.refs[p] = pw.m[i];
1586                    }
1587                    i += 1;
1588                }
1589            }
1590            if !pw.bad.is_empty() {
1591                if root {
1592                    // Nothing is left to pair a zero pivot with: the matrix is
1593                    // singular to working precision.
1594                    return Err(PivotError::Zero(pw.active[pw.bad[0]]));
1595                }
1596                pw.bad.sort_unstable();
1597                for &b in pw.bad.iter().rev() {
1598                    let j = pw.active.remove(b);
1599                    pw.removed.push((j, pw.refs[b]));
1600                }
1601                continue;
1602            }
1603        }
1604        // M4: the rows below the diagonal block, in pivot order (the
1605        // delayed rows in increasing order of their column: step M5 stores
1606        // the cross terms of each with those after it).
1607        pw.removed.sort_unstable_by_key(|&(j, _)| j);
1608        let wa = pw.active.len();
1609        let nz = pw.removed.len();
1610        let nb = nz + deg;
1611        let panel = &mut pw.panel;
1612        fit(panel, nb, wa);
1613        for i in 0..wa {
1614            let j = pw.active[pw.perm.fwd[i] as usize];
1615            let col = &mut panel.data[i * nb..(i + 1) * nb];
1616            for (r, &(k, _)) in pw.removed.iter().enumerate() {
1617                col[r] = at(a, k, j);
1618            }
1619            col[nz..].copy_from_slice(&a.data[w + j * nr0..nr0 + j * nr0]);
1620        }
1621        pw.u.clear();
1622        if wa > 0 && nb > 0 {
1623            if wa > 1 {
1624                let unit = &mut pw.unit;
1625                fit(unit, wa, wa);
1626                unit.data.fill(T::ZERO);
1627                let mut i = 0;
1628                while i < wa {
1629                    let pair = pw.two[i];
1630                    unit.data[i + i * wa] = T::ONE;
1631                    for ii in i + 1 + usize::from(pair)..wa {
1632                        unit.data[ii + i * wa] = pw.tile.data[ii + i * wa];
1633                    }
1634                    if pair {
1635                        unit.data[i + 1 + (i + 1) * wa] = T::ONE;
1636                        for ii in i + 2..wa {
1637                            unit.data[ii + (i + 1) * wa] = pw.tile.data[ii + (i + 1) * wa];
1638                        }
1639                        i += 2;
1640                    } else {
1641                        i += 1;
1642                    }
1643                }
1644                kernel.trsm_lower(unit, panel, true);
1645            }
1646            // U, the rows of the removed columns before B₁⁻¹ (step M5).
1647            for i in 0..wa {
1648                pw.u.extend_from_slice(&panel.data[i * nb..i * nb + nz]);
1649            }
1650            // L₂₁ ← U B₁⁻¹.
1651            let mut i = 0;
1652            while i < wa {
1653                if pw.two[i] {
1654                    let (e11, e21, e22) = (
1655                        pw.tile.data[i + i * wa],
1656                        pw.tile.data[i + 1 + i * wa],
1657                        pw.tile.data[i + 1 + (i + 1) * wa],
1658                    );
1659                    let det = e11 * e22 - e21 * e21;
1660                    let (lo, hi) = panel.data.split_at_mut((i + 1) * nb);
1661                    let cx = &mut lo[i * nb..];
1662                    let cy = &mut hi[..nb];
1663                    for (x, y) in cx.iter_mut().zip(cy.iter_mut()) {
1664                        let (vx, vy) = (*x, *y);
1665                        *x = (vx * e22 - vy * e21) / det;
1666                        *y = (vy * e11 - vx * e21) / det;
1667                    }
1668                    i += 2;
1669                } else {
1670                    let d = pw.tile.data[i + i * wa];
1671                    for x in &mut panel.data[i * nb..(i + 1) * nb] {
1672                        *x = *x / d;
1673                    }
1674                    i += 1;
1675                }
1676            }
1677            // The growth test (step M4): a pivot whose column of L below the
1678            // block exceeds 1/u is delayed; its large entry's row is a
1679            // candidate partner higher up.
1680            pw.bad.clear();
1681            pw.refs.clear();
1682            pw.refs.resize(wa, T::ZERO);
1683            let grown = |i: usize| -> bool {
1684                panel.data[i * nb..(i + 1) * nb]
1685                    .iter()
1686                    .any(|x| !x.is_finite() || lt(growth_cap, x.abs()))
1687            };
1688            let mut i = 0;
1689            while i < wa {
1690                let p = pw.perm.fwd[i] as usize;
1691                if pw.two[i] {
1692                    let q = pw.perm.fwd[i + 1] as usize;
1693                    if grown(i) || grown(i + 1) {
1694                        pw.bad.push(p);
1695                        pw.bad.push(q);
1696                        pw.refs[p] = pw.m[i].max(pw.m[i + 1]);
1697                        pw.refs[q] = pw.refs[p];
1698                    }
1699                    i += 2;
1700                } else {
1701                    if grown(i) {
1702                        pw.bad.push(p);
1703                        pw.refs[p] = pw.m[i];
1704                    }
1705                    i += 1;
1706                }
1707            }
1708            if !pw.bad.is_empty() {
1709                if root {
1710                    // A root has no pattern rows; only delayed rows can grow,
1711                    // and nothing is left to pair them with.
1712                    return Err(PivotError::Zero(pw.active[pw.bad[0]]));
1713                }
1714                pw.bad.sort_unstable();
1715                for &b in pw.bad.iter().rev() {
1716                    let j = pw.active.remove(b);
1717                    pw.removed.push((j, pw.refs[b]));
1718                }
1719                continue;
1720            }
1721        }
1722        break;
1723    }
1724    let wa = pw.active.len();
1725    let nz = pw.removed.len();
1726    let nb = nz + deg;
1727    let panel = &mut pw.panel;
1728    // M5: the delayed columns, with their Schur complement after the
1729    // active pivots: `a − l_row · u_k`.
1730    let mut out = Vec::with_capacity(nz);
1731    for (r, &(k, scale)) in pw.removed.iter().enumerate() {
1732        let schur = |row: usize| strided_dot(&panel.data, row, nb, &pw.u, r, nz, wa);
1733        let diag_k = at(a, k, k) - schur(r);
1734        // The terms of this sum join the scale (step M5): pivots chosen
1735        // after the column was flagged may cancel in it.
1736        let scale = scale.max(at(a, k, k).abs()).max(strided_term_max(
1737            &panel.data,
1738            r,
1739            nb,
1740            &pw.u,
1741            r,
1742            nz,
1743            wa,
1744        ));
1745        let cross: Vec<T> = (r + 1..nz)
1746            .map(|r2| at(a, pw.removed[r2].0, k) - schur(r2))
1747            .collect();
1748        let pattern: Vec<T> = (0..deg)
1749            .map(|q| a.data[w + q + k * nr0] - schur(nz + q))
1750            .collect();
1751        out.push(DelayedCol {
1752            sym: cols[k],
1753            diag: diag_k,
1754            scale,
1755            cross,
1756            pattern,
1757            src: NONE,
1758        });
1759    }
1760    // M6: the new block.
1761    let nrn = wa + nb;
1762    let next = &mut pw.next;
1763    fit(next, nrn, wa);
1764    next.data.fill(T::ZERO);
1765    for i in 0..wa {
1766        let col = &mut next.data[i * nrn..(i + 1) * nrn];
1767        col[i..wa].copy_from_slice(&pw.tile.data[i + i * wa..(i + 1) * wa]);
1768        col[wa..].copy_from_slice(&panel.data[i * nb..(i + 1) * nb]);
1769        diag[i] = pw.tile.data[i + i * wa];
1770        two[i] = pw.two[i];
1771    }
1772    core::mem::swap(&mut a.data, &mut next.data);
1773    a.rows = nrn;
1774    a.cols = wa;
1775    pw.cols.clear();
1776    pw.cols
1777        .extend((0..wa).map(|i| cols[pw.active[pw.perm.fwd[i] as usize]]));
1778    cols.clear();
1779    cols.extend_from_slice(&pw.cols);
1780    Ok(out)
1781}
1782
1783/// Algorithm U for the `LBLᵀ` path (step M2), kernel path: as
1784/// [`update_kernel`], with `B ← L_d[a..b, :] B_d` for the block-diagonal
1785/// `B_d` (`dd`, `td`: the pivots and the `2×2` marks of `d` in pivot
1786/// order; `e₂₁` read from the block) and the rows of `d` read past its
1787/// `off` delayed rows.
1788#[allow(clippy::too_many_arguments)] // the operands of step M2
1789fn update_lblt_kernel<T: Real, K: DenseKernel<T>>(
1790    ld: &DenseBlock<T>,
1791    dd: &[T],
1792    td: &[bool],
1793    off: usize,
1794    pat_d: &[u32],
1795    a: usize,
1796    b: usize,
1797    ls: &mut DenseBlock<T>,
1798    s0: usize,
1799    loc: &[u32],
1800    dscale: &mut [T],
1801    ws: &mut Scratch<T>,
1802    kernel: &K,
1803) {
1804    let (nrd, ncd) = (ld.rows, ld.cols);
1805    let base = ncd + off;
1806    let e = nrd - base;
1807    let (nm, nr) = (b - a, e - a);
1808    let ab = &mut ws.a;
1809    fit(ab, nr, ncd);
1810    for k in 0..ncd {
1811        gather_col(ld, k, base + a, nrd, &mut ab.data[k * nr..(k + 1) * nr]);
1812    }
1813    let bb = &mut ws.b;
1814    fit(bb, nm, ncd);
1815    let mut k = 0;
1816    while k < ncd {
1817        let lk = &ld.data[k * nrd + base + a..k * nrd + base + b];
1818        if td[k] {
1819            let lk1 = &ld.data[(k + 1) * nrd + base + a..(k + 1) * nrd + base + b];
1820            let (e11, e21, e22) = (dd[k], ld.data[k + 1 + k * nrd], dd[k + 1]);
1821            for j in 0..nm {
1822                bb.data[k * nm + j] = e11 * lk[j] + e21 * lk1[j];
1823                bb.data[(k + 1) * nm + j] = e21 * lk[j] + e22 * lk1[j];
1824            }
1825            k += 2;
1826        } else {
1827            let dk = dd[k];
1828            for (x, &l) in bb.data[k * nm..(k + 1) * nm].iter_mut().zip(lk) {
1829                *x = l * dk;
1830            }
1831            k += 1;
1832        }
1833    }
1834    let cb = &mut ws.c;
1835    fit(cb, nr, nm);
1836    cb.data.fill(T::ZERO);
1837    kernel.gemm_sub(ab, bb, cb);
1838    let nrs = ls.rows;
1839    for j in 0..nm {
1840        let cj = pat_d[a + j] as usize - s0;
1841        let col = &cb.data[j * nr..(j + 1) * nr];
1842        dscale[cj] = dscale[cj].max(col[j].abs());
1843        let dst = &mut ls.data[cj * nrs..(cj + 1) * nrs];
1844        for i in j..nr {
1845            dst[loc[pat_d[a + i] as usize] as usize] += col[i];
1846        }
1847    }
1848}
1849
1850/// Algorithm U for the `LBLᵀ` path, simplicial path (plain loops).
1851#[allow(clippy::too_many_arguments)] // the same operands as the kernel path
1852fn update_lblt_scalar<T: Real>(
1853    ld: &DenseBlock<T>,
1854    dd: &[T],
1855    td: &[bool],
1856    off: usize,
1857    pat_d: &[u32],
1858    a: usize,
1859    b: usize,
1860    ls: &mut DenseBlock<T>,
1861    s0: usize,
1862    loc: &[u32],
1863    dscale: &mut [T],
1864) {
1865    let (nrd, ncd) = (ld.rows, ld.cols);
1866    let base = ncd + off;
1867    let e = nrd - base;
1868    let nrs = ls.rows;
1869    let mut k = 0;
1870    while k < ncd {
1871        let col = &ld.data[k * nrd + base..(k + 1) * nrd];
1872        if td[k] {
1873            let col1 = &ld.data[(k + 1) * nrd + base..(k + 2) * nrd];
1874            let (e11, e21, e22) = (dd[k], ld.data[k + 1 + k * nrd], dd[k + 1]);
1875            for j in a..b {
1876                let (t0, t1) = (e11 * col[j] + e21 * col1[j], e21 * col[j] + e22 * col1[j]);
1877                let cj = pat_d[j] as usize - s0;
1878                dscale[cj] = dscale[cj].max((col[j] * t0 + col1[j] * t1).abs());
1879                let dst = &mut ls.data[cj * nrs..(cj + 1) * nrs];
1880                for i in j..e {
1881                    dst[loc[pat_d[i] as usize] as usize] -= col[i] * t0 + col1[i] * t1;
1882                }
1883            }
1884            k += 2;
1885        } else {
1886            let dk = dd[k];
1887            for j in a..b {
1888                let t = col[j] * dk;
1889                let cj = pat_d[j] as usize - s0;
1890                dscale[cj] = dscale[cj].max((col[j] * t).abs());
1891                let dst = &mut ls.data[cj * nrs..(cj + 1) * nrs];
1892                for i in j..e {
1893                    dst[loc[pat_d[i] as usize] as usize] -= col[i] * t;
1894                }
1895            }
1896            k += 1;
1897        }
1898    }
1899}
1900
1901impl<T: Real, K: DenseKernel<T>> SupernodalLdl<T, K> {
1902    /// Algorithm M: the `LBLᵀ` of the unregularized augmented system.
1903    #[allow(clippy::too_many_lines)] // steps M1–M6 and N4–N6 in order, as in the chapter
1904    fn factorize_lblt(
1905        &self,
1906        symbolic: &SymbolicLdl,
1907        k: &CscMatrix<T>,
1908        reg: &Regularization<T>,
1909    ) -> Result<(NumericLdl<T>, Inertia), KktError> {
1910        let st = &symbolic.shared;
1911        let n = st.n;
1912        let ns = st.n_supernodes();
1913        // N1.
1914        let (v, scale) = assemble_regularized(&symbolic.lower, symbolic.form, k, reg)?;
1915        // N2.
1916        let mut blocks: Vec<DenseBlock<T>> = (0..ns)
1917            .map(|s| {
1918                let (s0, s1) = st.cols(s);
1919                DenseBlock::zeros(s1 - s0 + st.pattern(s).len(), s1 - s0)
1920            })
1921            .collect();
1922        for (p, &x) in v.iter().enumerate() {
1923            blocks[symbolic.sc_super[p] as usize].data[symbolic.sc_off[p]] = x;
1924        }
1925        let fwd = &st.perm.fwd;
1926        let mut super_of = vec![NONE; n];
1927        for s in 0..ns {
1928            let (s0, s1) = st.cols(s);
1929            super_of[s0..s1].fill(idx32(s));
1930        }
1931        let sparent = |s: usize| -> u32 {
1932            let p = symbolic.etree[st.cols(s).1 - 1];
1933            if p == NONE {
1934                NONE
1935            } else {
1936                super_of[p as usize]
1937            }
1938        };
1939        let zero_tol = T::from_f64(self.opts.zero_pivot_tol);
1940        let growth_cap = T::from_f64(self.opts.pivot_threshold).recip();
1941        let min_cols = if symbolic.simplicial {
1942            usize::MAX
1943        } else {
1944            self.opts.min_supernode_cols
1945        };
1946        let mut diag = vec![T::ZERO; n];
1947        let mut two = vec![false; n];
1948        let mut fwd_new = vec![0_u32; n];
1949        let mut pos = vec![NONE; n];
1950        let mut starts = vec![0_u32; ns + 1];
1951        let mut drow_ptr = vec![0_usize; ns + 1];
1952        let mut drows: Vec<u32> = Vec::new();
1953        let mut inbox: Vec<Vec<DelayedCol<T>>> = (0..ns).map(|_| Vec::new()).collect();
1954        let mut loc = vec![NONE; n];
1955        let mut ws = Scratch::new();
1956        let mut pw = PivotWork::new();
1957        let mut cols: Vec<u32> = Vec::new();
1958        let mut refs: Vec<T> = Vec::new();
1959        let mut dscale = vec![T::ZERO; n];
1960        let mut delayed = 0_usize;
1961        let mut next = 0_usize;
1962        for s in 0..ns {
1963            let (s0, s1) = st.cols(s);
1964            let nc = s1 - s0;
1965            let pat = st.pattern(s);
1966            let deg = pat.len();
1967            let inb = core::mem::take(&mut inbox[s]);
1968            let nd = inb.len();
1969            let w = nc + nd;
1970            cols.clear();
1971            cols.extend((s0..s1).map(idx32));
1972            cols.extend(inb.iter().map(|d| d.sym));
1973            // N3a.
1974            for c in 0..nc {
1975                loc[s0 + c] = idx32(c);
1976            }
1977            for (q, &r) in pat.iter().enumerate() {
1978                loc[r as usize] = idx32(w + q);
1979            }
1980            let (head, tail) = blocks.split_at_mut(s);
1981            let ls = &mut tail[0];
1982            // M1.
1983            if nd > 0 {
1984                let nr = w + deg;
1985                let old = core::mem::replace(ls, DenseBlock::zeros(nr, w));
1986                let nr_old = old.rows;
1987                for c in 0..nc {
1988                    let src = &old.data[c * nr_old..(c + 1) * nr_old];
1989                    let dst = &mut ls.data[c * nr..(c + 1) * nr];
1990                    dst[..nc].copy_from_slice(&src[..nc]);
1991                    dst[w..].copy_from_slice(&src[nc..]);
1992                }
1993                for (i, d) in inb.iter().enumerate() {
1994                    let c = nc + i;
1995                    ls.data[c + c * nr] = d.diag;
1996                    for (i2, &x) in d.cross.iter().enumerate() {
1997                        ls.data[c + 1 + i2 + c * nr] = x;
1998                    }
1999                    for (&r, &x) in st.pattern(d.src as usize).iter().zip(&d.pattern) {
2000                        let lr = loc[r as usize] as usize;
2001                        debug_assert_ne!(lr, NONE as usize, "(L9)");
2002                        if lr < c {
2003                            ls.data[c + lr * nr] = x;
2004                        } else {
2005                            ls.data[lr + c * nr] = x;
2006                        }
2007                    }
2008                }
2009            }
2010            let kernel_path = w >= min_cols;
2011            // M2.
2012            for u in symbolic.upd_ptr[s]..symbolic.upd_ptr[s + 1] {
2013                let d = symbolic.upd_d[u] as usize;
2014                let (a, b) = (symbolic.upd_from[u] as usize, symbolic.upd_to[u] as usize);
2015                let ld = &head[d];
2016                let (d0, d1) = (starts[d] as usize, starts[d + 1] as usize);
2017                let off = drow_ptr[d + 1] - drow_ptr[d];
2018                let (dd, td, pat_d) = (&diag[d0..d1], &two[d0..d1], st.pattern(d));
2019                if kernel_path && ld.cols >= min_cols {
2020                    update_lblt_kernel(
2021                        ld,
2022                        dd,
2023                        td,
2024                        off,
2025                        pat_d,
2026                        a,
2027                        b,
2028                        ls,
2029                        s0,
2030                        &loc,
2031                        &mut dscale[s0..s1],
2032                        &mut ws,
2033                        &self.kernel,
2034                    );
2035                } else {
2036                    update_lblt_scalar(
2037                        ld,
2038                        dd,
2039                        td,
2040                        off,
2041                        pat_d,
2042                        a,
2043                        b,
2044                        ls,
2045                        s0,
2046                        &loc,
2047                        &mut dscale[s0..s1],
2048                    );
2049                }
2050            }
2051            // M3–M6; the reference scales the columns bring (step M3): the
2052            // largest update a descendant made to the diagonal of an own
2053            // column, the carried scale of a delayed one.
2054            refs.clear();
2055            refs.extend_from_slice(&dscale[s0..s1]);
2056            refs.extend(inb.iter().map(|d| d.scale));
2057            let parent = sparent(s);
2058            let out = pivot_block(
2059                ls,
2060                w,
2061                &mut cols,
2062                &refs,
2063                zero_tol,
2064                growth_cap,
2065                parent == NONE,
2066                &mut diag[next..],
2067                &mut two[next..],
2068                &mut pw,
2069                &self.kernel,
2070            )
2071            .map_err(|e| match e {
2072                PivotError::Zero(c) => KktError::ZeroPivot {
2073                    position: fwd[cols[c] as usize] as usize,
2074                },
2075                PivotError::NotFinite(c) => KktError::NotFinite {
2076                    position: fwd[cols[c] as usize] as usize,
2077                },
2078            })?;
2079            let wp = ls.cols;
2080            for (i, &c) in cols.iter().enumerate() {
2081                fwd_new[next + i] = fwd[c as usize];
2082                pos[c as usize] = idx32(next + i);
2083            }
2084            next += wp;
2085            starts[s + 1] = idx32(next);
2086            drow_ptr[s + 1] = drow_ptr[s] + out.len();
2087            drows.extend(out.iter().map(|d| d.sym));
2088            delayed += out.len();
2089            if !out.is_empty() {
2090                debug_assert_ne!(parent, NONE, "(L9)");
2091                let p = parent as usize;
2092                for mut d in out {
2093                    d.src = idx32(s);
2094                    inbox[p].push(d);
2095                }
2096            }
2097            // N3d.
2098            for c in 0..nc {
2099                loc[s0 + c] = NONE;
2100            }
2101            for &r in pat {
2102                loc[r as usize] = NONE;
2103            }
2104        }
2105        debug_assert_eq!(next, n, "(L7)");
2106        debug_assert!(pos.iter().all(|&p| p != NONE), "(L7)");
2107        // (L8) and the first columns of the 2×2 blocks (Algorithm S′).
2108        let mut first = vec![false; n];
2109        for s in 0..ns {
2110            let (b0, b1) = (starts[s] as usize, starts[s + 1] as usize);
2111            let mut c = b0;
2112            while c < b1 {
2113                if two[c] {
2114                    debug_assert!(c + 1 < b1 && two[c + 1], "(L8)");
2115                    first[c] = true;
2116                    c += 2;
2117                } else {
2118                    c += 1;
2119                }
2120            }
2121        }
2122        // N4: L̂ = S⁻¹ L S, Δ̂ = S⁻¹ Δ S⁻¹ (ê₂₁ = e₂₁ / (s_k s_{k+1})), in the
2123        // caller's units.
2124        for (s, blk) in blocks.iter_mut().enumerate() {
2125            let (b0, b1) = (starts[s] as usize, starts[s + 1] as usize);
2126            let wp = b1 - b0;
2127            let nr = blk.rows;
2128            let dr = &drows[drow_ptr[s]..drow_ptr[s + 1]];
2129            let pat = st.pattern(s);
2130            for c in 0..wp {
2131                let sc = scale[fwd_new[b0 + c] as usize];
2132                // The slot (c + 1, c) of the first column of a pair holds e₂₁.
2133                let pair_first = first[b0 + c];
2134                let col = &mut blk.data[c * nr..(c + 1) * nr];
2135                col[c] = col[c] / (sc * sc);
2136                diag[b0 + c] = col[c];
2137                for i in c + 1..wp {
2138                    let si = scale[fwd_new[b0 + i] as usize];
2139                    col[i] = if pair_first && i == c + 1 {
2140                        col[i] / (sc * si)
2141                    } else {
2142                        col[i] * sc / si
2143                    };
2144                }
2145                for (x, &r) in col[wp..wp + dr.len()].iter_mut().zip(dr) {
2146                    *x = *x * sc / scale[fwd[r as usize] as usize];
2147                }
2148                for (x, &r) in col[wp + dr.len()..].iter_mut().zip(pat) {
2149                    *x = *x * sc / scale[fwd[r as usize] as usize];
2150                }
2151            }
2152        }
2153        // N5 (step K3′, (S10)).
2154        for (s, blk) in blocks.iter().enumerate() {
2155            let b0 = starts[s] as usize;
2156            for c in 0..blk.cols {
2157                if blk.data[c + c * blk.rows..(c + 1) * blk.rows]
2158                    .iter()
2159                    .any(|x| !x.is_finite())
2160                {
2161                    return Err(KktError::NotFinite {
2162                        position: fwd_new[b0 + c] as usize,
2163                    });
2164                }
2165            }
2166        }
2167        // N6 (S6), with the 2×2 blocks (step K4).
2168        let mut ones = Vec::with_capacity(n);
2169        let mut twos = Vec::new();
2170        for s in 0..ns {
2171            let (b0, b1) = (starts[s] as usize, starts[s + 1] as usize);
2172            let blk = &blocks[s];
2173            let mut c = b0;
2174            while c < b1 {
2175                if first[c] {
2176                    let local = c - b0;
2177                    twos.push((diag[c], blk.data[local + 1 + local * blk.rows], diag[c + 1]));
2178                    c += 2;
2179                } else {
2180                    ones.push(diag[c]);
2181                    c += 1;
2182                }
2183            }
2184        }
2185        let found = count_inertia(ones.into_iter(), twos.into_iter());
2186        let inertia = check_inertia(found, symbolic.form.expected_inertia(n))?;
2187        // The rows of every block in pivot order (Algorithm S′).
2188        let mut row_ptr = vec![0_usize; ns + 1];
2189        let mut row_idx: Vec<u32> = Vec::with_capacity(drows.len() + st.row_idx.len());
2190        for s in 0..ns {
2191            row_idx.extend(
2192                drows[drow_ptr[s]..drow_ptr[s + 1]]
2193                    .iter()
2194                    .map(|&c| pos[c as usize]),
2195            );
2196            row_idx.extend(st.pattern(s).iter().map(|&r| pos[r as usize]));
2197            row_ptr[s + 1] = row_idx.len();
2198        }
2199        let perm = Perm::from_fwd(fwd_new).map_err(KktError::Structure)?;
2200        Ok((
2201            NumericLdl {
2202                blocks,
2203                diag,
2204                pivot_2x2: two,
2205                inertia,
2206                bumped: 0,
2207                scale,
2208                shared: Arc::clone(st),
2209                scratch: SolveScratch(Mutex::new(vec![T::ZERO; n])),
2210                lblt: Some(Lblt {
2211                    perm,
2212                    starts,
2213                    row_ptr,
2214                    row_idx,
2215                    first,
2216                    delayed,
2217                }),
2218            },
2219            inertia,
2220        ))
2221    }
2222
2223    /// Algorithm S′: the solve with an `LBLᵀ` factor.
2224    fn solve_lblt(numeric: &NumericLdl<T>, lb: &Lblt, x: &mut [T]) {
2225        let n = numeric.shared.n;
2226        let mut held = numeric.scratch.0.try_lock().ok();
2227        let mut temp = Vec::new();
2228        let y: &mut [T] = match held.as_deref_mut() {
2229            Some(v) if v.len() == n => v.as_mut_slice(),
2230            _ => {
2231                temp.resize(n, T::ZERO);
2232                temp.as_mut_slice()
2233            }
2234        };
2235        let fwd = &lb.perm.fwd;
2236        for (yk, &i) in y.iter_mut().zip(fwd) {
2237            *yk = x[i as usize];
2238        }
2239        let ns = lb.starts.len() - 1;
2240        // S1 with S2 block by block.
2241        for s in 0..ns {
2242            let (s0, s1) = (lb.starts[s] as usize, lb.starts[s + 1] as usize);
2243            let nc = s1 - s0;
2244            let blk = &numeric.blocks[s];
2245            let nr = blk.rows;
2246            let rows = &lb.row_idx[lb.row_ptr[s]..lb.row_ptr[s + 1]];
2247            let (ys, rest) = y.split_at_mut(s1);
2248            let mut j = 0;
2249            while j < nc {
2250                let pair = lb.first[s0 + j];
2251                let skip = usize::from(pair);
2252                {
2253                    let xj = ys[s0 + j];
2254                    let col = &blk.data[j * nr..(j + 1) * nr];
2255                    for (yi, &l) in ys[s0 + j + 1 + skip..]
2256                        .iter_mut()
2257                        .zip(&col[j + 1 + skip..nc])
2258                    {
2259                        *yi -= l * xj;
2260                    }
2261                    for (&r, &l) in rows.iter().zip(&col[nc..]) {
2262                        rest[r as usize - s1] -= l * xj;
2263                    }
2264                }
2265                if pair {
2266                    let xj = ys[s0 + j + 1];
2267                    let col = &blk.data[(j + 1) * nr..(j + 2) * nr];
2268                    for (yi, &l) in ys[s0 + j + 2..].iter_mut().zip(&col[j + 2..nc]) {
2269                        *yi -= l * xj;
2270                    }
2271                    for (&r, &l) in rows.iter().zip(&col[nc..]) {
2272                        rest[r as usize - s1] -= l * xj;
2273                    }
2274                    // S2 for the 2×2 block, by Cramer's rule.
2275                    let (e11, e21, e22) = (
2276                        numeric.diag[s0 + j],
2277                        blk.data[j + 1 + j * nr],
2278                        numeric.diag[s0 + j + 1],
2279                    );
2280                    let det = e11 * e22 - e21 * e21;
2281                    let (b0, b1) = (ys[s0 + j], ys[s0 + j + 1]);
2282                    ys[s0 + j] = (e22 * b0 - e21 * b1) / det;
2283                    ys[s0 + j + 1] = (e11 * b1 - e21 * b0) / det;
2284                    j += 2;
2285                } else {
2286                    ys[s0 + j] = ys[s0 + j] / numeric.diag[s0 + j];
2287                    j += 1;
2288                }
2289            }
2290        }
2291        // S3.
2292        for s in (0..ns).rev() {
2293            let (s0, s1) = (lb.starts[s] as usize, lb.starts[s + 1] as usize);
2294            let nc = s1 - s0;
2295            let blk = &numeric.blocks[s];
2296            let nr = blk.rows;
2297            let rows = &lb.row_idx[lb.row_ptr[s]..lb.row_ptr[s + 1]];
2298            let (ys, rest) = y.split_at_mut(s1);
2299            let mut j = nc;
2300            while j > 0 {
2301                j -= 1;
2302                let col = &blk.data[j * nr..(j + 1) * nr];
2303                let outer = gather_dot(&col[nc..], rows, rest, s1);
2304                let inner = dot(&col[j + 1..nc], &ys[s0 + j + 1..]);
2305                ys[s0 + j] -= inner + outer;
2306                if j > 0 && lb.first[s0 + j - 1] {
2307                    // The first column of the pair: the slot at row j is e₂₁.
2308                    j -= 1;
2309                    let col = &blk.data[j * nr..(j + 1) * nr];
2310                    let outer = gather_dot(&col[nc..], rows, rest, s1);
2311                    let inner = dot(&col[j + 2..nc], &ys[s0 + j + 2..]);
2312                    ys[s0 + j] -= inner + outer;
2313                }
2314            }
2315        }
2316        for (&yk, &i) in y.iter().zip(fwd) {
2317            x[i as usize] = yk;
2318        }
2319    }
2320}
2321
2322impl<T: Real, K: DenseKernel<T>> KktSolver<T> for SupernodalLdl<T, K> {
2323    type Symbolic = SymbolicLdl;
2324    type Numeric = NumericLdl<T>;
2325
2326    #[allow(clippy::too_many_lines)] // steps A1–A10 in order, as in the chapter
2327    fn analyze(
2328        &self,
2329        pattern: &Pattern,
2330        form: KktForm,
2331        ordering: &dyn Ordering,
2332    ) -> Result<SymbolicLdl, KktError> {
2333        // A1.
2334        let lower = lower_with_diagonal(pattern, form)?;
2335        let n = lower.n_cols();
2336        let full = lower.symmetric()?;
2337        // A2.
2338        let perm = ordering.order(&full, OrderingTarget::Symmetric)?;
2339        if perm.len() != n {
2340            return Err(KktError::Structure(SparseError::Dimension {
2341                what: "ordering length",
2342                expected: n,
2343                found: perm.len(),
2344            }));
2345        }
2346        // A2′.
2347        let perm = full.etree_postorder(&perm);
2348        // A3.
2349        let (parent, counts) = etree_counts(&full, &perm);
2350        let none = usize::MAX;
2351        let mut nchild = vec![0_u32; n];
2352        for &p in &parent {
2353            if p != none {
2354                nchild[p] += 1;
2355            }
2356        }
2357        // A3′.
2358        let lnz: usize = counts.iter().sum();
2359        let flops: usize = counts.iter().map(|&c| c + c * (c + 1) / 2).sum();
2360        let simplicial = le(
2361            count_f64(flops),
2362            self.opts.supernodal_switch * count_f64(lnz),
2363            0.0,
2364        );
2365        let relax = if simplicial { 0 } else { self.opts.relax_zeros };
2366        // A4.
2367        let mut fs: Vec<usize> = Vec::with_capacity(n + 1);
2368        for j in 0..n {
2369            if j == 0 || !(parent[j - 1] == j && nchild[j] == 1 && counts[j - 1] == counts[j] + 1) {
2370                fs.push(j);
2371            }
2372        }
2373        fs.push(n);
2374        let nf = fs.len() - 1;
2375        let mut fs_of = vec![0_usize; n];
2376        for f in 0..nf {
2377            fs_of[fs[f]..fs[f + 1]].fill(f);
2378        }
2379        let fdeg = |f: usize| counts[fs[f + 1] - 1] - 1;
2380        let fparent = |f: usize| {
2381            let p = parent[fs[f + 1] - 1];
2382            if p == none { none } else { fs_of[p] }
2383        };
2384        // A5.
2385        let mut bounds: Vec<u32> = vec![0];
2386        let mut zeros_total = 0_usize;
2387        let mut g_size = if nf > 0 { fs[1] - fs[0] } else { 0 };
2388        let mut g_zeros = 0_usize;
2389        for f in 0..nf {
2390            let merged = if f + 1 < nf && fparent(f) == f + 1 {
2391                accept_merge(
2392                    relax,
2393                    g_size,
2394                    fdeg(f),
2395                    g_zeros,
2396                    fs[f + 2] - fs[f + 1],
2397                    fdeg(f + 1),
2398                )
2399            } else {
2400                None
2401            };
2402            if let Some(z) = merged {
2403                g_size += fs[f + 2] - fs[f + 1];
2404                g_zeros = z;
2405            } else {
2406                bounds.push(idx32(fs[f + 1]));
2407                zeros_total += g_zeros;
2408                if f + 1 < nf {
2409                    g_size = fs[f + 2] - fs[f + 1];
2410                    g_zeros = 0;
2411                }
2412            }
2413        }
2414        let ns = bounds.len() - 1;
2415        let cols = |s: usize| (bounds[s] as usize, bounds[s + 1] as usize);
2416        let mut super_of = vec![NONE; n];
2417        for s in 0..ns {
2418            let (s0, s1) = cols(s);
2419            super_of[s0..s1].fill(idx32(s));
2420        }
2421        let sparent: Vec<u32> = (0..ns)
2422            .map(|s| {
2423                let p = parent[cols(s).1 - 1];
2424                if p == none { NONE } else { super_of[p] }
2425            })
2426            .collect();
2427        let mut child_ptr = vec![0_usize; ns + 1];
2428        for &p in &sparent {
2429            if p != NONE {
2430                child_ptr[p as usize + 1] += 1;
2431            }
2432        }
2433        for s in 0..ns {
2434            child_ptr[s + 1] += child_ptr[s];
2435        }
2436        let mut child_idx = vec![0_u32; child_ptr[ns]];
2437        let mut next = child_ptr.clone();
2438        for (c, &p) in sparent.iter().enumerate() {
2439            if p != NONE {
2440                child_idx[next[p as usize]] = idx32(c);
2441                next[p as usize] += 1;
2442            }
2443        }
2444        // A6.
2445        let mut row_ptr = vec![0_usize; ns + 1];
2446        let mut row_idx: Vec<u32> = Vec::new();
2447        let mut mark = vec![NONE; n];
2448        for s in 0..ns {
2449            let (s0, s1) = cols(s);
2450            let start = row_idx.len();
2451            let tag = idx32(s);
2452            for j in s0..s1 {
2453                for &i in full.col(perm.fwd[j] as usize) {
2454                    let r = perm.inv[i as usize] as usize;
2455                    if r >= s1 && mark[r] != tag {
2456                        mark[r] = tag;
2457                        row_idx.push(idx32(r));
2458                    }
2459                }
2460            }
2461            for &c in &child_idx[child_ptr[s]..child_ptr[s + 1]] {
2462                let c = c as usize;
2463                for q in row_ptr[c]..row_ptr[c + 1] {
2464                    let r = row_idx[q];
2465                    if r as usize >= s1 && mark[r as usize] != tag {
2466                        mark[r as usize] = tag;
2467                        row_idx.push(r);
2468                    }
2469                }
2470            }
2471            row_idx[start..].sort_unstable();
2472            row_ptr[s + 1] = row_idx.len();
2473            debug_assert_eq!(row_idx.len() - start + 1, counts[s1 - 1], "(L2)");
2474        }
2475        // A7.
2476        let mut upd_ptr = vec![0_usize; ns + 1];
2477        for d in 0..ns {
2478            let mut q = row_ptr[d];
2479            while q < row_ptr[d + 1] {
2480                let s = super_of[row_idx[q] as usize] as usize;
2481                let s1 = bounds[s + 1];
2482                while q < row_ptr[d + 1] && row_idx[q] < s1 {
2483                    q += 1;
2484                }
2485                upd_ptr[s + 1] += 1;
2486            }
2487        }
2488        for s in 0..ns {
2489            upd_ptr[s + 1] += upd_ptr[s];
2490        }
2491        let nu = upd_ptr[ns];
2492        let (mut upd_d, mut upd_from, mut upd_to) =
2493            (vec![0_u32; nu], vec![0_u32; nu], vec![0_u32; nu]);
2494        let mut next = upd_ptr.clone();
2495        for d in 0..ns {
2496            let mut q = row_ptr[d];
2497            while q < row_ptr[d + 1] {
2498                let s = super_of[row_idx[q] as usize] as usize;
2499                let s1 = bounds[s + 1];
2500                let a = q - row_ptr[d];
2501                while q < row_ptr[d + 1] && row_idx[q] < s1 {
2502                    q += 1;
2503                }
2504                let u = next[s];
2505                upd_d[u] = idx32(d);
2506                upd_from[u] = idx32(a);
2507                upd_to[u] = idx32(q - row_ptr[d]);
2508                next[s] += 1;
2509            }
2510        }
2511        // A8.
2512        let nrows = |s: usize| {
2513            let (s0, s1) = cols(s);
2514            s1 - s0 + row_ptr[s + 1] - row_ptr[s]
2515        };
2516        let nnz0 = lower.nnz();
2517        let (mut sc_super, mut sc_off) = (vec![0_u32; nnz0], vec![0_usize; nnz0]);
2518        for j in 0..n {
2519            let b = perm.inv[j] as usize;
2520            for p in lower.col_ptr[j]..lower.col_ptr[j + 1] {
2521                let a = perm.inv[lower.row_idx[p] as usize] as usize;
2522                let (col, row) = (a.min(b), a.max(b));
2523                let s = super_of[col] as usize;
2524                let (s0, s1) = cols(s);
2525                let local_row = if row < s1 {
2526                    row - s0
2527                } else {
2528                    let pat = &row_idx[row_ptr[s]..row_ptr[s + 1]];
2529                    s1 - s0
2530                        + pat
2531                            .binary_search(&idx32(row))
2532                            .expect("(L1): the row is in R_s")
2533                };
2534                sc_super[p] = idx32(s);
2535                sc_off[p] = local_row + (col - s0) * nrows(s);
2536            }
2537        }
2538        // A9.
2539        let nnz_l: usize = (0..ns).map(|s| nrows(s) * (cols(s).1 - cols(s).0)).sum();
2540        let etree: Vec<u32> = parent
2541            .iter()
2542            .map(|&p| if p == none { NONE } else { idx32(p) })
2543            .collect();
2544        let shared = Arc::new(Structure {
2545            n,
2546            perm: perm.clone(),
2547            supernodes: bounds.clone(),
2548            row_ptr: row_ptr.clone(),
2549            row_idx: row_idx.clone(),
2550        });
2551        let sym = SymbolicLdl {
2552            perm,
2553            etree,
2554            supernodes: bounds,
2555            row_ptr,
2556            row_idx,
2557            nnz_l,
2558            form,
2559            lower,
2560            sc_super,
2561            sc_off,
2562            upd_ptr,
2563            upd_d,
2564            upd_from,
2565            upd_to,
2566            relax_zeros: zeros_total,
2567            counts,
2568            simplicial,
2569            shared,
2570        };
2571        debug_assert_eq!(sym.check_invariants(), Ok(()));
2572        Ok(sym)
2573    }
2574
2575    #[allow(clippy::too_many_lines)] // steps N1–N5 in order, as in the chapter
2576    fn factorize(
2577        &self,
2578        symbolic: &SymbolicLdl,
2579        k: &CscMatrix<T>,
2580        reg: Regularization<T>,
2581    ) -> Result<(NumericLdl<T>, Inertia), KktError> {
2582        check_regularization(&reg)?;
2583        // Algorithm M for the unregularized augmented system (the rule of
2584        // Chapter 5.15, step N2); Algorithm N otherwise.
2585        if matches!(symbolic.form, KktForm::Augmented { .. })
2586            && !reg.is_quasi_definite()
2587            && reg.pivot_tol.is_none()
2588        {
2589            return self.factorize_lblt(symbolic, k, &reg);
2590        }
2591        let st = &symbolic.shared;
2592        let n = st.n;
2593        let ns = st.n_supernodes();
2594        // N1.
2595        let (v, scale) = assemble_regularized(&symbolic.lower, symbolic.form, k, &reg)?;
2596        // N2.
2597        let mut blocks: Vec<DenseBlock<T>> = (0..ns)
2598            .map(|s| {
2599                let (s0, s1) = st.cols(s);
2600                DenseBlock::zeros(s1 - s0 + st.pattern(s).len(), s1 - s0)
2601            })
2602            .collect();
2603        for (p, &x) in v.iter().enumerate() {
2604            blocks[symbolic.sc_super[p] as usize].data[symbolic.sc_off[p]] = x;
2605        }
2606        let signs_orig = pivot_signs(symbolic.form, n);
2607        let fwd = &st.perm.fwd;
2608        let signs: Vec<i8> = (0..n).map(|k| signs_orig[fwd[k] as usize]).collect();
2609        let mut diag = vec![T::ZERO; n];
2610        let mut loc = vec![NONE; n];
2611        let mut ws = Scratch::new();
2612        let mut bumped = 0_usize;
2613        let min_cols = if symbolic.simplicial {
2614            usize::MAX
2615        } else {
2616            self.opts.min_supernode_cols
2617        };
2618        // N3.
2619        for s in 0..ns {
2620            let (s0, s1) = st.cols(s);
2621            let nc = s1 - s0;
2622            let pat = st.pattern(s);
2623            for c in 0..nc {
2624                loc[s0 + c] = idx32(c);
2625            }
2626            for (q, &r) in pat.iter().enumerate() {
2627                loc[r as usize] = idx32(nc + q);
2628            }
2629            let kernel_path = nc >= min_cols;
2630            let (head, tail) = blocks.split_at_mut(s);
2631            let ls = &mut tail[0];
2632            let (dhead, dtail) = diag.split_at_mut(s0);
2633            // N3b.
2634            for u in symbolic.upd_ptr[s]..symbolic.upd_ptr[s + 1] {
2635                let d = symbolic.upd_d[u] as usize;
2636                let (a, b) = (symbolic.upd_from[u] as usize, symbolic.upd_to[u] as usize);
2637                let (d0, d1) = st.cols(d);
2638                let (ld, dd, pat_d) = (&head[d], &dhead[d0..d1], st.pattern(d));
2639                if kernel_path && d1 - d0 >= min_cols {
2640                    update_kernel(ld, dd, pat_d, a, b, ls, s0, &loc, &mut ws, &self.kernel);
2641                } else {
2642                    update_scalar(ld, dd, pat_d, a, b, ls, s0, &loc);
2643                }
2644            }
2645            // N3c.
2646            if let Err(e) = factor_block(
2647                ls,
2648                &signs[s0..s1],
2649                reg.pivot_tol,
2650                reg.bump,
2651                &mut dtail[..nc],
2652                &mut bumped,
2653                kernel_path,
2654                &mut ws,
2655                &self.kernel,
2656            ) {
2657                return Err(match e {
2658                    PivotError::Zero(c) => KktError::ZeroPivot {
2659                        position: fwd[s0 + c] as usize,
2660                    },
2661                    PivotError::NotFinite(c) => KktError::NotFinite {
2662                        position: fwd[s0 + c] as usize,
2663                    },
2664                });
2665            }
2666            // N3d.
2667            for c in 0..nc {
2668                loc[s0 + c] = NONE;
2669            }
2670            for &r in pat {
2671                loc[r as usize] = NONE;
2672            }
2673        }
2674        // N4: L̂ = S⁻¹ L S, Δ̂ = S⁻¹ Δ S⁻¹ (exact, powers of two): the factor
2675        // of P K_reg Pᵀ in the caller's units, so that the solves need no
2676        // scaling pass.
2677        for (s, blk) in blocks.iter_mut().enumerate() {
2678            let (s0, s1) = st.cols(s);
2679            let nc = s1 - s0;
2680            let nr = blk.rows;
2681            let pat = st.pattern(s);
2682            for c in 0..nc {
2683                let sc = scale[fwd[s0 + c] as usize];
2684                let col = &mut blk.data[c * nr..(c + 1) * nr];
2685                col[c] = col[c] / (sc * sc);
2686                diag[s0 + c] = col[c];
2687                for i in c + 1..nc {
2688                    col[i] = col[i] * sc / scale[fwd[s0 + i] as usize];
2689                }
2690                for (x, &r) in col[nc..].iter_mut().zip(pat) {
2691                    *x = *x * sc / scale[fwd[r as usize] as usize];
2692                }
2693            }
2694        }
2695        // N5 (step K3′, (S10)): the lower parts of the blocks.
2696        for (s, blk) in blocks.iter().enumerate() {
2697            let (s0, _) = st.cols(s);
2698            for c in 0..blk.cols {
2699                if blk.data[c + c * blk.rows..(c + 1) * blk.rows]
2700                    .iter()
2701                    .any(|x| !x.is_finite())
2702                {
2703                    return Err(KktError::NotFinite {
2704                        position: fwd[s0 + c] as usize,
2705                    });
2706                }
2707            }
2708        }
2709        // N6 (S6).
2710        let found = count_inertia(diag.iter().copied(), core::iter::empty::<(T, T, T)>());
2711        let inertia = check_inertia(found, symbolic.form.expected_inertia(n))?;
2712        debug_assert_eq!(inertia, symbolic.form.expected_inertia(n), "(S6)");
2713        Ok((
2714            NumericLdl {
2715                blocks,
2716                diag,
2717                pivot_2x2: vec![false; n],
2718                inertia,
2719                bumped,
2720                scale,
2721                shared: Arc::clone(st),
2722                scratch: SolveScratch(Mutex::new(vec![T::ZERO; n])),
2723                lblt: None,
2724            },
2725            inertia,
2726        ))
2727    }
2728
2729    fn solve(&self, numeric: &NumericLdl<T>, x: &mut [T]) {
2730        let st = &numeric.shared;
2731        let n = st.n;
2732        assert_eq!(x.len(), n, "solve: x has the wrong length");
2733        if let Some(lb) = &numeric.lblt {
2734            return Self::solve_lblt(numeric, lb, x);
2735        }
2736        // The factor's own work vector; a temporary one only if another
2737        // thread holds it (or a panic poisoned it).
2738        let mut held = numeric.scratch.0.try_lock().ok();
2739        let mut temp = Vec::new();
2740        let y: &mut [T] = match held.as_deref_mut() {
2741            Some(v) if v.len() == n => v.as_mut_slice(),
2742            _ => {
2743                temp.resize(n, T::ZERO);
2744                temp.as_mut_slice()
2745            }
2746        };
2747        let fwd = &st.perm.fwd;
2748        for (yk, &i) in y.iter_mut().zip(fwd) {
2749            *yk = x[i as usize];
2750        }
2751        let ns = st.n_supernodes();
2752        // S1.
2753        for (s, blk) in numeric.blocks.iter().enumerate().take(ns) {
2754            let (s0, s1) = st.cols(s);
2755            let nc = s1 - s0;
2756            let nr = blk.rows;
2757            let pat = st.pattern(s);
2758            if nc == 1 {
2759                let xj = y[s0];
2760                for (&r, &l) in pat.iter().zip(&blk.data[1..]) {
2761                    y[r as usize] -= l * xj;
2762                }
2763                continue;
2764            }
2765            for j in 0..nc {
2766                let xj = y[s0 + j];
2767                let col = &blk.data[j * nr..(j + 1) * nr];
2768                let (ys, rest) = y.split_at_mut(s1);
2769                for (yi, &l) in ys[s0 + j + 1..].iter_mut().zip(&col[j + 1..nc]) {
2770                    *yi -= l * xj;
2771                }
2772                for (&r, &l) in pat.iter().zip(&col[nc..]) {
2773                    rest[r as usize - s1] -= l * xj;
2774                }
2775            }
2776        }
2777        // S2.
2778        for (yk, &dk) in y.iter_mut().zip(&numeric.diag) {
2779            *yk = *yk / dk;
2780        }
2781        // S3.
2782        for s in (0..ns).rev() {
2783            let (s0, s1) = st.cols(s);
2784            let nc = s1 - s0;
2785            let blk = &numeric.blocks[s];
2786            let nr = blk.rows;
2787            let pat = st.pattern(s);
2788            if nc == 1 {
2789                let mut acc = T::ZERO;
2790                for (&r, &l) in pat.iter().zip(&blk.data[1..]) {
2791                    acc += l * y[r as usize];
2792                }
2793                y[s0] -= acc;
2794                continue;
2795            }
2796            for j in (0..nc).rev() {
2797                let col = &blk.data[j * nr..(j + 1) * nr];
2798                let (ys, rest) = y.split_at(s1);
2799                let inner = dot(&col[j + 1..nc], &ys[s0 + j + 1..]);
2800                let outer = gather_dot(&col[nc..], pat, rest, s1);
2801                y[s0 + j] -= inner + outer;
2802            }
2803        }
2804        for (&yk, &i) in y.iter().zip(fwd) {
2805            x[i as usize] = yk;
2806        }
2807    }
2808
2809    fn nnz_factor(&self, numeric: &NumericLdl<T>) -> usize {
2810        numeric.blocks.iter().map(|b| b.data.len()).sum()
2811    }
2812
2813    fn name(&self) -> &'static str {
2814        "supernodal-ldl"
2815    }
2816}
2817
2818#[cfg(test)]
2819mod tests {
2820    use super::*;
2821    use crate::kkt::sym_lower_matvec;
2822    use crate::real::{approx_eq, le};
2823    use crate::tests::kkt_gen::{kkt, rhs};
2824    use crate::{Amd, Col, Natural, Refinement, Row, ShiftScale};
2825    use proptest::prelude::*;
2826
2827    type Naive = SupernodalLdl<f64, NaiveDense>;
2828
2829    /// The three option sets the tests exercise: the defaults, every
2830    /// supernode fundamental and on the kernel path, every supernode on the
2831    /// simplicial path.
2832    fn variants() -> [SupernodalOptions; 3] {
2833        [
2834            SupernodalOptions::default(),
2835            SupernodalOptions {
2836                relax_zeros: 0,
2837                min_supernode_cols: 1,
2838                supernodal_switch: 0.0,
2839                ..SupernodalOptions::default()
2840            },
2841            SupernodalOptions {
2842                relax_zeros: 4,
2843                min_supernode_cols: 1,
2844                supernodal_switch: 0.0,
2845                ..SupernodalOptions::default()
2846            },
2847        ]
2848    }
2849
2850    /// Factorizes `k` with `reg` and refines against the unregularized `K`
2851    /// with the right-hand side `K x*` for `x* = b`; returns the inertia,
2852    /// the refined residual, the bump count and the solution.
2853    fn solve_ok<K: DenseKernel<f64>>(
2854        s: &SupernodalLdl<f64, K>,
2855        k: &CscMatrix,
2856        form: KktForm,
2857        reg: Regularization,
2858        b: &[f64],
2859    ) -> (Inertia, f64, usize, Vec<f64>) {
2860        let sym = s.analyze(&k.pattern(), form, &Amd::default()).unwrap();
2861        assert_eq!(sym.check_invariants(), Ok(()));
2862        let (num, inertia) = s.factorize(&sym, k, reg).unwrap();
2863        let mut rhs = vec![0.0; b.len()];
2864        sym_lower_matvec(k, b, &mut rhs);
2865        let mut x = vec![0.0; b.len()];
2866        let rep = s.solve_refined(&num, k, &rhs, &mut x, Refinement::default());
2867        (inertia, rep.residual, num.bumped, x)
2868    }
2869
2870    #[test]
2871    fn augmented_and_normal_systems_solve_with_the_expected_inertia() {
2872        for (seed, spread) in [(1, 0.0), (2, 4.0), (3, 8.0)] {
2873            let (aug, normal, form) = kkt(12, 30, spread, seed);
2874            for opts in variants() {
2875                let s = Naive::new(NaiveDense, opts);
2876                let (i, res, _, _) =
2877                    solve_ok(&s, &aug, form, Regularization::default(), &rhs(42, seed));
2878                assert_eq!(i, form.expected_inertia(42));
2879                assert!(le(res, 1e-10, 0.0), "aug seed {seed} {opts:?}: {res}");
2880                let (i, res, _, _) = solve_ok(
2881                    &s,
2882                    &normal,
2883                    KktForm::NormalEquations,
2884                    Regularization::default(),
2885                    &rhs(12, seed),
2886                );
2887                assert_eq!(i, KktForm::NormalEquations.expected_inertia(12));
2888                assert!(le(res, 1e-10, 0.0), "normal seed {seed} {opts:?}: {res}");
2889            }
2890        }
2891    }
2892
2893    /// (L3) and (L6): the stored sizes against `Pattern::cholesky_nnz`, and
2894    /// two factorizations equal bit for bit; the kernel and the simplicial
2895    /// paths agree to rounding.
2896    #[test]
2897    fn sizes_determinism_and_paths() {
2898        let (aug, _, form) = kkt(20, 60, 3.0, 11);
2899        let full = aug.pattern().symmetric().unwrap();
2900        let mut sols = Vec::new();
2901        for opts in variants() {
2902            let s = Naive::new(NaiveDense, opts);
2903            let sym = s.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
2904            let structural = full.cholesky_nnz(&sym.perm).unwrap();
2905            let lower: usize = (0..sym.n_supernodes())
2906                .map(|t| {
2907                    let nc = (sym.supernodes[t + 1] - sym.supernodes[t]) as usize;
2908                    let deg = sym.row_ptr[t + 1] - sym.row_ptr[t];
2909                    nc * (nc + 1) / 2 + deg * nc
2910                })
2911                .sum();
2912            assert_eq!(lower, structural + sym.relaxation_zeros());
2913            if opts.relax_zeros == 0 {
2914                assert_eq!(sym.relaxation_zeros(), 0);
2915                assert_eq!(lower, structural);
2916            }
2917            let (n1, _) = s.factorize(&sym, &aug, Regularization::default()).unwrap();
2918            let (n2, _) = s.factorize(&sym, &aug, Regularization::default()).unwrap();
2919            assert_eq!(n1.blocks, n2.blocks);
2920            assert_eq!(s.nnz_factor(&n1), sym.nnz_l);
2921            let b = rhs(80, 11);
2922            let mut x = b.clone();
2923            s.solve(&n1, &mut x);
2924            let mut y = b.clone();
2925            s.solve(&n2, &mut y);
2926            assert_eq!(x, y);
2927            sols.push(x);
2928        }
2929        for x in &sols[1..] {
2930            assert!(
2931                x.iter().zip(&sols[0]).all(|(&a, &b)| approx_eq(a, b, 1e-8)),
2932                "the paths disagree"
2933            );
2934        }
2935    }
2936
2937    #[test]
2938    fn bumps_are_counted_exactly_with_both_signs() {
2939        // K = [0 1; 1 0], one primal and one dual unknown, no static
2940        // shift: the primal pivot 0 is bumped to −β (a negative-sign bump),
2941        // the dual one is then 1/β > 0.
2942        let k = CscMatrix::from_triplets(2, 2, &[(Row(1), Col(0), 1.0)]).unwrap();
2943        let form = KktForm::Augmented {
2944            n_primal: 1,
2945            n_dual: 1,
2946        };
2947        let reg = Regularization {
2948            primal: 0.0,
2949            dual: 0.0,
2950            pivot_tol: Some(1e-13),
2951            bump: 1e-8,
2952            scale: ShiftScale::Equilibrated,
2953        };
2954        // A normal-equations matrix with a zero pivot: a positive-sign bump.
2955        let z = CscMatrix::from_triplets(
2956            3,
2957            3,
2958            &[
2959                (Row(0), Col(0), 1.0),
2960                (Row(2), Col(0), 1.0),
2961                (Row(2), Col(2), 1.0),
2962            ],
2963        )
2964        .unwrap();
2965        for opts in variants() {
2966            let s = Naive::new(NaiveDense, opts);
2967            let sym = s.analyze(&k.pattern(), form, &Natural).unwrap();
2968            let (num, inertia) = s.factorize(&sym, &k, reg).unwrap();
2969            assert_eq!(inertia, form.expected_inertia(2));
2970            assert_eq!(num.bumped, 1, "{opts:?}");
2971            let sym = s
2972                .analyze(&z.pattern(), KktForm::NormalEquations, &Natural)
2973                .unwrap();
2974            let (num, _) = s.factorize(&sym, &z, reg).unwrap();
2975            assert_eq!(num.bumped, 2, "{opts:?}"); // pivots 1 (zero row) and 2 (1 − 1 = 0)
2976        }
2977        // Many bumps of both signs: an augmented system with the primal
2978        // block zeroed out (every primal pivot is bumped to −β) and a dual
2979        // block whose Schur complement has pivots of both signs; the count
2980        // equals the number of pivots equal to ±β exactly (β chosen so that
2981        // no genuine pivot can hit it) on both paths.
2982        let (aug, _, form) = kkt(15, 40, 0.0, 21);
2983        let mut t = Vec::new();
2984        for j in 0..55 {
2985            for p in aug.col_ptr[j]..aug.col_ptr[j + 1] {
2986                if aug.row_idx[p] as usize != j {
2987                    t.push((Row(aug.row_idx[p]), Col::from_usize(j), aug.val[p]));
2988                }
2989            }
2990        }
2991        let zeroed = CscMatrix::from_triplets(55, 55, &t).unwrap();
2992        let reg = Regularization {
2993            primal: 0.0,
2994            dual: 0.0,
2995            pivot_tol: Some(1e-3),
2996            bump: 3.0e-7,
2997            scale: ShiftScale::Equilibrated,
2998        };
2999        for opts in variants() {
3000            let s = Naive::new(NaiveDense, opts);
3001            let sym = s.analyze(&zeroed.pattern(), form, &Amd::default()).unwrap();
3002            let (num, inertia) = s.factorize(&sym, &zeroed, reg).unwrap();
3003            assert_eq!(inertia, form.expected_inertia(55));
3004            let by_value = num
3005                .diag
3006                .iter()
3007                .enumerate()
3008                .filter(|&(k, &d)| {
3009                    let sk = num.scale()[num.perm().fwd[k] as usize];
3010                    approx_eq((d * sk * sk).abs(), 3.0e-7, 0.0)
3011                })
3012                .count();
3013            assert_eq!(num.bumped, by_value, "{opts:?}");
3014            assert!(num.bumped >= 40, "{opts:?}: {}", num.bumped);
3015        }
3016    }
3017
3018    #[test]
3019    fn s6_errors_zero_pivot_and_wrong_inertia() {
3020        let s = Naive::default();
3021        // K = [−1, 0; 0, 0]: the dual pivot is exactly zero.
3022        let k = CscMatrix::from_triplets(2, 2, &[(Row(0), Col(0), -1.0)]).unwrap();
3023        let form = KktForm::Augmented {
3024            n_primal: 1,
3025            n_dual: 1,
3026        };
3027        let sym = s.analyze(&k.pattern(), form, &Natural).unwrap();
3028        assert_eq!(
3029            s.factorize(&sym, &k, Regularization::none()).err(),
3030            Some(KktError::ZeroPivot { position: 1 })
3031        );
3032        let (_, inertia) = s.factorize(&sym, &k, Regularization::default()).unwrap();
3033        assert_eq!(inertia, form.expected_inertia(2));
3034        // Indefinite "normal equations": wrong inertia without bumping,
3035        // the expected one (with a bump) with it.
3036        let ind = CscMatrix::from_triplets(
3037            2,
3038            2,
3039            &[
3040                (Row(0), Col(0), 1.0),
3041                (Row(1), Col(0), 2.0),
3042                (Row(1), Col(1), 1.0),
3043            ],
3044        )
3045        .unwrap();
3046        let sym = s
3047            .analyze(&ind.pattern(), KktForm::NormalEquations, &Natural)
3048            .unwrap();
3049        assert_eq!(
3050            s.factorize(&sym, &ind, Regularization::none()).err(),
3051            Some(KktError::WrongInertia {
3052                found: Inertia {
3053                    positive: 1,
3054                    negative: 1,
3055                    zero: 0
3056                },
3057                expected: Inertia {
3058                    positive: 2,
3059                    negative: 0,
3060                    zero: 0
3061                }
3062            })
3063        );
3064        let reg = Regularization {
3065            primal: 0.0,
3066            dual: 0.0,
3067            pivot_tol: Some(1e-13),
3068            bump: 1e-8,
3069            scale: ShiftScale::Equilibrated,
3070        };
3071        let (num, inertia) = s.factorize(&sym, &ind, reg).unwrap();
3072        assert_eq!(inertia.positive, 2);
3073        assert_eq!(num.bumped, 1);
3074        // A pivot equal to δ is not a bump.
3075        let (aug, _, form) = kkt(3, 5, 0.0, 4);
3076        let sym = s.analyze(&aug.pattern(), form, &Natural).unwrap();
3077        let (num, _) = s.factorize(&sym, &aug, Regularization::default()).unwrap();
3078        assert_eq!(num.bumped, 0);
3079    }
3080
3081    #[test]
3082    fn s10_overflow_is_an_error_and_non_finite_input_is_refused() {
3083        // Pivots bumped to a tiny β make L overflow (step K3′).
3084        let t = |v: f64| {
3085            CscMatrix::from_triplets(
3086                3,
3087                3,
3088                &[
3089                    (Row(0), Col(0), v),
3090                    (Row(1), Col(0), 1.0),
3091                    (Row(2), Col(0), 1.0),
3092                    (Row(1), Col(1), 1.0),
3093                    (Row(2), Col(1), 1.0),
3094                    (Row(2), Col(2), 1.0),
3095                ],
3096            )
3097            .unwrap()
3098        };
3099        let k = t(1e-310);
3100        let reg = Regularization {
3101            primal: 0.0,
3102            dual: 0.0,
3103            pivot_tol: Some(1e-300),
3104            bump: 1e-300,
3105            scale: ShiftScale::Equilibrated,
3106        };
3107        for opts in variants() {
3108            let s = Naive::new(NaiveDense, opts);
3109            let sym = s
3110                .analyze(&k.pattern(), KktForm::NormalEquations, &Natural)
3111                .unwrap();
3112            assert!(
3113                matches!(
3114                    s.factorize(&sym, &k, reg),
3115                    Err(KktError::NotFinite { position: 1 | 2 })
3116                ),
3117                "{opts:?}"
3118            );
3119            // A NaN in K never reaches the factorization (step K1′).
3120            let mut nan = t(1.0);
3121            nan.val[0] = f64::NAN;
3122            assert!(matches!(
3123                s.factorize(&sym, &nan, Regularization::default()),
3124                Err(KktError::Structure(_))
3125            ));
3126        }
3127    }
3128
3129    #[test]
3130    fn structural_errors() {
3131        let s = Naive::default();
3132        let skew = CscMatrix::from_triplets(
3133            2,
3134            2,
3135            &[
3136                (Row(1), Col(0), 1.0),
3137                (Row(1), Col(1), 1.0),
3138                (Row(0), Col(0), 1.0),
3139                (Row(0), Col(1), 3.0),
3140            ],
3141        )
3142        .unwrap();
3143        assert!(
3144            s.analyze(&skew.pattern(), KktForm::NormalEquations, &Amd::default())
3145                .is_ok()
3146        );
3147        let up = CscMatrix::from_triplets(2, 2, &[(Row(0), Col(1), 1.0)]).unwrap();
3148        assert_eq!(
3149            s.analyze(&up.pattern(), KktForm::NormalEquations, &Amd::default())
3150                .err(),
3151            Some(KktError::NotSymmetric)
3152        );
3153        let sym = s
3154            .analyze(
3155                &CscMatrix::<f64>::zeros(2, 2).pattern(),
3156                KktForm::NormalEquations,
3157                &Amd::default(),
3158            )
3159            .unwrap();
3160        let k = CscMatrix::from_triplets(2, 2, &[(Row(1), Col(0), 1.0), (Row(0), Col(0), 1.0)])
3161            .unwrap();
3162        assert!(matches!(
3163            s.factorize(&sym, &k, Regularization::default()),
3164            Err(KktError::Structure(_))
3165        ));
3166        let k3 = CscMatrix::<f64>::zeros(3, 3);
3167        assert!(matches!(
3168            s.factorize(&sym, &k3, Regularization::default()),
3169            Err(KktError::Structure(_))
3170        ));
3171        let bad = Regularization {
3172            pivot_tol: Some(1e-13),
3173            bump: 0.0,
3174            ..Regularization::default()
3175        };
3176        assert!(matches!(
3177            s.factorize(&sym, &CscMatrix::zeros(2, 2), bad),
3178            Err(KktError::Structure(_))
3179        ));
3180        // A value that vanished (left the CSC pattern) is a zero inside the
3181        // analyzed one; the empty system is fine.
3182        let (aug, _, form) = kkt(4, 8, 1.0, 5);
3183        let sym = s.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3184        let mut thin = aug.clone();
3185        thin.row_idx.remove(1);
3186        thin.val.remove(1);
3187        for p in &mut thin.col_ptr[1..] {
3188            *p -= 1;
3189        }
3190        assert!(s.factorize(&sym, &thin, Regularization::default()).is_ok());
3191        let empty = CscMatrix::<f64>::zeros(0, 0);
3192        let sym = s
3193            .analyze(&empty.pattern(), KktForm::NormalEquations, &Amd::default())
3194            .unwrap();
3195        let (num, _) = s
3196            .factorize(&sym, &empty, Regularization::default())
3197            .unwrap();
3198        let mut x: [f64; 0] = [];
3199        s.solve(&num, &mut x);
3200        assert_eq!(s.nnz_factor(&num), 0);
3201    }
3202
3203    /// The generic code with a second scalar: `f32` (the test-only
3204    /// instance of Chapter 5.6).
3205    #[test]
3206    fn a_second_scalar_type_factorizes_and_solves() {
3207        let (aug, normal, form) = kkt(8, 20, 1.0, 7);
3208        let to32 = |k: &CscMatrix| {
3209            CscMatrix::<f32>::from_raw_parts(
3210                k.n_rows,
3211                k.col_ptr.clone(),
3212                k.row_idx.clone(),
3213                #[allow(clippy::cast_possible_truncation)]
3214                k.val.iter().map(|&v| v as f32).collect(),
3215            )
3216            .unwrap()
3217        };
3218        for opts in variants() {
3219            let s = SupernodalLdl::<f32, NaiveDense>::new(NaiveDense, opts);
3220            for (k, form) in [
3221                (to32(&aug), form),
3222                (to32(&normal), KktForm::NormalEquations),
3223            ] {
3224                let n = k.n_rows;
3225                let sym = s.analyze(&k.pattern(), form, &Amd::default()).unwrap();
3226                let (num, inertia) = s
3227                    .factorize(&sym, &k, Regularization::<f32>::default())
3228                    .unwrap();
3229                assert_eq!(inertia, form.expected_inertia(n));
3230                let xs: Vec<f32> = (0..n)
3231                    .map(|i| if i % 2 == 0 { 1.0 } else { -0.5 })
3232                    .collect();
3233                let mut b = vec![0.0_f32; n];
3234                sym_lower_matvec(&k, &xs, &mut b);
3235                let mut x = vec![0.0_f32; n];
3236                let rep = s.solve_refined(
3237                    &num,
3238                    &k,
3239                    &b,
3240                    &mut x,
3241                    Refinement {
3242                        max_iters: 10,
3243                        target_residual: 1e-5,
3244                    },
3245                );
3246                assert!(le(rep.residual, 1e-4, 0.0), "{opts:?} {form:?}: {rep:?}");
3247            }
3248        }
3249    }
3250
3251    /// The same systems through `FaerLdl` (forced supernodal) and through
3252    /// `SupernodalLdl<f64, FaerDense>`: the same stored size (the same
3253    /// amalgamation rule under the same permutation, step A5), the same
3254    /// inertia, solutions equal to rounding.
3255    #[cfg(feature = "faer")]
3256    #[test]
3257    fn agrees_with_faer() {
3258        use crate::{FaerDense, FaerLdl};
3259        for (seed, spread, m, n) in [(1, 0.0, 12, 30), (2, 4.0, 25, 60), (3, 8.0, 40, 90)] {
3260            let (aug, normal, form) = kkt(m, n, spread, seed);
3261            for (k, form) in [(aug, form), (normal, KktForm::NormalEquations)] {
3262                let nn = k.n_rows;
3263                let faer = FaerLdl {
3264                    supernodal: Some(true),
3265                };
3266                let ours = SupernodalLdl::<f64, FaerDense>::new(
3267                    FaerDense,
3268                    SupernodalOptions {
3269                        supernodal_switch: 0.0,
3270                        ..SupernodalOptions::default()
3271                    },
3272                );
3273                let fs = faer.analyze(&k.pattern(), form, &Amd::default()).unwrap();
3274                let os = ours.analyze(&k.pattern(), form, &Amd::default()).unwrap();
3275                assert_eq!(fs.perm(), &os.perm);
3276                assert_eq!(fs.nnz_factor(), os.nnz_l, "seed {seed} {form:?}");
3277                let (fn_, fi) = faer.factorize(&fs, &k, Regularization::default()).unwrap();
3278                let (on, oi) = ours.factorize(&os, &k, Regularization::default()).unwrap();
3279                assert_eq!(fi, oi);
3280                assert_eq!(fn_.bumped(), on.bumped);
3281                let b = rhs(nn, seed);
3282                let mut x = b.clone();
3283                let mut y = b.clone();
3284                faer.solve(&fn_, &mut x);
3285                ours.solve(&on, &mut y);
3286                let scale = x.iter().fold(1.0_f64, |m, v| m.max(v.abs()));
3287                assert!(
3288                    x.iter()
3289                        .zip(&y)
3290                        .all(|(&a, &b)| approx_eq(a, b, 1e-9 * scale)),
3291                    "seed {seed} {form:?}"
3292                );
3293                // And the naive kernel agrees with faer's on the kernel path.
3294                let naive = Naive::new(
3295                    NaiveDense,
3296                    SupernodalOptions {
3297                        min_supernode_cols: 1,
3298                        supernodal_switch: 0.0,
3299                        ..SupernodalOptions::default()
3300                    },
3301                );
3302                let ns = naive.analyze(&k.pattern(), form, &Amd::default()).unwrap();
3303                let (nn_, _) = naive.factorize(&ns, &k, Regularization::default()).unwrap();
3304                let mut z = b.clone();
3305                naive.solve(&nn_, &mut z);
3306                assert!(
3307                    y.iter()
3308                        .zip(&z)
3309                        .all(|(&a, &b)| approx_eq(a, b, 1e-9 * scale))
3310                );
3311            }
3312        }
3313    }
3314
3315    /// A fixed permutation as an `Ordering` (the tests of the delayed
3316    /// pivots need the dual rows eliminated first).
3317    struct Fixed(Vec<u32>);
3318    impl Ordering for Fixed {
3319        fn order(&self, _: &Pattern, _: OrderingTarget) -> Result<Perm, SparseError> {
3320            Perm::from_fwd(self.0.clone())
3321        }
3322        fn name(&self) -> &'static str {
3323            "fixed"
3324        }
3325    }
3326
3327    /// The dual rows first, then the primal columns.
3328    fn duals_first(n_primal: usize, n: usize) -> Fixed {
3329        Fixed((n_primal..n).chain(0..n_primal).map(idx32).collect())
3330    }
3331
3332    /// `true` if the constraint block `A` of the augmented `k` (its rows
3333    /// `n_primal..`) has full row rank: Gaussian elimination with partial
3334    /// pivoting on the dense `A`, relative tolerance `10⁻¹⁰`. The random
3335    /// generator guarantees a nonzero per row, not independent rows (two
3336    /// singleton rows on one column happen): a rank-deficient `A` makes the
3337    /// unregularized `K` singular, and an explicit error (`ZeroPivot`, or
3338    /// `WrongInertia` when the zero pivot reaches the root as rounding
3339    /// noise of either sign) is then the right answer.
3340    fn full_row_rank(k: &CscMatrix, n_primal: usize) -> bool {
3341        let n = k.n_rows;
3342        let m = n - n_primal;
3343        let mut a = vec![0.0_f64; m * n_primal];
3344        for j in 0..n_primal {
3345            for p in k.col_ptr[j]..k.col_ptr[j + 1] {
3346                let i = k.row_idx[p] as usize;
3347                if i >= n_primal {
3348                    a[(i - n_primal) + j * m] = k.val[p];
3349                }
3350            }
3351        }
3352        let big = a.iter().fold(0.0_f64, |x, v| x.max(v.abs()));
3353        let mut rank = 0;
3354        let mut row_used = vec![false; m];
3355        for j in 0..n_primal {
3356            let mut best = (0.0_f64, usize::MAX);
3357            for i in 0..m {
3358                if !row_used[i] && a[i + j * m].abs() > best.0 {
3359                    best = (a[i + j * m].abs(), i);
3360                }
3361            }
3362            if best.1 == usize::MAX || le(best.0, 1e-10 * big, 0.0) {
3363                continue;
3364            }
3365            let r = best.1;
3366            row_used[r] = true;
3367            rank += 1;
3368            for i in 0..m {
3369                if i != r && !row_used[i] {
3370                    let f = a[i + j * m] / a[r + j * m];
3371                    for c in j..n_primal {
3372                        a[i + c * m] -= f * a[r + c * m];
3373                    }
3374                }
3375            }
3376        }
3377        rank == m
3378    }
3379
3380    /// `‖P K Pᵀ − L B Lᵀ‖_max` from the public fields of a factor (dense;
3381    /// small systems).
3382    fn reconstruction_error(num: &NumericLdl<f64>, k: &CscMatrix) -> f64 {
3383        let n = num.order();
3384        let fwd = &num.perm().fwd;
3385        let (mut l, mut b) = (vec![0.0; n * n], vec![0.0; n * n]);
3386        let starts = num.supernodes();
3387        for s in 0..num.n_supernodes() {
3388            let (s0, s1) = (starts[s] as usize, starts[s + 1] as usize);
3389            let blk = &num.blocks[s];
3390            let (nc, nr) = (s1 - s0, blk.rows);
3391            let rows = num.rows(s);
3392            assert_eq!(nr, nc + rows.len());
3393            let mut j = 0;
3394            while j < nc {
3395                let pair = num.pivot_2x2[s0 + j];
3396                for (jj, skip) in [(j, usize::from(pair)), (j + 1, 0)] {
3397                    if jj == j + 1 && !pair {
3398                        break;
3399                    }
3400                    let col = &blk.data[jj * nr..(jj + 1) * nr];
3401                    let g = s0 + jj;
3402                    l[g + g * n] = 1.0;
3403                    b[g + g * n] = col[jj];
3404                    for i in jj + 1 + skip..nc {
3405                        l[s0 + i + g * n] = col[i];
3406                    }
3407                    for (q, &r) in rows.iter().enumerate() {
3408                        l[r as usize + g * n] = col[nc + q];
3409                    }
3410                }
3411                if pair {
3412                    assert!(num.pivot_2x2[s0 + j + 1], "(L8)");
3413                    b[s0 + j + 1 + (s0 + j) * n] = blk.data[j + 1 + j * nr];
3414                    b[s0 + j + (s0 + j + 1) * n] = blk.data[j + 1 + j * nr];
3415                    j += 2;
3416                } else {
3417                    j += 1;
3418                }
3419            }
3420        }
3421        let mut kd = vec![0.0; n * n];
3422        for c in 0..n {
3423            for p in k.col_ptr[c]..k.col_ptr[c + 1] {
3424                let r = k.row_idx[p] as usize;
3425                kd[r + c * n] = k.val[p];
3426                kd[c + r * n] = k.val[p];
3427            }
3428        }
3429        let mut err = 0.0_f64;
3430        for i in 0..n {
3431            for j in 0..=i {
3432                let mut s = 0.0;
3433                for p in 0..n {
3434                    for q in 0..n {
3435                        s += l[i + p * n] * b[p + q * n] * l[j + q * n];
3436                    }
3437                }
3438                let (pi, pj) = (fwd[i] as usize, fwd[j] as usize);
3439                err = err.max((s - kd[pi + pj * n]).abs());
3440            }
3441        }
3442        err
3443    }
3444
3445    /// Algorithm M: the unregularized augmented system factorizes with the
3446    /// expected inertia, `P K Pᵀ = L B Lᵀ` holds, the refined residual is
3447    /// small, and two factorizations agree bit for bit (L6).
3448    #[test]
3449    fn unregularized_augmented_systems_take_the_lblt_path() {
3450        // Spreads up to 10^±4: beyond that the random systems of the
3451        // generator are often numerically singular (κ > 10¹⁶, measured with
3452        // numpy on a failing seed), and the only correct answers are a zero
3453        // pivot or the wrong inertia, which the proptest below accepts.
3454        for (seed, spread, m, n) in [
3455            (1, 0.0, 6, 14),
3456            (2, 4.0, 12, 30),
3457            (3, 3.0, 20, 45),
3458            (4, 2.0, 9, 9),
3459        ] {
3460            let (aug, _, form) = kkt(m, n, spread, seed);
3461            let nn = n + m;
3462            let big = aug.val.iter().fold(0.0_f64, |x, v| x.max(v.abs()));
3463            let singular = !full_row_rank(&aug, n);
3464            for opts in variants() {
3465                let s = Naive::new(NaiveDense, opts);
3466                for ord in [&Amd::default() as &dyn Ordering, &duals_first(n, nn)] {
3467                    let sym = s.analyze(&aug.pattern(), form, ord).unwrap();
3468                    let factor = s.factorize(&sym, &aug, Regularization::none());
3469                    if singular {
3470                        // A zero pivot, or a rounding-level pivot at the root
3471                        // whose sign is noise (S6): explicit either way.
3472                        assert!(
3473                            matches!(
3474                                factor,
3475                                Err(KktError::ZeroPivot { .. } | KktError::WrongInertia { .. })
3476                            ),
3477                            "seed {seed} {opts:?}: singular K, got {:?}",
3478                            factor.map(|(_, i)| i)
3479                        );
3480                        continue;
3481                    }
3482                    let (num, inertia) = factor
3483                        .unwrap_or_else(|e| panic!("seed {seed} {opts:?} {}: {e:?}", ord.name()));
3484                    assert_eq!(inertia, form.expected_inertia(nn), "seed {seed} {opts:?}");
3485                    assert!(num.is_pivoted() && num.bumped == 0);
3486                    assert_eq!(num.perm().check_invariants(), Ok(()));
3487                    assert_eq!(num.supernodes().len(), num.n_supernodes() + 1);
3488                    assert_eq!(*num.supernodes().last().unwrap() as usize, nn);
3489                    let err = reconstruction_error(&num, &aug);
3490                    assert!(le(err, 1e-9 * big, 0.0), "seed {seed} {opts:?}: {err}");
3491                    let b = rhs(nn, seed);
3492                    let mut rhs_ = vec![0.0; nn];
3493                    sym_lower_matvec(&aug, &b, &mut rhs_);
3494                    let mut x = vec![0.0; nn];
3495                    let rep = s.solve_refined(&num, &aug, &rhs_, &mut x, Refinement::default());
3496                    assert!(
3497                        le(rep.residual, 1e-10, 0.0),
3498                        "seed {seed} {opts:?}: {rep:?}"
3499                    );
3500                    let (num2, _) = s.factorize(&sym, &aug, Regularization::none()).unwrap();
3501                    assert_eq!(num.blocks, num2.blocks);
3502                    assert_eq!(num.pivot_2x2, num2.pivot_2x2);
3503                    assert_eq!(num.delayed(), num2.delayed());
3504                }
3505            }
3506            // The regularized path is the LDLᵀ of Algorithm N.
3507            let s = Naive::default();
3508            let sym = s.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3509            let (num, _) = s.factorize(&sym, &aug, Regularization::default()).unwrap();
3510            assert!(!num.is_pivoted() && num.delayed() == 0);
3511            assert!(num.pivot_2x2.iter().all(|&t| !t));
3512            assert_eq!(num.supernodes(), &sym.supernodes[..]);
3513        }
3514    }
3515
3516    /// Step M5: dual leaves of the elimination tree are delayed to their
3517    /// parent and pivoted there (`A = [1 1 0; 1 0 1]`, dual rows first:
3518    /// both are leaves under the first primal column, which can pair with
3519    /// only one of them, so the other is delayed twice); two identical
3520    /// dual rows make the matrix singular and the zero pivot is reported at
3521    /// one of them.
3522    #[test]
3523    fn dual_leaves_are_delayed_never_ignored() {
3524        let aug = |rows: &[(usize, usize)]| {
3525            let mut t = vec![
3526                (Row(0), Col(0), -1.0),
3527                (Row(1), Col(1), -2.0),
3528                (Row(2), Col(2), -0.5),
3529            ];
3530            for &(i, j) in rows {
3531                t.push((Row::from_usize(3 + i), Col::from_usize(j), 1.0));
3532            }
3533            CscMatrix::from_triplets(5, 5, &t).unwrap()
3534        };
3535        let form = KktForm::Augmented {
3536            n_primal: 3,
3537            n_dual: 2,
3538        };
3539        let k = aug(&[(0, 0), (0, 1), (1, 0), (1, 2)]);
3540        for opts in variants() {
3541            let s = Naive::new(NaiveDense, opts);
3542            let sym = s.analyze(&k.pattern(), form, &duals_first(3, 5)).unwrap();
3543            let (num, inertia) = s.factorize(&sym, &k, Regularization::none()).unwrap();
3544            assert_eq!(inertia, form.expected_inertia(5));
3545            assert!(num.delayed() >= 1, "{opts:?}: {}", num.delayed());
3546            assert!(le(reconstruction_error(&num, &k), 1e-12, 0.0));
3547            let b = [1.0, 2.0, 3.0, 4.0, 5.0];
3548            let mut x = [0.0; 5];
3549            let rep = s.solve_refined(&num, &k, &b, &mut x, Refinement::default());
3550            assert!(le(rep.residual, 1e-12, 0.0), "{rep:?}");
3551            // Singular: identical dual rows.
3552            let z = aug(&[(0, 0), (1, 0)]);
3553            let sym = s.analyze(&z.pattern(), form, &duals_first(3, 5)).unwrap();
3554            assert!(
3555                matches!(
3556                    s.factorize(&sym, &z, Regularization::none()),
3557                    Err(KktError::ZeroPivot { position: 3 | 4 })
3558                ),
3559                "{opts:?}"
3560            );
3561            // And with the other orderings too (the leaf may sit anywhere).
3562            let sym = s.analyze(&z.pattern(), form, &Amd::default()).unwrap();
3563            assert!(matches!(
3564                s.factorize(&sym, &z, Regularization::none()),
3565                Err(KktError::ZeroPivot { .. })
3566            ));
3567        }
3568    }
3569
3570    /// The `f32` instance through Algorithm M as well.
3571    #[test]
3572    fn a_second_scalar_type_takes_the_lblt_path() {
3573        let (aug, _, form) = kkt(8, 20, 1.0, 7);
3574        let k = CscMatrix::<f32>::from_raw_parts(
3575            aug.n_rows,
3576            aug.col_ptr.clone(),
3577            aug.row_idx.clone(),
3578            #[allow(clippy::cast_possible_truncation)]
3579            aug.val.iter().map(|&v| v as f32).collect(),
3580        )
3581        .unwrap();
3582        for opts in variants() {
3583            let s = SupernodalLdl::<f32, NaiveDense>::new(NaiveDense, opts);
3584            let sym = s.analyze(&k.pattern(), form, &duals_first(20, 28)).unwrap();
3585            let (num, inertia) = s
3586                .factorize(&sym, &k, Regularization::<f32>::none())
3587                .unwrap();
3588            assert_eq!(inertia, form.expected_inertia(28));
3589            assert!(num.is_pivoted());
3590            let xs: Vec<f32> = (0..28)
3591                .map(|i| if i % 2 == 0 { 1.0 } else { -0.5 })
3592                .collect();
3593            let mut b = vec![0.0_f32; 28];
3594            sym_lower_matvec(&k, &xs, &mut b);
3595            let mut x = vec![0.0_f32; 28];
3596            let rep = s.solve_refined(
3597                &num,
3598                &k,
3599                &b,
3600                &mut x,
3601                Refinement {
3602                    max_iters: 10,
3603                    target_residual: 1e-5,
3604                },
3605            );
3606            assert!(le(rep.residual, 1e-4, 0.0), "{opts:?}: {rep:?}");
3607        }
3608    }
3609
3610    /// `FaerLdl` without regularization (its intranodal `LBLᵀ`, supernodal
3611    /// structure) and `SupernodalLdl<f64, FaerDense>` on the same systems:
3612    /// the same inertia and solutions equal to rounding.
3613    #[cfg(feature = "faer")]
3614    #[test]
3615    fn lblt_agrees_with_faer() {
3616        use crate::{FaerDense, FaerLdl};
3617        for (seed, spread, m, n) in [(1, 0.0, 12, 30), (2, 4.0, 25, 60), (3, 8.0, 40, 90)] {
3618            let (aug, _, form) = kkt(m, n, spread, seed);
3619            let nn = n + m;
3620            let faer = FaerLdl {
3621                supernodal: Some(true),
3622            };
3623            let ours = SupernodalLdl::<f64, FaerDense>::new(
3624                FaerDense,
3625                SupernodalOptions {
3626                    supernodal_switch: 0.0,
3627                    ..SupernodalOptions::default()
3628                },
3629            );
3630            let fs = faer.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3631            let os = ours.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3632            let Ok((fn_, fi)) = faer.factorize(&fs, &aug, Regularization::none()) else {
3633                // faer's intranodal pivoting has no delays: a dual leaf
3634                // alone in a supernode defeats it (that is the point of
3635                // step M5); nothing to compare on this seed.
3636                continue;
3637            };
3638            let (on, oi) = ours.factorize(&os, &aug, Regularization::none()).unwrap();
3639            assert_eq!(fi, oi);
3640            assert!(fn_.is_pivoted() && on.is_pivoted());
3641            let b = rhs(nn, seed);
3642            let (mut x, mut y) = (b.clone(), b.clone());
3643            faer.solve_refined(&fn_, &aug, &b, &mut x, Refinement::default());
3644            ours.solve_refined(&on, &aug, &b, &mut y, Refinement::default());
3645            let scale = x.iter().fold(1.0_f64, |m, v| m.max(v.abs()));
3646            assert!(
3647                x.iter()
3648                    .zip(&y)
3649                    .all(|(&a, &b)| approx_eq(a, b, 1e-8 * scale)),
3650                "seed {seed}"
3651            );
3652        }
3653    }
3654
3655    proptest! {
3656        #![proptest_config(ProptestConfig::with_cases(24))]
3657        /// (S6) and the refined residual on random KKT systems in the three
3658        /// IPM regimes, with every option set.
3659        #[test]
3660        fn random_kkt_systems(m in 1_usize..15, extra in 0_usize..20, regime in 0_usize..3, v in 0_usize..3, seed in any::<u64>()) {
3661            let n = m + extra;
3662            let spread = [0.0, 4.0, 9.0][regime];
3663            let s = Naive::new(NaiveDense, variants()[v]);
3664            let (aug, normal, form) = kkt(m, n, spread, seed);
3665            let (i, res, _, _) = solve_ok(&s, &aug, form, Regularization::default(), &rhs(n + m, seed));
3666            prop_assert_eq!(i, form.expected_inertia(n + m));
3667            prop_assert!(le(res, 1e-10, 0.0), "augmented: {}", res);
3668            if regime == 2 {
3669                // Near the end of an interior-point method the unregularized
3670                // system may be numerically singular: an explicit error or a
3671                // finite solution, never a silent NaN.
3672                let sym = s.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3673                if let Ok((num, _)) = s.factorize(&sym, &aug, Regularization::none()) {
3674                    let mut x = rhs(n + m, seed);
3675                    s.solve(&num, &mut x);
3676                    prop_assert!(x.iter().all(|v| v.is_finite()));
3677                }
3678            } else if full_row_rank(&aug, n) {
3679                let (i, res, _, _) = solve_ok(&s, &aug, form, Regularization::none(), &rhs(n + m, seed));
3680                prop_assert_eq!(i, form.expected_inertia(n + m));
3681                prop_assert!(le(res, 1e-10, 0.0), "augmented, LBLᵀ: {}", res);
3682            } else {
3683                let sym = s.analyze(&aug.pattern(), form, &Amd::default()).unwrap();
3684                let singular = s.factorize(&sym, &aug, Regularization::none());
3685                prop_assert!(matches!(singular, Err(KktError::ZeroPivot { .. } | KktError::WrongInertia { .. })), "rank-deficient A: {:?}", singular.map(|(_, i)| i));
3686            }
3687            let (i, _, _, _) = solve_ok(&s, &normal, KktForm::NormalEquations, Regularization::default(), &rhs(m, seed));
3688            prop_assert_eq!(i, KktForm::NormalEquations.expected_inertia(m));
3689        }
3690    }
3691}