Skip to main content

Module dense

Module dense 

Source
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§

DenseBlock
A column-major dense block: a_ij = data[i + j·rows].
FaerDense
faer’s dense kernels (f64 only in v0.1; extended types use NaiveDense). sytrf uses faer’s Bunch–Kaufman with partial pivoting, whose pivot choices may differ from NaiveDense’s in ties: both satisfy (D2).
NaiveDense
Reference kernels: straightforward loops, always available, the oracle of the others in tests.

Constants§

GEMM_BLOCK_K
Columns of A (the summation index k) per block; see GEMM_BLOCK_ROWS.
GEMM_BLOCK_ROWS
Rows of C and A handled per block in NaiveDense::gemm_sub and NaiveDense::syrk_sub (a cache-blocking size, not a numerical threshold): GEMM_BLOCK_ROWS × GEMM_BLOCK_K entries of A — 128 KiB in f64 — stay in cache while the columns of C pass over them.

Traits§

DenseKernel
The kernels a supernodal factorization needs (BLAS-3 names kept for recognizability). Square blocks are read and written in their lower triangle (invariant (D3)).