Skip to content

ell_matrix: architecture of the ELLPACK sparse matrix

How mtl::mat::ell_matrix is put together, and why it trades memory for regularity. Where compressed2D stores exactly the nonzeros of each row in a variable-length run, ELLPACK (ELL) pads every row to a fixed width so the whole matrix becomes a regular, dense-shaped nrows × width grid of index/value pairs. That regularity is the entire point: a branch-free, fixed-trip-count inner loop is what makes sparse matrix-vector products vectorize cleanly on SIMD units and coalesce on GPUs.

ELL is not a build format and not a general-purpose store. It is a re-encoding of a finished CSR matrix for one particular access pattern. Its design is best read as a deliberate set of trade-offs around that single idea.

The implementation is ~130 lines in include/mtl/mat/ell_matrix.hpp.


The representation: two padded nrows × width arrays

Section titled “The representation: two padded nrows × width arrays”
ell_matrix<Value, Parameters = parameters<>>
nrows_, ncols_, width_ shape + the fixed row width
indices_ : vector<size_type> len nrows*width column index of each slot
data_ : vector<Value> len nrows*width value of each slot
invalid = size_type(-1) sentinel for an unused slot
Matrix CSR rows ELL, width = max row nnz = 2
[ a . b ] 0: {0:a, 2:b} row r, slot k -> index [r*width + k]
[ . . c ] 1: {2:c}
[ . d e ] 2: {1:d, 2:e} indices_ = [ 0, 2 | 2, -1 | 1, 2 ]
data_ = [ a, b | c, 0 | d, e ]
row0 row1 row2

Every row occupies exactly width_ consecutive slots, whether or not it has that many nonzeros. Row 1 has a single entry, so its second slot is padding: index invalid (-1), value math::zero<Value>(). Element k of row r is always at indices_[r*width_ + k] — no row-pointer indirection, no per-row length lookup. The address is pure arithmetic.


Decision 1 — pad every row to a fixed width

Section titled “Decision 1 — pad every row to a fixed width”

The defining choice is that all rows have the same number of slots. This costs memory — the padding slots store nothing useful — and buys a regular access pattern:

  • No indirection. CSR reads starts_[r] to find where a row begins; ELL computes r*width_ directly. The row-pointer array is gone.
  • A fixed trip count. A per-row loop runs exactly width_ iterations for every row. A kernel can unroll or vectorize it without a data-dependent bound — the property CSR lacks, because CSR row lengths vary and stall a vector unit that wants a uniform stride.
  • A dense-shaped footprint. indices_/data_ are just nrows × width_ arrays; they index and stream like a dense matrix, which is why ELL is the classic format for GPU SpMV (one thread per row, uniform work) and SIMD kernels.

This implementation stores rows contiguously (r*width_ + k), so a single row’s slots are adjacent — the natural fit for a per-row unrolled/vectorized inner loop on a CPU. (Some ELL variants transpose to slot-major, k*nrows + r, for GPU memory coalescing; MTL5’s layout is the row-contiguous form.)


Decision 2 — width_ is the max row length, and that is the whole trade

Section titled “Decision 2 — width_ is the max row length, and that is the whole trade”

width_ is set to the longest row in the source matrix:

width_ = 0;
for (size_type i = 0; i < nrows_; ++i)
width_ = std::max(width_, starts[i+1] - starts[i]); // max nnz over all rows

This single line is where ELL’s suitability is decided. Total storage is nrows × width_, so the wasted space is nrows × width_ − nnz — the sum over rows of (width_ − nnz_row). That is small when rows are uniform (structured grids, stencils, finite-difference operators: every interior row has the same degree) and catastrophic when they are not: a single dense row forces width_ wide, and every other row then pads out to that width.

The design states this honestly in its own doc comment — ELL is “good for GPU and matrices with uniform row lengths.” It is deliberately not a general-purpose sparse store; a matrix with a few dense rows belongs in CSR, or in a hybrid ELL+overflow format (which MTL5 does not currently provide). Choosing ELL is choosing to assert your rows are near-uniform.


Decision 3 — derived from CSR, read-only, with no build path of its own

Section titled “Decision 3 — derived from CSR, read-only, with no build path of its own”

ell_matrix has no inserter, no insert, and no mutable operator(). Its only populating constructor takes a compressed2D:

explicit ell_matrix(const compressed2D<Value, Parameters>& crs); // the one fill path

(The other constructor merely allocates an empty, all-padding grid of a given width.) This is a deliberate placement in the pipeline: you assemble a matrix in COO or an inserter, freeze it to CSR, and only then re-encode it to ELL for a vectorized compute phase.

Why no independent build path. ELL’s whole value is the fixed width, and you cannot know the right width until every row’s final length is known — which is exactly the point at which you already have a CSR matrix. Building ELL incrementally would mean either guessing width_ up front (and reallocating the entire padded grid when a row exceeds it) or scanning for the max anyway. Deriving from a completed CSR does the width computation once and scatters each row’s entries left-packed into its slots. ELL is downstream of CSR by construction:

COO / inserter -> compress -> CSR -> ell_matrix(crs) -> vectorized SpMV

Decision 4 — left-packed slots and early-exit access

Section titled “Decision 4 — left-packed slots and early-exit access”

Entries are packed to the left of each row; padding is always on the right. operator() exploits that to stop early:

value_type operator()(size_type r, size_type c) const {
for (size_type k = 0; k < width_; ++k) {
size_type idx = indices_[r*width_ + k];
if (idx == invalid) break; // packed left => no real entry past here
if (idx == c) return data_[r*width_ + k];
}
return math::zero<Value>(); // absent -> structural zero
}

Because a row’s real entries are a contiguous left prefix, the first invalid slot marks the end of that row’s data, and the scan breaks — so a lookup costs O(nnz_row), not O(width_), in the common case. The scan is linear rather than a CSR-style binary search because width_ is small and bounded by design; a branchy binary search would not pay off over a handful of contiguous slots, and the linear form is what a compiler can unroll. As with every MTL5 matrix, an absent element returns math::zero<value_type>(), so custom number types get the correct additive identity.

Entries within a row keep the column order they had in CSR (ascending), since the constructor copies them in starts[i]..starts[i+1] order — a property a kernel may rely on even though operator() does not require it.


Decision 5 — row-major only, enforced early (#355, lower severity)

Section titled “Decision 5 — row-major only, enforced early (#355, lower severity)”

Like its CSR source, ell_matrix accepts a Parameters bundle but is row-padded unconditionally: every access is indices_[r*width_ + k], and nothing ever read Parameters::orientation. A col_major instantiation was therefore accepted silently while being byte-for-byte the row-major layout — the same inert-tag defect as compressed2D. A compile-time static_assert rejects it:

static_assert(std::is_same_v<typename Parameters::orientation, tag::row_major>,
"ell_matrix is row-padded ELLPACK storage only; a col_major instantiation "
"would be byte-identical to the row-major layout and silently misdescribe it (#355). ...");

The severity here is genuinely lower than in CSR, and the source comment is careful to say why rather than assert it by analogy: ELL’s only fill path is the compressed2D constructor, which for col_major parameters is already a compile error (CSR’s own static_assert fires). So no col_major ELL can be populated today, and none can be returning wrong answers. What a col_major ELL could still do is be constructed empty while claiming a layout it does not implement — and the instant someone adds an inserter or a setter, that latent hole reopens silently. The assert closes it now, at the point of misuse, so a future contributor gets a clear diagnostic on ell_matrix rather than a confusing one about compressed2D. It is a fix applied before the bug can bite, not after.


Storage: std::vector, regular in shape but not over-aligned

Section titled “Storage: std::vector, regular in shape but not over-aligned”

Both arrays are plain std::vector (assign-ed to nrows*width_ on construction), like the other sparse containers and unlike dense2D’s custom, 64-byte-aligned contiguous_memory_block. Worth being precise about what ELL does and does not guarantee:

  • It guarantees structural regularity — the fixed stride width_ that a vectorized kernel needs to compute addresses without branches.
  • It does not guarantee alignment — indices_.data() and data_.data() carry only std::vector’s default alignment. Aligned loads, if a kernel wants them, are a separate concern (an aligned allocator or padding the leading dimension), not something the container currently provides.

Regularity and alignment are independent properties; ELL supplies the first, which is the one that distinguishes it from CSR. The second remains available to layer on if a tuned ELL kernel needs it.


The same two external specializations as the other sparse types:

template <...> struct traits::category<ell_matrix<...>> { using type = tag::sparse; };
template <...> struct ashape::ashape<ell_matrix<...>> { using type = mat<Value>; };

category = tag::sparse and ashape = mat<Value> give ELL the same type-system identity as CSR and COO. Note that MTL5 does not yet ship a tuned ELL SpMV kernel — the format is present as storage (and is consumed by the spy visualizers), with ref_indices()/ref_data() exposing the raw padded arrays for a kernel to stream. The regular layout is the enabling precondition for such a kernel; the trait plumbing is what will let it be selected by category when it lands.


ELL is a fourth core format, but it belongs to a different phase than the COO→CSR build chain — it is a compute-oriented re-encoding of CSR, chosen when row lengths are uniform enough to make the padding cheap:

dense2Dcoordinate2D (COO)compressed2D (CSR)ell_matrix (ELL)
Optimized fordense computebuildinggeneral SpMV / solversregular / vectorized SpMV
Storageone aligned blocktriplet vectorthree arraystwo padded nrows×width arrays
Per rowfull rown/aexact nnz, variablefixed width_, padded
Build pathin placeinsertinserter / COOnone — from CSR only
Read costO(1)O(nnz) scanO(log nnz_row)O(nnz_row), fixed-trip loop
Best whendenseany-order fillgeneral sparserows near-uniform length
Weakness—not queryableirregular vector accessmemory blows up on skewed rows

The intended flow when ELL is appropriate: COO/inserter → compress → CSR → ell_matrix(crs) → vectorized SpMV. ELL owns only that last re-encoding step, and only earns its keep when the rows are uniform.


FileRole
mat/ell_matrix.hppthe ELL container: padded arrays, CSR constructor, early-exit operator(), #355 assert
mat/compressed2D.hppthe CSR source ELL is built from
mat/parameter.hppthe shared parameters<> bundle
math/identity.hppmath::zero<T>() for padding and absent-element returns
io/spy.hppcurrent consumer of ELL (sparsity visualization)

For the source format and the rest of the family, see the compressed2D, coordinate2D, and dense2D architecture docs.