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(®)?;
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, ®);
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, ®)?;
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}