symm — symmetric matrix–matrix product

symm computes C := βC + αAB for a symmetric A = Aᵀ stored as a single triangle. Numerically it is gemm; the interest is the symmetric-storage confluence — symv’s two-face feed, now on gemm’s 3-D reduction cube.

The SURE

The operand a carrying A(i,k) reads the stored triangle two ways: the lower cells (k ≤ i) read the stored A[i][k], the upper cells (i < k) read the reflected A[k][i]. So cell (i,j,k) always sees A_sym(i,k) and the rest is the ordinary gemm sweep (B along +i, α/β projected, βC epilogue).

system ((i,j,k) | 0 <= i < M, 0 <= j < N, 0 <= k < K) {
    a(i,j,k)     = a(i,j-1,k);                                          // A_sym(i,k) along +j
    b(i,j,k)     = b(i-1,j,k);                                          // B(k,j) along +i
    alpha(i,j,k) = alpha(i,j,k-1);  beta(i,j,k) = beta(i-1,j,k);  cin(i,j,k) = cin(i,j,k-1);
    c(i,j,k)     = c(i,j,k-1) + alpha(i,j,k-1)*a(i,j-1,k)*b(i-1,j,k);
}
// A feeds on TWO faces of one stored triangle:
input a(i,j,k) = A[i][k]   on  k <= i    // lower: the stored element
input a(i,j,k) = A[k][i]   on  i <  k    // upper: the reflected element
output C[i][j] = c(i,j,K-1) + beta*cin;

Executable spec: docs/SURE/symm.sure. For the reduction + epilogue see gemm; for the symmetric-storage confluence see symv.

Schedule

Box domain, so the canonical τ = [1,1,1] is legal, as is the free schedule. The wavefront sweeps the (i,j,k) cube exactly as gemm.

Reduced dependency graph

The reduced dependency graph (RDG) draws the recurrence as one node per variable and one arc per dependence, each annotated with its translation vector θ. symm (C := αAB + βC, A symmetric) has the same six-node reduction-cube structure as gemm — the symmetry is in the two-face read of A’s stored triangle, not in the dependence graph:

arc	θ	dependence
`c → c`	`[0,0,1]ᵀ`	the reduction chains along `+k`
`a → c`	`[0,1,0]ᵀ`	`A(i,k)` enters the product
`b → c`	`[1,0,0]ᵀ`	`B(k,j)` enters the product
`alpha → c`	`[0,0,1]ᵀ`	α enters the product
`a → a`	`[0,1,0]ᵀ`	`A` pipelined along `+j`
`b → b`	`[1,0,0]ᵀ`	`B` pipelined along `+i`
`alpha → alpha`, `cin → cin`	`[0,0,1]ᵀ`	α and the incoming `C` on the feed face
`beta → beta`	`[1,0,0]ᵀ`	β projected on its face

Every arc is a translation vector, so symm is a genuine SURE.