Skip to main content

Module supernodal

Module supernodal 

Source
Expand description

§Chapter 5.17 — SupernodalLdl: the own supernodal LDLᵀ

New with task L1.6a (PLAN.md trilha L; the contract’s §5.7, decision D10 and D-0098). Part 1 (L1.6a): 1×1 pivots for the two regularized systems. Part 2 (L1.6b): Algorithm M, the LBLᵀ with Bunch–Kaufman 1×1/2×2 pivots inside each supernode and delayed pivots, for the unregularized augmented system.

§Purpose

SupernodalLdl implements KktSolver with no dependency: a supernodal LDLᵀ of P K̃_reg Pᵀ written here, generic in the scalar T: Real, with the dense arithmetic of its blocks delegated to a DenseKernel (NaiveDense always, FaerDense with the faer feature, Chapter 5.16). What it shares with every backend is the trait’s: the ordering (any Ordering, our crate::Amd by default), the regularization policy and the inertia check (Algorithm K of Chapter 5.14), the refinement (Algorithm F). What is new here is the symbolic phase (elimination tree, relaxed supernodes, the row pattern of every supernode and the scatter map of K), the numeric phase (left-looking supernodal elimination with the pivot bumping of step K3 and an exact count of the bumped pivots of both signs) and the solves, which allocate nothing.

Why left-looking. CHOLMOD (Chen, Davis, Hager & Rajamanickam 2008, §2.3) and faer 0.24 (read, not copied) both factorize supernode by supernode in postorder, each one receiving the updates of its descendants before it is factorized (“left-looking”); the alternative, multifrontal, carries a stack of dense frontal matrices whose peak memory can exceed the factor’s by a large factor on wide trees (Liu 1992), while left-looking needs only the factor and three scratch blocks. With the same supernodes the two do the same flops; the choice is memory and simplicity, and the CHOLMOD paper reports no systematic speed advantage of either on its test set.

§Notation

As in Chapters 5.14–5.15: K of order N by its lower triangle, L₀ the analyzed lower pattern with a full diagonal, π the ordering (Perm, fwd[k] = the row eliminated k-th), σ_k the pivot signs, (ρ, δ, τ, β) the regularization, K̃_reg = S K S + Σ the equilibrated regularized matrix of step K2″ whose factor P K̃_reg Pᵀ = L Δ Lᵀ is computed, L unit lower triangular, Δ = diag(d_k). Columns are in the permuted numbering 0..N unless said otherwise. The elimination tree has parent[j] (Chapter 5.9, Algorithm E) and column counts c_j (entries of column j of L, diagonal included).

A supernode s is a run of consecutive columns [s₀, s₁) whose columns of L have nested patterns: the pattern of column j ∈ s below the diagonal block is the same set R_s of deg(s) = c_{s₁−1} − 1 rows, all ≥ s₁. Its block of L is stored dense, column-major, as a DenseBlock of nrows(s) = ncols(s) + deg(s) rows and ncols(s) = s₁ − s₀ columns: row i < ncols(s) is column s₀ + i, row ncols(s) + q is the row R_s[q]; the diagonal of the block holds Δ (the unit diagonal of L is implicit) and the strict upper triangle of the diagonal block is never read. A fundamental supernode has exactly nested patterns; a relaxed one merges a child into its parent at the price of explicit zeros (entries stored where the fundamental structure has none).

§Algorithm A (Analyze)

A1. L₀ ← the lower triangle of the pattern plus a full diagonal (invariant (K1) of Chapter 5.14; KktError::NotSymmetric or KktError::Structure otherwise); G ← L₀ + L₀ᵀ. A2. π ← ordering.order(G, Symmetric) (its length checked). A2′. π ← the postorder of the elimination tree of π with the heaviest child last (Algorithm P of Chapter 5.9): every subtree is a run of consecutive columns, so every chain of only children is a candidate supernode, and the largest child sits right before its parent, where step A4 can merge it. A3. (parent, c) ← Algorithm E on G under π (the tree and the column counts); nchild[j] the number of children of j. A3′. [Switch.] φ = Σ_j c_j + Σ_j c_j(c_j+1)/2 (the divisions and multiply-subtracts of the LDLᵀ) and ℓ = Σ_j c_j; if φ ≤ supernodal_switch · ℓ (SupernodalOptions, default 40 as CHOLMOD’s supernodal_switch and faer’s AUTO) the matrix is simplicial: A5 keeps the fundamental supernodes and Algorithm N takes the simplicial path everywhere — on such matrices dense blocks only add explicit zeros and copies (measured in L1.6a: fit2p’s augmented system, 16 525 columns in 13 500 supernodes, factorized 2× slower with relaxed blocks than column by column). A4. [Fundamental supernodes.] Column j continues the supernode of j − 1 iff parent[j − 1] = j, nchild[j] = 1 and c_{j−1} = c_j + 1 (Liu, Ng & Peyton 1993); otherwise it starts a new one. Each fundamental supernode f has size(f) columns and deg(f) = c_{last} − 1; its parent in the supernodal tree is the supernode of parent[last]. A5. [Relaxed amalgamation.] Walk the fundamental supernodes in order, keeping a group that starts as {f} and whose top is f. The group (of size columns, top degree deg(f), zeros explicit zeros so far) is merged into f + 1 when f + 1 is the parent of f — the only child adjacent to it, by A2′ — and the rule below accepts; the group then continues with top f + 1. Otherwise the group is closed as one supernode and a new group starts at f + 1. Merging adds z_new = size · (size(f+1) + deg(f+1) − deg(f)) zeros (every column of the child gains the rows of the parent’s block it does not have; the child’s pattern is contained in the parent’s columns and pattern, so the difference is never negative), for a merged supernode of w = size + size(f+1) columns and e = w(w+1)/2 + deg(f+1) · w stored entries in its lower part. With relax_zeros = r (SupernodalOptions), the merge is accepted iff r > 0 and one of: z_new = 0 (nothing is lost); w ≤ r (small supernodes always merge: CHOLMOD’s nrelax[0], faer’s first cutoff); or (zeros + z_new) / e ≤ ζ(w) with ζ = 0.8 for w ≤ 16, 0.1 for w ≤ 48, 0.05 beyond (CHOLMOD’s nrelax[1..]/zrelax defaults, which faer uses too; RELAX_CUTOFFS, compared in integers). r = 0 keeps the fundamental supernodes. The rule is faer’s (read, not copied), so the stored factor of this chapter is the same size as faer’s under the same permutation — a stated acceptance criterion of L1.6a. A6. [Patterns.] For every supernode s in order, R_s is the union, restricted to rows ≥ s₁, of the rows of G in the columns of s and of the patterns R_c of its children c in the supernodal tree (the children come first in postorder); sorted increasing. Invariant (L2): |R_s| = c_{s₁−1} − 1. A7. [Descendants.] For every supernode d and every maximal run of consecutive rows R_d[a..b) that fall in the columns of one supernode s, record (d, a, b) in the list of s: the updates s receives in Algorithm N come from exactly these d, with R_d[a..b) the columns of s they touch and R_d[a..] the rows. A8. [Scatter map.] For every entry p of L₀ (original indices (i, j)), the supernode of min(inv[i], inv[j]) and the offset of the permuted entry in its block: the numeric phase scatters the values of K̃_reg with one indexed store each. A9. [Sizes.] nnz_l = Σ_s nrows(s) · ncols(s), the stored length of the factor (dense blocks, their explicit zeros and the unused strict upper triangles of the diagonal blocks included — the convention of crate::FaerSymbolic::nnz_factor, (F2), so the two backends are comparable). Invariant (L3): the lower parts of the blocks, Σ_s (ncols(s)(ncols(s)+1)/2 + deg(s) · ncols(s)), equal Σ_j c_j (Pattern::cholesky_nnz) plus the zeros counted in A5.

§Algorithm N (Numeric factorization, left-looking supernodal)

N1. v ← the values of K on L₀ (steps K1′–K2 of Chapter 5.14), equilibrated (K2′), plus the static shifts (K2″): v holds K̃_reg. N2. Allocate the blocks of L (zeros) and scatter v into them by the map of A8. The pivot signs in permuted order are σ_{fwd[k]}. N3. For s = 0, 1, … (postorder: every descendant before s): N3a. [Map.] loc[s₀ + i] ← i for the columns of s, loc[R_s[q]] ← ncols(s) + q for its pattern rows. N3b. [Updates.] For every (d, a, b) in the list of s (A7), Algorithm U: L_s ← L_s − L_d[a.., :] Δ_d L_d[a..b, :]ᵀ on the rows and columns loc says, lower part only. N3c. [Factor.] Algorithm D on the block of s: the diagonal block A₁₁ = L₁₁ Δ_s L₁₁ᵀ with the bumping of step K3 under the signs σ of its columns, then L₂₁ ← A₂₁ L₁₁⁻ᵀ Δ_s⁻¹ for the rows of R_s. A zero pivot without dynamic regularization is KktError::ZeroPivot at the original row fwd[k]; a pivot that is not finite is KktError::NotFinite there (an overflow of the elimination is never bumped). N3d. [Unmap.] Reset loc for the rows touched in N3a. N4. [Unscale.] The factor computed is that of P K̃_reg Pᵀ, K̃ = S K S. Since K_reg = S⁻¹ K̃_reg S⁻¹ = (S⁻¹ L S)(S⁻¹ Δ S⁻¹)(S⁻¹ L S)ᵀ, the stored blocks become L̂ = S⁻¹ L S (l̂_ij = l_ij s_j / s_i, unit diagonal kept) and Δ̂ = S⁻¹ Δ S⁻¹ (d̂_k = d_k / s_k²) — exact, the scales being powers of two — so that the solves work in the caller’s units with no scaling pass (the equilibration is kept, NumericLdl::scale, to read the pivots of the equilibrated matrix back: d_k = d̂_k s_k²). N5. (S10) Every stored value of L̂ and Δ̂ is finite, or the call fails with KktError::NotFinite at the original row of the first column holding a NaN or an infinity (step K3′). N6. (S6) The inertia is the count of signs of Δ̂ (= of Δ, step K4; KktError::WrongInertia unless it is the form’s). With τ = Some, every pivot has its sign σ_k by construction and the check cannot fail. The factor also allocates its work vector for Algorithm S (N scalars).

A supernode with fewer than min_supernode_cols columns (SupernodalOptions) takes the simplicial path: steps N3b and N3c run column by column with plain loops (the same arithmetic, in the same order as the kernel path up to the rounding of the sums), and so does an update whose descendant d has fewer than min_supernode_cols columns — a dense kernel on a block one to seven columns wide costs more in copies than it saves. Above the threshold the kernel path gathers the operands into scratch blocks and calls gemm_sub and trsm_lower (DenseKernel). The storage is the same on both paths.

§Algorithm U (Update of s by a descendant d)

With R_d[a..b) the rows of d inside the columns of s, n_m = b − a, n_r = |R_d| − a (the rows of d from a on: they lie in s’s columns or in R_s, by A6): U1. A ← L_d[a.., :] (n_r × ncols(d)), B ← L_d[a..b, :] Δ_d (n_m × ncols(d), the columns scaled by d_k), gathered into scratch blocks (the rows of a column-major block are strided, and a DenseBlock has no stride: the gather is the price of the kernel interface). U2. C ← 0 (n_r × n_m); C ← C − A Bᵀ by gemm_sub. U3. [Scatter.] For j < n_m and i ≥ j: L_s[loc(R_d[a+i]), R_d[a+j] − s₀] += c_ij — the lower part of the update, since R_d is sorted so that i ≥ j is row at or below column. Simplicial path: for k < ncols(d), j ∈ [a, b), i ∈ [j, |R_d|): L_s[loc(R_d[i]), R_d[j] − s₀] −= l_{d,ik} · (d_k l_{d,jk}), column k of L_d read once, contiguous.

§Algorithm D (Dense LDLᵀ of a supernode block, with bumping)

On the block A of s (n_r rows, n_c columns), panels of PANEL columns [p, q): D1. [Tile.] Columns p..q, rows p..q, by the scalar right-looking elimination: for k = p, …, q − 1: d_k ← a_kk; if d_k is not finite, fail (N3c); if τ = Some and σ_k d_k ≤ τ, d_k ← σ_k β and count the bump (step K3); if τ = None and d_k = 0, fail (zero pivot); l_ik ← a_ik / d_k for k < i < q; a_ij ← a_ij − l_ik d_k l_jk for k < j ≤ i < q. D2. [Panel below the tile.] If q < n_r: L₂₁ ← A₂₁ L̃⁻ᵀ with L̃ = L₁₁ Δ₁ (the unit lower tile with its columns scaled by the pivots: lower triangular with diagonal d_k), by trsm_lower(L̃, A₂₁, transpose): row i of A₂₁ solves L̃ x = a_i, i.e. l_ik = (a_ik − Σ_{j<k} l_ij d_j l_kj) / d_k — the formula of D1 for the rows below the tile, with the sums in the kernel’s order. D3. [Trailing update.] If q < n_c: for the remaining columns, in panels [c, c + w): A[c.., c..c+w] ← A[c.., c..c+w] − W[c−q.., :] L₂₁[c−q..c−q+w, :]ᵀ with W = L₂₁ Δ₁, by gemm_sub on gathered blocks — the lower trapezoid of the trailing matrix, one panel at a time (the strict upper triangle of each w × w diagonal tile is computed and discarded: w² ncols wasted flops per panel against n_r w ncols useful ones). For n_c ≤ PANEL there is one tile and no trailing update: the whole supernode is D1 on its diagonal block and D2 for its pattern rows. The simplicial path runs D1 with q = n_r on all the rows and n_c columns (no panels, no kernel).

§Algorithm M (LBLᵀ of the unregularized augmented system)

Task L1.6b. An augmented system without regularization (ρ = 0 or δ = 0, and τ = None: the rule of Chapter 5.15, step N2) is indefinite but not quasi-definite: its dual diagonal is zero, so a dual column that is a leaf of the elimination tree has a pivot that is exactly zero, and a column whose rows depend on the pivots already taken inside its supernode has one that is zero up to rounding. The two regularized systems take Algorithm N as before (they are quasi-definite — Vanderbei 1995 — and need no pivoting; that path is untouched, bit for bit); the unregularized augmented one takes this algorithm, which replaces steps N3b–N3c and the solve.

The pivoting is intranodal — the candidates for a pivot are the columns of the supernode being factorized, the “fully summed” variables of the multifrontal method, whose columns the block holds complete — and the search is Bunch–Kaufman’s (Algorithm B of Chapter 5.16, DenseKernel::sytrf) on the diagonal block. A column that cannot be pivoted there is delayed to the parent supernode (Duff & Reid 1983; MA57, Duff 2004), where its remaining entries lie in any case ((L1): the pattern of a child is contained in the columns and the pattern of its parent), and tries again with more candidates; a column delayed out of a root is a zero pivot of a singular matrix, KktError::ZeroPivot. The structure of Algorithm A does not change: a delayed column adds one column and one row to the block of the parent (explicit zeros where it has no entry) and leaves its row of L behind in the block it came from.

For s = 0, 1, … in postorder, with nc columns and deg = |R_s|: M1. [Receive.] The nd columns delayed into s by its children (step M5) are appended to its columns: the block becomes (nc + nd + deg) × (nc + nd), the own entries keep their places (the pattern rows move down by nd), and each delayed column k brings its diagonal, its entries at the columns delayed after it by the same block (cross terms) and its entries at the pattern rows of that block, scattered by loc. A delayed column needs no update from the descendants of s: it arrives with the updates of its own subtree and of the pivots of the block that delayed it. M2. [Updates.] Step N3b with Algorithm U, where B ← L_d[a..b, :] B_d has B_d block diagonal: for a 2×2 block E = [e₁₁ e₂₁; e₂₁ e₂₂] at the columns k, k+1 of d, B[:, k] = e₁₁ l_k + e₂₁ l_{k+1} and B[:, k+1] = e₂₁ l_k + e₂₂ l_{k+1}; the rows of d are read past its own delayed rows (M6). The largest update any descendant makes to the diagonal of a column of s is kept as that column’s reference scale for M3. M3. [Pivot.] With A₁₁ the diagonal block of the w = nc + nd active columns: P A₁₁ Pᵀ = L₁₁ B₁ L₁₁ᵀ by sytrf on a copy. A 1×1 pivot d with |d| ≤ ζ m_j, or a 2×2 block whose three entries are all ≤ ζ max(m_j, m_{j'}) (ζ = SupernodalOptions::zero_pivot_tol, default 10⁻¹⁴: a relative test, so that a pivot that is zero up to the rounding of the sum that produced it is caught, and a pivot that is merely small — the 10⁻¹⁰ of a primal column at the end of an interior-point method — is kept, as in Algorithm N), is a zero pivot: its columns are removed from the active set and M3 is repeated on the rest (a zero column of the Schur complement contributes nothing to the other pivots: the repetition only drops it). w = 1 is the direct case, d = a₀₀ against the scale it carries. Without a parent, a zero pivot is KktError::ZeroPivot at the original row of its column: nothing is left to pair it with, and the matrix is singular to working precision (measured on the Netlib systems: taking such a pivot instead gave factors with the expected inertia and residuals of 10¹⁵, a silent failure); a pivot that is not finite is KktError::NotFinite there. The reference scale m_j is the largest term of the sums that produced the pivot — its diagonal as the block holds it and the largest update a descendant made to it (M2: a dual column coupled only to pairs below it receives updates that cancel to rounding noise, and the noise must not pass for a pivot); for a column delayed into this block, the scale it was flagged with where it came from and the terms of the Schur complement step M5 formed for it (a carried diagonal that is already rounding noise must not be judged against itself); and the terms l_jk b_k l_jk of the pivots k before it in the block. Measured on the random systems of the tests: without the carried scale a dual leaf whose diagonal arrived as 3·10⁻¹⁶ was taken as a pivot and the factor was wrong by 10⁻². The scale is a bound on the rounding noise of the sum, not an uncertainty propagated through the pivots: a version that let a pivot hand its own scale to what it updates compounded the scales to 10⁶⁵ on stair (Netlib) and flagged a pivot of 1.27 as zero; the one case that needed the propagation — a pivot of 5·10⁻¹⁹ beside terms of 10⁻¹⁸, the residue of a 2×2 block with one noise diagonal — is caught by the growth test of M4 instead. M4. [Rows.] The rows below the diagonal block — the nz columns removed in M3, as rows, then R_s — are gathered in the order of P and solved: U ← A₂₁ L₁₁⁻ᵀ by trsm_lower against the unit L₁₁ (its diagonal written as ones, the slots of e₂₁ as zeros), then L₂₁ ← U B₁⁻¹ column by column: / d for a 1×1 pivot, [x y] E⁻¹ for a 2×2 one. [Growth.] A pivot whose column of L₂₁ has an entry above 1/u (u = SupernodalOptions::pivot_threshold, default 10⁻⁸) is removed like a zero pivot and M3 repeats without it: the row of the large entry is a candidate partner in the parent, where it is fully summed — the threshold partial pivoting of MA57 among the fully summed variables, with Ipopt’s lax u. Without it a pivot small inside its block but not zero (a 2×2 block with a small e₂₁, stable by Bunch–Kaufman’s test on the block alone) made L₂₁ grow to 10⁷ and every pivot below it rounding noise (ganges, Netlib: a pivot of 0.70 with an error of 0.07); u = 10⁻² (MA57’s default) delays so much in the middle of an interior-point method that one Netlib system (woodw, augmented) did not finish in six minutes, and u = 10⁻⁴ sits in between (tables in the decision log). M5. [Delay.] Each removed column k goes to the parent with its reference scale — raised to |a_kk| and to the largest term of l_k · u_k: the pivots the block took after k was flagged may cancel in that sum (two singleton rows of A on one column: the second, flagged with an exact zero and scale 0, got b² − (ab)²/a² = 4·10⁻¹⁶ from the pivots of the first and was taken at the root with the expected inertia; 0.3.1) — and its Schur complement after the active pivots: a_kk − l_k · u_k, the cross terms a_{k'k} − l_{k'} · u_k with the removed columns k' after it, and a_{rk} − l_r · u_k for r ∈ R_s (l the rows of L₂₁, u the rows of U: l_r B₁ l_kᵀ = l_r · u_k). Its row l_k stays in the block of s for the solve. M6. [Record.] The block of s is (w' + nz + deg) × w' (w' = w − nz pivots in the order of P, then the nz delayed rows, then R_s): L₁₁ with B₁ on its diagonal and e₂₁ at (k+1, k) — the slot where L has an implicit zero, the convention of DenseKernel::sytrf — and L₂₁ below. The pivots take the next w' positions of the pivot order: fwd′, diag and pivot_2x2 (true on both columns of a 2×2 block) are indexed by it, and pos[j] records where the analyzed column j was eliminated. Then steps N4–N6 as before (e₂₁ is an entry of Δ: ê₂₁ = e₂₁ / (s_k s_{k+1}); the inertia counts +1 −1 for a 2×2 block with det E < 0, step K4), and the rows of every block are remapped by pos for the solve. NumericLdl::perm is fwd′, NumericLdl::supernodes the block boundaries in pivot order, NumericLdl::rows the rows of a block below its diagonal block, NumericLdl::delayed the number of delays.

The simplicial structure takes the same steps: a supernode of one column is the direct case of M3, and its pivot is zero iff exactly zero — then it is delayed, never ignored (the simplicial LBLᵀ of faer accepts a zero pivot in silence and its solve returns infinities, D-0094; here the unregularized factorization of a nonsingular matrix either succeeds or fails with the row named). Why the leaf is not merged with its parent in the symbolic phase instead: the symbolic phase does not know the regularization, the regularized systems would pay the explicit zeros, and a leaf is adjacent to its parent only when it is the heaviest child; the numeric delay costs one row and one column of a block per delayed pivot, only when it happens.

Growth and the end of an interior-point method. The threshold test of M4 delays every primal pivot below u relative to its column — near the end of the method, where D reaches 10⁻¹⁰, that is half of them, and the delays pile up at the root (up to 15 352 in one Netlib system). There the unregularized augmented system is singular to working precision anyway (κ > 10¹² in 93 of 93 Netlib systems of the end regime, by the scipy oracle of L1.5), and the regularized path, which lives with the growth and whose refinement handles it (Chapter 5.14, L1.5b), is the one to use. The refinement of Algorithm F is the safeguard here too, and (S10) still refuses a factor with an infinity.

§Algorithm S (Solve)

y ← P x gathered into the factor’s work vector (y_k = x_{fwd[k]}; a second thread solving with the same factor at the same moment uses a temporary vector instead of waiting — the mutex of task L1.5b, D6; an in-place permutation by cycles was measured first and rejected: following a cycle is a chain of dependent loads, twice slower than the gather on the 16 525 unknowns of fit2p’s augmented system). Then, supernode by supernode: S1. [Forward, L̂ y = y.] For s in order, for each column j of s: y_i ← y_i − l̂_ij y_j for the rows i of the diagonal block below j (a contiguous axpy) and for the rows R_s (a scatter; column j of the block read once). S2. [Diagonal.] y_k ← y_k / d̂_k. S3. [Backward, L̂ᵀ y = y.] For s in reverse order and j from the last column of s down: y_j ← y_j − Σ_{i>j in s} l̂_ij y_i − Σ_q l̂_{R_s[q], j} y_{R_s[q]}: two dot products with the same column, each summed in four independent partial sums (a single accumulator makes the sweep latency-bound: 2× slower on maros-r7’s normal equations, measured in L1.6a) and combined in a fixed order. A supernode of one column takes the plain loops of a column-oriented simplicial solve. Finally x_{fwd[k]} ← y_k. Nothing is allocated while the work vector is free (invariant (L5)); the factor is read only.

§Algorithm S′ (Solve with the LBLᵀ factor)

Algorithm S with: y ← P′ x by fwd′; the blocks walked by their pivot ranges and their remapped rows (delayed rows, then R_s); in S1 and S3 the slot (k+1, k) of a 2×2 block is skipped (it holds e₂₁, not an entry of L); S2 runs block by block right after S1 (the pivots of a block are final once its forward step is done), and a 2×2 block solves E [y_k; y_{k+1}] = [b_k; b_{k+1}] by Cramer’s rule. Nothing is allocated (L5); the pivot pairs never cross a block (L8).

§Invariants

(L1) The supernodes partition 0..N into runs in increasing order; R_s is sorted, its rows are ≥ s₁, and every row of R_s lies in the columns of an ancestor of s. (L2) |R_s| = c_{s₁−1} − 1 (the pattern of the last column, Liu 1990). (L3) Σ_s (ncols(ncols+1)/2 + deg · ncols) = Σ_j c_j + zeros(A5): the stored lower parts are the structural factor plus the counted zeros of the relaxation; with relax_zeros = 0, exactly Pattern::cholesky_nnz. (L4) Every (d, a, b) of A7 has d < s, R_d[a..b) ⊆ [s₀, s₁) and R_d[b..] ⊆ R_s. (L5) KktSolver::solve allocates nothing (its work vector belongs to the factor) and reads the factor only. (L6) The factorization is a deterministic function of its inputs: no threads, no hashing, the same operations in the same order — two factorizations of the same matrix are equal bit for bit. (L7) In the LBLᵀ path the pivot ranges of the blocks partition 0..N, fwd′ is a permutation, and every analyzed column is eliminated exactly once (pos is a permutation of 0..N). (L8) A 2×2 block lies inside one block of pivots (intranodal): pivot_2x2[k] = true comes in pairs (k, k+1), k+1 in the same block. (L9) A delayed column is received by the parent supernode of the block that delayed it and nowhere else; its row of L stays in that block. (S6), (S10) as in Chapter 5.14, checked in steps N4–N5 and asserted in debug builds. SymbolicLdl::check_invariants checks (L1)–(L4); the L1.6a harness checks (L5) with a counting allocator (0 allocations in a second solve and in a refined solve with a reused workspace), the tests check (L6) by comparing two factors.

§What was read

CHOLMOD (Chen, Davis, Hager & Rajamanickam 2008: §2.2 analyze, §2.3 the supernodal left-looking numeric phase and its relaxed amalgamation parameters nrelax, zrelax); faer 0.24.4 sparse::linalg::cholesky::supernodal (the fundamental-supernode test, the merge rule on adjacent children, the storage of a supernode as one column-major block with Δ on its diagonal, the per-supernode row structure that drives the left-looking updates) and amd::postorder; Liu, Ng & Peyton 1993 (supernodes), Ng & Peyton 1993 (left-looking supernodal), Liu 1992 (multifrontal memory) — read, not copied.

For Algorithm M (L1.6b): Duff & Reid 1983 (delayed pivots in the multifrontal method), Duff 2004 (MA57: the threshold test among the fully summed variables, the treatment of delays), Vanderbei 1995 (quasi-definite matrices factorize with 1×1 pivots in any order: why the regularized path needs none), faer 0.24.4 linalg::cholesky::bunch_kaufman::factor (read to confirm that a column with no off-diagonal entry is taken as a 1×1 pivot without elimination, which is what M3 relies on from sytrf) — read, not copied.

§References

See Chapter 5.14; Chen, Davis, Hager & Rajamanickam, “Algorithm 887: CHOLMOD”, ACM TOMS 35(3), 2008; Liu, Ng & Peyton, “On finding supernodes for sparse matrix computations”, SIAM J. Matrix Anal. Appl. 14(1), 1993; Ng & Peyton, “Block sparse Cholesky algorithms on advanced uniprocessor computers”, SIAM J. Sci. Comput. 14(5), 1993; Liu, “The multifrontal method for sparse matrix solution: theory and practice”, SIAM Review 34(1), 1992; Liu, “The role of elimination trees in sparse factorization”, SIAM J. Matrix Anal. Appl. 11(1), 1990; Davis, Direct Methods for Sparse Linear Systems (2006), ch. 4; Ashcraft & Grimes, “The influence of relaxed supernode partitions on the multifrontal method”, ACM TOMS 15(4), 1989 (relaxed amalgamation); Duff & Reid, “The multifrontal solution of indefinite sparse symmetric linear systems”, ACM TOMS 9(3), 1983; Duff, “MA57 — a code for the solution of sparse symmetric definite and indefinite systems”, ACM TOMS 30(2), 2004; Vanderbei, “Symmetric quasi-definite matrices”, SIAM J. Optim. 5(1), 1995; Bunch & Kaufman, “Some stable methods for calculating inertia and solving symmetric linear systems”, Math. Comp. 31, 1977.

Structs§

NumericLdl
The numeric factor of SupernodalLdl: P K_reg Pᵀ = L̂ Δ̂ L̂ᵀ with L̂ by blocks (column-major, Δ̂ on the diagonal, the unit diagonal of L̂ implicit), in the caller’s units (step N4). For the LDLᵀ of Algorithm N (both regularized systems) Δ̂ is diagonal, the blocks are the symbolic supernodes and P is SymbolicLdl::perm. For the LBLᵀ of Algorithm M (the unregularized augmented system) Δ̂ has 2×2 blocks — pivot_2x2 true on both their columns, e₂₁ stored in the block at the slot (k + 1, k) where L̂ has an implicit zero —, P is the pivot order NumericLdl::perm, and the blocks’ pivot ranges and rows are NumericLdl::supernodes and NumericLdl::rows (delayed pivots move columns between blocks).
SupernodalLdl
Our own supernodal LDLᵀ (D10; Chapter 5.17): analyze (ordering, elimination tree, relaxed supernodes, pattern of L), factorize (left-looking supernodal with the dense kernel K on the diagonal and update blocks, pivot bumping with the expected signs, regularization policy of Chapter 5.14), solve (block forward/diagonal/backward sweeps without allocation). Generic in the scalar T; K is NaiveDense by default and FaerDense with the faer feature.
SupernodalOptions
Options of the supernodal factorization (steps A5 and N3).
SymbolicLdl
The symbolic factor of SupernodalLdl (Algorithm A): permutation, elimination tree, supernode partition and the row pattern of every supernode, plus (private) the scatter map of K and the descendant lists of the left-looking numeric phase.

Constants§

PANEL
Panel width of Algorithm D (a blocking size for the dense kernels, not a numerical threshold).
RELAX_CUTOFFS
Step A5: the largest fraction of explicit zeros a relaxed supernode of at most the given number of columns may hold, in per mille — CHOLMOD’s nrelax[1..3]/zrelax defaults (16: 0.8, 48: 0.1, else 0.05), which faer 0.24 uses too. The first cutoff (always merge up to relax_zeros columns) is SupernodalOptions::relax_zeros.