Origins of gemmt: the Joseph form and the triangular-output product
MTL5’s gemmt and congruence (gemmt.md) came from a request by
branes-ai/cortex for the covariance updates of a multi-state constraint Kalman
filter (#656). The operations they compute are older than any BLAS: they are
the computational kernel of the Joseph-stabilized covariance update from the
1960s. This page traces that line from estimation theory to the BLAS
extension, and says where MTL5 sits on it.
1. The Joseph-stabilized covariance update
Section titled “1. The Joseph-stabilized covariance update”After a measurement, the Kalman filter updates the state-error covariance with the gain , the measurement matrix and the measurement-noise covariance . The textbook update is
or equivalently, with the innovation covariance ,
Both forms are cheap. Both are also exact only when is the optimal gain, and in finite precision they subtract nearly equal quantities. Rounding errors then accumulate across updates. drifts away from symmetry and can lose positive semi-definiteness, and a filter whose covariance has a negative eigenvalue diverges. The early aerospace implementations of the Kalman filter ran into exactly this.
Peter D. Joseph’s remedy, published in R. S. Bucy and P. D. Joseph, Filtering for Stochastic Processes with Applications to Guidance (Interscience, 1968), is the form now named after him:
Why this structure matters
Section titled “Why this structure matters”- It holds for any gain. The Joseph form is the covariance of the updated error for any , not just the optimal one. The short forms are that covariance only at the optimal gain ; with any other gain they report a covariance the filter does not have, wrong to first order in . The Joseph covariance itself is , so near the optimum a gain error, such as one from rounding, changes it only to second order. Far from the optimum the change is first order, but it is then the true covariance of a suboptimal filter.
- Each term is a congruence. Both terms have the shape with symmetric positive semi-definite: , in the first, and , in the second. In exact arithmetic a congruence of a positive semi-definite matrix is positive semi-definite, and so is the sum. The update never subtracts.
- Floating point still needs care. The form removes the cancellation, but it does not make the computed result symmetric by itself. A product formed by two general matrix multiplies has two triangles that round differently. Implementations either average the triangles, , or form one triangle and copy it. For badly conditioned , even the Joseph form can lose definiteness in the last bits, which is what the square-root (Potter, 1963) and (Bierman, 1977) filters address by never forming at all.
- is often diagonal. In sensor fusion, robotics and navigation, the measurement channels are commonly modelled as independent, which makes diagonal, and the second term is then . A block-diagonal , whose blocks correlate the channels of one sensor, is a general symmetric middle term.
2. The gap in classical BLAS
Section titled “2. The gap in classical BLAS”The Level-3 BLAS (Dongarra, Du Croz, Hammarling and Duff, 1990) gave matrix products their standard interface. Three of its routines come close to the Joseph form’s kernel, and none fits it.
GEMMcomputes for general matrices. It forms all of , so when the product is known to be symmetric about half of its multiply-adds produce entries that are already known.SYRKcomputes and forms one triangle only. It needs both factors to be the same matrix. Reaching through it takes a factorization first, and reaching takes the scaled factor , which requires and adds a square root’s rounding to every column.SYR2Kcomputes from two distinct matrices, but only that symmetrized sum.
What is missing is the product of two distinct general matrices whose
result the caller knows to be symmetric, with one triangle formed. With
, the congruence is exactly . Without such a routine,
code either calls GEMM and discards half the work, or writes its own
triangular loop and gives up the cache blocking and vectorization of a tuned
kernel.
3. GEMMT, the triangular-output product
Section titled “3. GEMMT, the triangular-output product”The routine that fills the gap is GEMMT, GEMM with a triangular output:
and are independent general matrices. The routine does not check that the product is symmetric; it forms the requested triangle and leaves the other untouched.
It is an extension, not part of the 1990 standard, and arrived library by library:
- Intel MKL shipped
?gemmtas an extension. - BLIS, the framework of Field G. Van Zee, Robert van de Geijn and
colleagues, provides
gemmt, and so does AMD AOCL-BLAS, which is built on BLIS. - OpenBLAS added
?gemmtlater. Its 0.3.26 release, the one in Ubuntu 24.04, checksldaandldbagainst each other’s dimensions and rejects valid calls; 0.3.27 fixed it. MTL5’s CMake probe runs a call for this reason rather than only linking one (gemmt.md). - Reference BLAS standardized it in LAPACK 3.12 under the name
?gemmtr.
Diagonal middle terms and packing
Section titled “Diagonal middle terms and packing”A tuned GEMM does not multiply its operands where they lie. It copies panels of them into contiguous, cache-sized buffers first, and the micro-kernel reads only those buffers. The BLIS design makes this packing step the place where cheap transformations of an operand can be folded in, without a separate pass over memory.
For that suggests:
- No materialized scaling pass. The scaled operand need not exist as a matrix.
- Scaling during packing. As the panels of are packed for the macro-kernel, each column is multiplied by its , so the packed buffer holds the scaled operand directly.
- Triangle-aware scheduling. Since only one triangle of is formed, the work per block row grows along the diagonal, and a threaded implementation partitions by work rather than by rows. BLIS weights its thread partitions this way for its triangular-output operations.
Whether a given library folds a diagonal scaling into packing for GEMMT
is a property of that library’s implementation, not of the interface: the
BLAS signature has no argument for a diagonal middle term, so a caller who
needs one forms the scaled operand first.
Where MTL5 sits
Section titled “Where MTL5 sits”MTL5’s congruence(alpha, K, r, beta, C) does what a BLAS caller does: it
forms explicitly, one rounding per entry, in
work, and then calls gemmt(T, K^T). The scaling is a separate pass,
not a packing step. For a dense , congruence forms with
mult and the lower triangle of with gemmt, then mirrors it, which
is the “form one triangle and copy it” route from section 1.
The full Joseph update is two calls:
// C = (I - K H) P (I - K H)^T + K diag(r) K^Tmtl::congruence(IKH, P, C); // first termmtl::congruence(1.0, K, r, 1.0, C); // add the secondThe second call reads with , which requires to be
symmetric; the first call leaves it so. A block-diagonal takes the
dense-middle form, congruence(1.0, K, R, 1.0, C), instead of the second line.
With MTL5_BLAS_HAS_GEMMT, dense float or double operands and an
accumulator that allows BLAS, the second product of each call goes to the
vendor’s ?gemmt (the full conditions are in
gemmt.md); otherwise it runs MTL5’s generic loop,
which rounds the formed triangle exactly as mult does. A
fused, packing-level diagonal scaling would be a kernel of MTL5’s own and is
not implemented.