Expand description
§Chapter 11.7 — DdDense: the dense kernel of xingo-sparse in double-double
§Purpose
xingo_sparse::SupernodalLdl<T, K> spends its time in the dense
operations of a DenseKernel<T> (Chapter 5.16 of xingo-sparse). For
T = DoubleDouble the only kernel so far was the generic
NaiveDense, one scalar double-double operation at a time. DdDense
is the same kernel with its inner loop — the column update of
Chapter 11.5, step B3 — on vector registers (Chapter 11.6). It returns
the bits of NaiveDense, so a factorization does not change when
the kernel is swapped; only its speed does.
§Notation
As in Chapter 5.16: a DenseBlock A is rows × cols, column-major;
square blocks are read and written in their lower triangle. c ← c ⊖ a ⊗ t is the column update of Chapter 11.5 (c, a columns of equal
length, t a double-double), ⊘ the division D2 of Chapter 11.2.
§Algorithm K (the five operations)
K1. [gemm_sub: C ← C − A Bᵀ.] Step B3 of Chapter 11.5 with t(j, l) = b_jl, in its blocks: for each entry, l increasing.
K2. [syrk_sub: C ← C − A Aᵀ, lower triangle.] For l in blocks of
BLOCK_K, for each column j of C: the column update of the
rows i ≥ j with a = A[j.., l] and t = a_jl.
K3. [trsm_lower, B ← B L⁻ᵀ.] For j = 0, …, n − 1: for l < j,
the column update of column j of B with a = column l of B
(already solved) and t = l_jl; then b_ij ← b_ij ⊘ l_jj.
K4. [trsm_lower, B ← L⁻¹ B.] For each column c of B, for l = 0, …, n − 1: x ← b_lc ⊘ l_ll, b_lc ← x, then the column update
of the rows below l with a = L[l + 1.., l] and t = x.
K5. [potrf, left-looking (Algorithm P of Chapter 5.16 since
xingo-sparse 0.4.0).] For j = 0, …, n − 1: for k < j, the
column update of the rows i ≥ j of column j with a = L[j.., k] and t = l_jk; then the pivot test and l_jj ← √a_jj of
NaiveDense, and l_ij ← a_ij ⊘ l_jj for i > j.
K6. [sytrf.] That of NaiveDense, unchanged: its eliminations
update a full working copy row and column at once, and the block
factorization is not where the supernodal factorization spends its
time.
K7. [solve_unit_lower, Algorithm V of Chapter 5.16.] For j = 0, …, n_c − 1: the column update of y[o..] with a = L[o.., j] and
t = y_j.
K8. [solve_unit_lower_t, Algorithm W.] For j = n_c − 1, …, 0:
y_j ← y_j ⊖ (D(L[o..n_c, j], y[o..n_c]) ⊕ D(L[n_c.., j], y[n_c..])), with D the kernel dot4 of Chapter 11.5 (step B4)
on SIMD registers (step W2 of Chapter 11.6).
K9. [solve_min_rows.] SOLVE_MIN_ROWS: the supernodes of
SupernodalLdl with at least that many rows are solved through
K7–K8 (step S0′ of Chapter 5.17), the others by the generic loops.
A cost switch (invariant (D5) of Chapter 5.16): the bits are the
same either way.
Task L1.8. Until xingo-sparse 0.3.x the generic potrf summed each
entry along a row of L (Σ_k l_ik l_jk, left to right, subtracted
once), which lanes would reorder, so it was NaiveDense’s here too;
0.4.0 subtracts term by term down a column, the statement of K1–K4, and
K5 vectorizes it with the same bits.
K1–K5, K7 are the loops of NaiveDense (Chapter 5.16, “Loop order”), which
compute each entry as x ← x − a · t with the same operands in the
same order; the column update is that statement for a whole column, and
it is bit for bit the scalar one (invariant K1 of Chapter 11.5). The
product is a ⊗ t with the entry of the column first: the
double-double product M2 is not commutative in its last bits, so the
order of the operands is part of the definition.
§What the contract said
The approved contract describes DdDense as “potrf, sytrf and the
triangular solves are those of NaiveDense; gemm_sub and syrk_sub
go through kernels::gemm_sub”. Two differences, neither visible in a
result: the triangular solves also use the vectorized column update
(their results are still NaiveDense’s, bit for bit), because the
supernodal factorization calls trsm_lower once per panel; and
gemm_sub/syrk_sub go through the column update of
kernels::gemm_sub rather than through that function, whose B is
k × n where the trait’s is n × k (transposed).
§Invariants
(X1) Same bits. Every operation of DdDense leaves in its output
block the bits NaiveDense would (NaN payloads aside, invariant K1
of Chapter 11.5). Tested entry by entry on random blocks, and on
whole factorizations in tests/sparse_dd.rs.
(X2) (D3) of Chapter 5.16: the strict upper triangle of a square block
is untouched.
(X3) Same bits in the solve (task L1.8): K7–K8 return the bits of the
provided solve_unit_lower, solve_unit_lower_t of
DenseKernel — (D4) of Chapter 5.16 — so SupernodalLdl solves to
the same bits with DdDense as with NaiveDense, whatever
SOLVE_MIN_ROWS is. Tested on blocks and on whole solves in
tests/sparse_dd.rs.
§References
Chapter 5.16 of xingo-sparse (DenseKernel, NaiveDense: the loop
order and the cache blocks); Chapters 11.5 and 11.6.
Structs§
- DdDense
- The dense kernel of
xingo-sparsefor double-double blocks, with the results ofNaiveDensebit for bit (Chapter 11.7):gemm_sub,syrk_suband the triangular solves run the column update ofcrate::kernels::gemm_subon SIMD registers (featuresimd), and so doespotrf(left-looking sincexingo-sparse0.4.0);sytrfis that ofNaiveDense. With itSupernodalLdl<DoubleDouble, DdDense>spends its time in SIMD.
Constants§
- SOLVE_
MIN_ 🔒ROWS - Step K9: the smallest supernode block, in rows, that the solves of
SupernodalLdl<DoubleDouble, DdDense>send through K7–K8 (a cost switch). Measured in task L1.8 withdd_bench ldl(NEON, Apple M2):1,8and32within the noise of each other on the four systems (2-D grid simplicial and forced supernodal, 3-D grid, dense 200), all 1.3–1.8× faster than the generic loops;8keeps the gather out of the smallest blocks.
Functions§
- check_
solve 🔒 - The argument checks of K7–K8 (those of the provided methods).
- is_
consistent 🔒 rows · colsentries.- potrf_
columns 🔒 - Step K5 (the error of a non-positive pivot is
NaiveDense’s). - solve_
backward 🔒 - Step K8, with the kernel
dotof step B4. - solve_
forward 🔒 - Step K7.
- solve_
offset 🔒 o = j + 1 + [skip_j]of Algorithms V and W of Chapter 5.16.- square 🔒
- The order of a consistent square block.
- syrk 🔒
- Step K2.
- trsm_
plain 🔒 - Step K4.
- trsm_
transposed 🔒 - Step K3.