Skip to content

Triangular-output products and congruences

#include <mtl/operation/gemmt.hpp>
// One triangle of C = alpha A B + beta C, mirrored to the other
mtl::gemmt(alpha, A, B, beta, C); // lower, mirrored
mtl::gemmt(alpha, A, B, beta, C, mtl::uplo::upper);
mtl::gemmt(alpha, A, B, beta, C, mtl::uplo::lower, mtl::gemmt_fill::keep);
// C = A P A^T, P symmetric; A dense or compressed2D
mtl::congruence(A, P, C);
mtl::congruence(alpha, A, P, beta, C); // C = alpha A P A^T + beta C
// A diagonal middle term: C = alpha K diag(r) K^T + beta C
mtl::congruence(alpha, K, r, beta, C);

Where these operations come from, the Joseph covariance update and the GEMMT BLAS extension, is told in gemmt-origins.md.

gemmt computes C = α A B + β C for an n × k matrix A and a k × n matrix B whose product the caller knows to be symmetric. Only one triangle of C, the diagonal included, is formed: uplo::lower (the default) or uplo::upper. That is half the multiply–adds of mult.

The other triangle is then mirrored from the formed one, so C is exactly symmetric: C(i,j) and C(j,i) hold the same bits. This is syrk’s full-result convention. gemmt_fill::keep leaves the other triangle as it was, as the BLAS routine does.

With β ≠ 0 and the default mirror, the input C must be symmetric. Only the formed triangle of the old C is read, so an asymmetric C loses the other triangle’s β C terms and the result is not α A B + β C.

B can be a dense matrix, trans() of one, or trans() of a compressed2D. For a transposed CRS matrix R, entry (i,j) sums over the stored entries of row j of R, so its cost is that row’s number of non-zeros rather than k.

α and β follow the BLAS convention. They are converted to C’s element type first, as ?gemmt takes them, so the generic and BLAS paths combine with the same coefficients. With β = 0, C is not read, so a NaN left in it does not propagate; with α = 0, A and B are not read.

On the generic path every entry of the formed triangle is summed exactly as mult’s generic kernel sums it: from zero, adding A(i,0) B(0,j), A(i,1) B(1,j), … in ascending k. The triangle therefore agrees with mult bit for bit, and the test suite checks this for a class-type scalar that rounds at every step. With an explicit Accumulator, each entry is summed in that type and rounded once to C’s element type before the α/β combine, as mult<Acc> and syrk<Acc> do.

For a transposed CRS B, the sum leaves out the terms whose B entry is not stored. Adding an exact zero product does not change a finite sum, so the result agrees with the dense one bit for bit whenever A is finite.

?gemmt is a BLAS extension. MKL, BLIS and recent OpenBLAS export it; reference BLAS added it in 3.12 under the name ?gemmtr, and older OpenBLAS releases lack it. CMake links and runs a small dgemmt_ call and defines MTL5_BLAS_HAS_GEMMT only if it returns the right answer. Linking alone is not enough: OpenBLAS 0.3.26, the version in Ubuntu 24.04, exports dgemmt_ but checks lda and ldb against each other’s dimensions, so it rejects a valid call with k > n and leaves C unwritten (fixed in 0.3.27). When cross-compiling, the probe cannot run and gemmt keeps its generic path. A build that links BLAS without CMake defines MTL5_BLAS_HAS_GEMMT by hand, and only for a library that has a working ?gemmt.

With MTL5_BLAS_HAS_GEMMT, gemmt dispatches when the accumulator allows BLAS, C is a dense float or double matrix, and A and B are dense matrices of the same type or trans() of one. The operands’ orientations need not agree: each maps onto transa or transb, and a row-major C is computed as Cᵀ = Bᵀ Aᵀ with the other triangle. The vendor’s summation order is its own, so a BLAS result is not bit-identical to mult.

OpenBLAS is the exception (MTL5_BLAS_VENDOR_OPENBLAS, which CMake defines from the library’s exports). Its dgemmt takes about twice as long as a full dgemm while doing half the work: at n = 512 on one core of an i7-12700K, 7.1 ms against 3.7 ms, which is 19 GFLOP/s against 72 (#744). With OpenBLAS, gemmt calls dgemmt only up to 64 rows, where it is as fast as anything else, and uses the blocked path below above that. A BLAS build without a working ?gemmt uses the blocked path too, where it used to take the generic loops.

In a BLAS build that does not call ?gemmt, and in the MTL5_NATIVE_FAST_GEMM build, operands of the same shape as above take a blocked path once n is larger than detail::gemmt_block, which is 64. This builds gemmt out of a full-speed GEMM: ?gemm in a BLAS build, and detail::gemm_blocked otherwise.

  • Splitting the triangle: for the lower triangle, the block below the diagonal, C[h:n, 0:h] = α A[h:n, :] B[:, 0:h] + β C[h:n, 0:h], is one rectangular GEMM. The two triangles on the diagonal, [0, h) and [h, n), are split the same way, recursively. The upper triangle is the mirror image.
  • Diagonal blocks: a block of at most 64 rows is formed as a square GEMM in a scratch tile. Only its triangle is combined into C, so the other triangle of C is never written before the mirror. About n · 64 · k of the flops go to entries that are discarded, an eighth of the work at n = 512.
  • The contract is unchanged: β = 0 does not read C. α = 0, k = 0 and n ≤ 64 keep the path they had: ?gemmt where the build calls it, and the generic loop otherwise.
  • Rounding is the GEMM’s, as for mult on these builds.

Above 64 rows, congruence hands its second product to this path as trans(A), described by its strides, with no copy. At 64 rows and fewer it copies Aᵀ out as before, because the generic loop is fast only on the copy.

congruence(A, P, C) computes the symmetric m × m matrix C = A P Aᵀ for an m × n matrix A and a symmetric n × n matrix P. It forms T = A P with mult and then the lower triangle of T Aᵀ with gemmt, mirrored. On the generic path the lower triangle is therefore bit-identical to mult(mult(A, P), trans(A)). P’s symmetry is the caller’s promise; it is neither checked nor used to save work. With β ≠ 0, C must be symmetric too: only its lower triangle is read, and the upper triangle of the result is the mirror of the lower one, so an asymmetric C loses its upper β C terms.

This is the shape of every covariance update in a Kalman filter:

StepProduct
PredictionP ← F P Fᵀ + Q
Clone augmentationP ← G P Gᵀ
Innovation covarianceS = H P Hᵀ
Joseph update(I − K H) P (I − K H)ᵀ + K R Kᵀ

A may be a compressed2D. The Jacobians F, G and H are mostly identity blocks and strips, and both products then walk only the stored entries: the first through mult’s CRS × dense kernel (#550), the second through gemmt with a transposed CRS B. A dense and a CRS A with the same entries give the same bits.

The vector overload, congruence(α, K, r, β, C), computes α K diag(r) Kᵀ + β C for the K R Kᵀ term of the Joseph form when R is diagonal. It forms T(i,k) = K(i,k) r(k) directly, one rounding per entry, and then calls gemmt. With β = 1 it adds the term to a C already holding the first one.

Moving from mult followed by a symmetrize, (C + Cᵀ)/2, to congruence is not bit-identical. The average rounds the two triangles’ sum, while congruence keeps one triangle as mult computed it and copies it across. Each is a correctly symmetric result of the same accuracy; they differ in the last bit of some entries.

benchmarks/bench_congruence.cpp times C = A P Aᵀ for a transition-shaped A, F = Φ ⊕ I: a dense 15 × 15 block and the identity elsewhere. P is a symmetric d × d covariance and everything is row-major double. The arms are:

  • two_step: mult(A, P), then mult(T, trans(A)) and (C + Cᵀ)/2. This is the form branes-ai/cortex uses today.
  • copy: the same, with trans(A) first copied into a dense matrix, so that the second product is a plain mult that BLAS can take.
  • congruence: congruence(A, P, C) with a dense A.
  • CRS: congruence(A, P, C) with A a compressed2D.

The times are in microseconds per call, the minimum over 15 rounds. They were measured on one core of an i7-12700K, pinned, with MTL5_NUM_THREADS=1 and OPENBLAS_NUM_THREADS=1 and the powersave governor. The generic build has neither BLAS nor MTL5_NATIVE_FAST_GEMM; the BLAS build links OpenBLAS with MTL5_BLAS_HAS_GEMMT. The BLAS rows for d ≥ 100 were re-measured after #744, where the second product takes the blocked path. The earlier dgemmt times were 61.5, 224 and 446.

dnnz(A)two_stepcopycongruenceCRStwo_step, BLAScopy, BLAScongruence, BLASCRS, BLAS
152251.441.441.151.561.020.640.781.47
302409.058.396.264.066.422.842.804.00
6027072.956.242.110.054.416.814.310.2
10031038826320420.629366.763.021.1
1503601440109180340.799521719841.6
20041035422499181960.1254549042361.5
  • Generic, dense A: congruence takes 0.73–0.78× the time of the copy arm from d = 60 up and half the time of two_step at d = 200. The second product does half the work, and the dense A is copied out as Aᵀ so that it runs in the vectorizable i-k-j form, as mult does for row-major operands. The first product is a full mult in both arms, which is why the saving is about a quarter and not a half.
  • BLAS, dense A: congruence takes 0.85–1.03× the time of the copy arm from d = 30 up, and is slower at d = 15. The second product is half of a dgemm’s work, but the first product, a full mult, dominates. Since #744 the second product takes the blocked path from d = 100 up, at 0.87–0.94×. The gain over two_step comes from avoiding trans(A), which mult cannot hand to BLAS.
  • CRS A: both products walk only the stored entries, so the time follows nnz(A) rather than d². At d = 200 it is 30 times faster than the generic dense arm and 7 times faster than the BLAS one. When A is fully dense (d = 15), the indirection makes it the slowest arm.

The CSVs are not committed; rerun the benchmark to reproduce the table.

mtl5_bench’s blas3/gemmt entry times gemmt(1, A, B, 0, C) for square, row-major double operands, on one core of an i7-12700K. Its rate counts the triangle’s n³ flops, half of gemm’s 2n³, so equal GFLOP/s means half the time.

buildngemmgemmt before #744gemmtgemmt time / gemm time
BLAS (OpenBLAS 0.3.32)51272.8 GFLOP/s18.9 GFLOP/s52.3 GFLOP/s0.70
BLAS (OpenBLAS 0.3.32)102473.5 GFLOP/s19.0 GFLOP/s60.4 GFLOP/s0.61
native-fast51271.4 GFLOP/sabout 14 GFLOP/s51.4 GFLOP/s0.69
native-fast102470.6 GFLOP/s—56.3 GFLOP/s0.63
  • Why not 0.5: the recursion ends in GEMMs of 64 rows and fewer, which OpenBLAS runs at 46–64 GFLOP/s rather than 72. The diagonal blocks also do an eighth more work than the triangle needs.
  • The mirror: the default gemmt_fill::mirror copies the triangle across in 8 × 8 tiles. That is about 0.2 ms at n = 512. A plain loop took 0.33 ms there and 1.4 ms at n = 1024, because with a power-of-two leading dimension the writes down a column all fall in a few L1 cache sets.
  • Only float and double dispatch to BLAS; ?gemmt for complex types is not wrapped.
  • A as a compressed2D is read through A(i,k) on the generic path of gemmt itself. The CRS-aware path is for the transposed B, which is where congruence puts it.
  • Every entry of T = A P is formed, as mult forms it. A congruence that also exploited P’s symmetry would be symm followed by gemmt, which saves nothing on the generic path, since symm reads both triangles.