# A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units

arXiv: https://arxiv.org/abs/1307.6209 · HTML: https://mlsanity.com/paper/1307.6209/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2013.

## Built on by (most cited first, 6 of 6)

- [MACKO: Sparse Matrix-Vector Multiplication for Low Sparsity](https://mlsanity.com/paper/2511.13061/) (2025)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [Optimizing Sparse Linear Algebra Through Automatic Format Selection and Machine Learning](https://mlsanity.com/paper/2303.05098/) (2023)
- [Sparser, Faster, Lighter Transformer Language Models](https://mlsanity.com/paper/2603.23198/) (2026)
- [SparseDitto: An Agentic Sparse Compilation Framework through Architecture-Aware Synthesis on GPUs](https://mlsanity.com/paper/2608.05033/) (2026)
- [Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets](https://mlsanity.com/paper/2609.23995/) (2026)

## Abstract (arXiv)

Sparse matrix-vector multiplication (spMVM) is the most time-consuming kernel in many numerical algorithms and has been studied extensively on all modern processor and accelerator architectures. However, the optimal sparse matrix data storage format is highly hardware-specific, which could become an obstacle when using heterogeneous systems. Also, it is as yet unclear how the wide single instruction multiple data (SIMD) units in current multi- and many-core processors should be used most efficiently if there is no structure in the sparsity pattern of the matrix. We suggest SELL-C-sigma, a variant of Sliced ELLPACK, as a SIMD-friendly data format which combines long-standing ideas from General Purpose Graphics Processing Units (GPGPUs) and vector computer programming. We discuss the advantages of SELL-C-sigma compared to established formats like Compressed Row Storage (CRS) and ELLPACK and show its suitability on a variety of hardware platforms (Intel Sandy Bridge, Intel Xeon Phi and Nvidia Tesla K20) for a wide range of test matrices from different application areas. Using appropriate performance models we develop deep insight into the data transfer properties of the SELL-C-sigma spMVM kernel. SELL-C-sigma comes with two tuning parameters whose performance impact across the range of test matrices is studied and for which reasonable choices are proposed. This leads to a hardware-independent ("catch-all") sparse matrix format, which achieves very high efficiency for all test matrices across all hardware platforms.