Bring Your Own Formats and Kernels: Composable Abstractions for Sparse Matrix Computation

Pratyush Das, Amirhossein Basareh, Artem Pelenitsyn, Kirshanthan Sundararajah, Milind Kulkarni, and Benjamin Delaware

CGO 2027 · Code Generation and Optimization · March 2027

To appearAcceptance rate 23%

Abstract

Real-world sparse matrices often feature multiple forms of structured sparsity—rectangular dense blocks, diagonal bands, and scattered entries—that no single storage format can efficiently exploit. Hybrid formats address this by storing each subregion of a matrix in its most efficient form. Existing hybrid approaches, however, only support fixed sets of formats and kernels, so incorporating a new representation or kernel requires modifying their internals. We present SABLE, a framework that lets users build bespoke hybrid formats compositionally through a plan–extract–dispatch interface. Users define extractors that carve a matrix into format-specific regions and kernels that emit specialized C code for each region; SABLE assembles these pieces into a single program specialized to the target matrix at compile time. Both components are independent and composable, so a new format automatically integrates with all existing kernels without any changes to the framework. We demonstrate this extensibility by introducing VDIA, a novel format for diagonal bands of non-uniform length, and composing it to build two new hybrid formats—VDIA+CSR and VDIA+VBR+CSR. We evaluate SABLE on SpMV and SpMM using matrices from the SuiteSparse benchmarks, demonstrating geometric-mean speedups over the best fully-sparse baselines of 1.10x/1.20× (SpMV/SpMM) for VBR+CSR, and 1.14×/1.31× for VDIA+CSR, with the full VDIA+VBR+CSR composition yielding a further 1.08×/1.25× over VBR+CSR.

Group members