Question about sparse format choice for RVV-accelerated SpMV
Yash Kaushik
Hi everyone,
I had another question while thinking about sparse matrix formats for RVV-targeted SpMV implementations.
Is CSR still generally considered the preferred storage format for SpMV on RISC-V Vector (RVV), or do formats like ELLPACK, COO, SELL-C-sigma, etc. tend to map better to RVV’s vector-length-agnostic execution model?
From what I understand, CSR is widely used because of its memory efficiency and generality, but I’m curious whether the irregular row lengths and indirect accesses become a bigger bottleneck on vector hardware specifically. On the other hand, formats like ELLPACK seem more vector-friendly due to their regular structure, even if they introduce padding overhead.
I would really like to understand how sparse format choices change when targeting RVV/vector architectures in practice, and what formats are typically preferred in production HPC or research implementations.
Thanks!
Jash Ambaliya
I think I’m a good fit to answer this because this summer I am working on a NumFOCUS GSoC project focused on sparse linear algebra and performance-oriented implementation work: https://summerofcode.withgoogle.com/programs/2026/projects/uVGglAZn. A big part of that work is thinking about sparse storage formats, memory access patterns, and what actually maps well to modern vector-style execution, so this is very close to the kind of tradeoff I am currently studying.
My understanding is that CSR is still usually the default or baseline choice for SpMV because it is general, compact, and already well supported across sparse libraries. That said, when targeting vector hardware like RVV, CSR is not always the most natural format for extracting SIMD-style parallelism, mainly because row lengths are irregular and column-index gathers are indirect. Those properties can make utilization less predictable even though RVV handles variable vector lengths better than fixed-width SIMD.
So in practice, I would say the answer is usually “it depends on the sparsity structure.” If the matrix has fairly regular row lengths, ELLPACK- or SELL-C-sigma-style layouts can often map better to vector execution because they improve regularity, make loads more structured, and reduce control overhead. SELL-C-sigma in particular is often attractive because it keeps much of the vector-friendliness of ELL while reducing the worst padding costs by sorting/bucketing rows locally. COO can also be useful in some cases, but for plain SpMV it is often less attractive than CSR or SELL variants unless you specifically want elementwise streaming or are targeting a kernel where that layout is otherwise convenient.
So I would not say there is one universally preferred RVV format in the abstract. CSR remains the practical general-purpose format, especially for portability and interoperability, but vector-oriented formats become much more compelling when the matrix structure is regular enough that the gain in vector efficiency outweighs padding/reordering overhead. In production HPC, this often ends up as either:
1. CSR as the default interchange/storage format, with
2. conversion to a more vector-friendly internal format when repeated SpMV on the same matrix justifies it.
That is also why many research implementations compare CSR against SELL-C-sigma/ELL-like hybrids rather than treating CSR as the only serious option.
So my short take would be: CSR is still the standard baseline, but for RVV-accelerated SpMV, formats like SELL-C-sigma or ELL-derived variants can be better choices when the matrix structure allows efficient vectorization without too much padding overhead.
Yash Kaushik
Thank you for such a detailed response, and congrats on the GSoC project!
The CSR → SELL-C-sigma progression makes a lot of sense now, I hadn't considered how irregular row lengths hurt RVV utilization despite its variable-length design. The point about using CSR as the interchange format and converting only when repeated SpMV justifies it is a really practical insight.
Are there any open implementations or papers on SELL-C-sigma you'd recommend as a starting point?
Jash Ambaliya
For a starting point, I would begin with the original SELL-C-σ paper by Kreutzer et al., A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units. That is the paper that really motivates the format, explains the role of the C and σ parameters, and compares it against CSR and ELLPACK across multiple architectures.
For an actual open implementation reference, PETSc is probably one of the best places to look. It has a MATSELL matrix type, documented as a sparse matrix format based on sliced ELLPACK, and also exposes sequential/parallel SELL variants such as MATSEQSELL and MPI SELL preallocation routines. That makes it a very practical codebase to study if you want to see how a production library integrates a SELL-family format rather than treating it as only a research idea.
If you also want a follow-up paper that is implementation-oriented, I’d look at the SELL-P work from Anzt et al., which presents a padded sliced-ELLPACK variant and develops an SpMV kernel around it for GPUs. It is not exactly SELL-C-σ, but it is very close in spirit and useful for understanding how these sliced-ELL ideas evolve when targeting throughput-oriented hardware.
Yash Kaushik
Got it! Kreutzer et al. paper: foundational reference for SELL-C-σ, and didn't know PETSc exposed a MATSELL type, that's a great concrete codebase to study alongside the theory. Anzt et al.: will check out the SELL-P work for the GPU-side perspective.
Really appreciate you taking the time!