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§
- Numeric
Ldl - The numeric factor of
SupernodalLdl:P K_reg Pᵀ = L̂ Δ̂ L̂ᵀwithL̂by blocks (column-major,Δ̂on the diagonal, the unit diagonal ofL̂implicit), in the caller’s units (step N4). For theLDLᵀof Algorithm N (both regularized systems)Δ̂is diagonal, the blocks are the symbolic supernodes andPisSymbolicLdl::perm. For theLBLᵀof Algorithm M (the unregularized augmented system)Δ̂has2×2blocks —pivot_2x2true on both their columns,e₂₁stored in the block at the slot(k + 1, k)whereL̂has an implicit zero —,Pis the pivot orderNumericLdl::perm, and the blocks’ pivot ranges and rows areNumericLdl::supernodesandNumericLdl::rows(delayed pivots move columns between blocks). - Supernodal
Ldl - Our own supernodal
LDLᵀ(D10; Chapter 5.17): analyze (ordering, elimination tree, relaxed supernodes, pattern ofL), factorize (left-looking supernodal with the dense kernelKon 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 scalarT;KisNaiveDenseby default andFaerDensewith thefaerfeature. - Supernodal
Options - Options of the supernodal factorization (steps A5 and N3).
- Symbolic
Ldl - The symbolic factor of
SupernodalLdl(Algorithm A): permutation, elimination tree, supernode partition and the row pattern of every supernode, plus (private) the scatter map ofKand 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]/zrelaxdefaults (16: 0.8,48: 0.1, else0.05), which faer 0.24 uses too. The first cutoff (always merge up torelax_zeroscolumns) isSupernodalOptions::relax_zeros.