Expand description
§Chapter 5.16 — Dense kernels for supernodal blocks
New with task L1.5 (PLAN.md trilha L; the contract’s §5.8, decision Q4).
§Purpose
A supernodal factorization (L1.6, SupernodalLdl) spends its time in a
handful of dense operations on the blocks of L: factorize a diagonal
block, solve the block below it against that factor, and subtract the
products into the blocks of the ancestors. DenseKernel names them
with their BLAS/LAPACK names (potrf, sytrf, trsm, gemm, syrk)
so a backend can be swapped without touching the sparse code:
NaiveDense — straightforward loops, generic in T, always available,
the oracle of the others — and FaerDense (feature faer), faer’s
optimized f64 kernels. A scalar type other than f64 (the
double-double of xingo-extprec) uses NaiveDense.
§Notation
A DenseBlock A is rows × cols, column-major: a_ij = data[i + j·rows]. Square blocks are read and written in their lower
triangle only (the strict upper triangle is left untouched), like
LAPACK with uplo = 'L'. For DenseKernel::sytrf, P A Pᵀ = L B Lᵀ
with P a permutation (Perm, fwd[k] = the original index placed
k-th), L unit lower triangular and B block diagonal with 1×1
and 2×2 blocks; α = (1 + √17)/8 ≈ 0.6404 is Bunch & Kaufman’s
constant, which minimizes the bound on element growth.
§Algorithm P (potrf, Cholesky by columns)
For j = 0, …, n − 1: d ← a_jj − Σ_{k<j} l_jk²; if d ≤ 0 (or not
finite) fail with DenseError::NotPositiveDefinite at j;
l_jj ← √d; for i > j, l_ij ← (a_ij − Σ_{k<j} l_ik l_jk) / l_jj.
§Algorithm B (sytrf, Bunch–Kaufman partial pivoting)
On a working copy W of the symmetric matrix, k ← 0; while k < n:
B1. λ ← max_{i>k} |w_ik|, r its first row index. If λ = 0, the
column is already eliminated: a 1×1 pivot w_kk (possibly zero).
B2. Else if |w_kk| ≥ α λ: 1×1 pivot at k.
B3. Else σ ← max_{i≥k, i≠r} |w_ir|: if |w_kk| σ ≥ α λ², 1×1 at
k; else if |w_rr| ≥ α σ, swap r into position k and take a
1×1 pivot; else swap r into position k + 1 and take the 2×2
pivot E = W[k..k+2, k..k+2].
B4. A swap exchanges rows and columns of W, the rows of the computed
columns of L, and the entries of P.
B5. Eliminate: 1×1 — l_ik ← w_ik / w_kk and W ← W − l d lᵀ on the
trailing block; 2×2 — [l_ik, l_i,k+1] ← [w_ik, w_i,k+1] E⁻¹ and
W ← W − [w_k w_k+1] E⁻¹ [w_k w_k+1]ᵀ; advance k by 1 or 2.
Output in A: B’s diagonal on the diagonal, the off-diagonal of each
2×2 block at (k + 1, k) (where L has an implicit zero), L below;
pivot_2x2[k] = pivot_2x2[k + 1] = true for a 2×2 block. The inertia
is that of B (Sylvester; Chapter 5.14, step K4).
§Algorithms T, G, S (trsm_lower, gemm_sub, syrk_sub)
trsm_lower(L, B, false): B ← L⁻¹ B by forward substitution, column
by column of B; trsm_lower(L, B, true): B ← B L⁻ᵀ, i.e. the rows
of B solved against L (the “solve the block below the diagonal”
step of a left-looking Cholesky). L is non-unit lower triangular (the
output of potrf). gemm_sub(A, B, C): C ← C − A Bᵀ. syrk_sub(A, C): C ← C − A Aᵀ on the lower triangle of C. Sums run over k in
increasing order.
Loop order of NaiveDense (task L1.6b). The first edition summed
each entry of the result in place (c_ij ← c_ij − Σ_k a_ik b_jk), which
reads A across its rows — a stride of rows between consecutive k
— and made SupernodalLdl<f64, NaiveDense> 14× slower than faer’s
kernels on dfl001 (D-0099). The kernels now run their innermost loop
down one column (contiguous: an axpy on the column of C with the
column k of A scaled by b_jk), in blocks of GEMM_BLOCK_ROWS
rows and GEMM_BLOCK_K columns of A so that the block of A in
use stays in cache while every column of C passes over it. No SIMD
and no unsafe: plain slices, which the compiler vectorizes. The
additions still run over k in increasing order, so the result is
deterministic; its rounding differs from the first edition’s (the sum
is accumulated into c_ij instead of formed apart and subtracted once).
§Invariants
(D1) After potrf, L Lᵀ = A (lower triangle) to working precision.
(D2) After sytrf, P A Pᵀ = L B Lᵀ to working precision, B has
only 1×1 and 2×2 blocks, every 2×2 block has a negative
determinant or is indefinite-safe (|e_21| ≥ λ > 0), and the
returned inertia sums to n. Checked by the tests against the
reconstruction and against NaiveDense vs FaerDense.
(D3) Every kernel leaves the strict upper triangle of a square block
untouched.
§References
Bunch & Kaufman, “Some stable methods for calculating inertia and
solving symmetric linear systems”, Math. Comp. 31, 1977; Golub & Van
Loan, Matrix Computations, 4th ed. 2013, §4.2 and §4.4; Higham,
Accuracy and Stability of Numerical Algorithms, 2nd ed. 2002, ch.
10–11; LAPACK dpotrf/dsytrf/dtrsm/dgemm/dsyrk (interfaces,
read); faer 0.24.4 linalg::{cholesky, triangular_solve, matmul} (the
API, read, not copied).
Structs§
- Dense
Block - A column-major dense block:
a_ij = data[i + j·rows]. - Faer
Dense - faer’s dense kernels (
f64only in v0.1; extended types useNaiveDense).sytrfuses faer’s Bunch–Kaufman with partial pivoting, whose pivot choices may differ fromNaiveDense’s in ties: both satisfy (D2). - Naive
Dense - Reference kernels: straightforward loops, always available, the oracle of the others in tests.
Constants§
- GEMM_
BLOCK_ K - Columns of
A(the summation indexk) per block; seeGEMM_BLOCK_ROWS. - GEMM_
BLOCK_ ROWS - Rows of
CandAhandled per block inNaiveDense::gemm_subandNaiveDense::syrk_sub(a cache-blocking size, not a numerical threshold):GEMM_BLOCK_ROWS × GEMM_BLOCK_Kentries ofA— 128 KiB inf64— stay in cache while the columns ofCpass over them.
Traits§
- Dense
Kernel - The kernels a supernodal factorization needs (BLAS-3 names kept for recognizability). Square blocks are read and written in their lower triangle (invariant (D3)).