Skip to content

coordinate2D: architecture of the COO sparse matrix

How mtl::mat::coordinate2D is put together, and why it is almost the exact inverse of compressed2D. If CSR is the frozen, read-optimized form, COO (Coordinate format) is the write-optimized form: an append-only bag of (row, column, value) triplets that accepts entries in any order, as fast as a push_back, and defers all structure — sorting, deduplication, row pointers — to a single compress() step that produces a compressed2D.

The organizing idea is staging. coordinate2D is not a matrix you compute with; it is the buffer you accumulate into while building a matrix, before handing a compressed form to the solvers. Every design choice follows from being the cheap-to-fill, expensive-to-query end of the sparse pipeline.

The implementation is ~150 lines in include/mtl/mat/coordinate2D.hpp.


Where CSR uses three parallel arrays (structure-of-arrays, tuned for row traversal), COO uses a single array of triplets (array-of-structs, tuned for appending):

coordinate2D<Value, Parameters = parameters<>>
nrows_, ncols_ logical shape
entries_ : vector<tuple<size_type,size_type,Value>> the (row, col, value) list
sorted_ : bool is entries_ ordered by (row,col)?
Example [ a . b ] entries_ = [ (0,0,a), (0,2,b), (1,2,c), (2,1,d), (2,2,e) ]
[ . . c ] ...in ANY order, with duplicates allowed:
[ . d e ] [ (2,2,e1), (0,0,a), (2,2,e2), ... ] is fine

Keeping (r, c, v) together in one tuple is what makes both core operations trivial: an insert is one emplace_back, and ordering is a single std::sort that carries the value along with its coordinates automatically. There are no invariants to maintain on insert — not sortedness, not uniqueness, not row grouping. That absence is the design.


Decision 1 — insertion is an unordered, duplicate-tolerant O(1) append

Section titled “Decision 1 — insertion is an unordered, duplicate-tolerant O(1) append”
void insert(size_type r, size_type c, Value v) {
assert(r < nrows_ && c < ncols_);
entries_.emplace_back(r, c, v); // append; no search, no ordering
sorted_ = false; // the list may no longer be ordered
}

insert does no lookup and no merge. A second write to an existing (r,c) does not overwrite or combine — it appends a second triplet, and the two are reconciled later. This is exactly right for the workloads COO exists to serve:

  • Finite-element / finite-volume assembly, where the same global (i,j) receives contributions from many elements, generated in element order, not matrix order.
  • Matrix I/O, where a Matrix Market file lists entries in whatever order the producer chose.
  • Unstructured fill, where you simply don’t know the final column pattern of a row until you’ve seen every contribution.

Making insert O(1) and order-free means assembly costs one push_back per contribution and nothing else. reserve(nnz) lets a caller pre-size entries_ to avoid reallocation when the count is known.


Decision 2 — defer all structure to compress()

Section titled “Decision 2 — defer all structure to compress()”

Nothing about coordinate2D tries to be incrementally organized. The sorted_ flag merely records whether the list happens to be ordered (it starts true for the empty matrix and flips to false on the first insert); sort() will order the triplets in place by (row, col) on demand. But the real work — turning an unordered, duplicate-laden triplet bag into a valid CSR matrix — is concentrated in one method, compress().

Why defer. You cannot correctly deduplicate or lay out a row until you have seen all of its contributions. Any per-insert organization would either be redundant (re-sorting on every append) or premature (committing to a row layout that the next insert invalidates). Concentrating the work in compress() means it is done once, over the complete data, at the moment the caller declares the matrix finished — the same “assemble, then freeze” philosophy the inserter follows, expressed here as an explicit conversion rather than an RAII finalize.


Decision 3 — compress(): sort, accumulate, prefix-sum, and it’s const

Section titled “Decision 3 — compress(): sort, accumulate, prefix-sum, and it’s const”

compress() is the bridge to the read-optimized world, and it is non-destructive:

compressed2D<Value, Parameters> compress() const {
// 1. sort a COPY by (row, col) -- leaves *this untouched
std::vector<triplet_type> sorted_entries(entries_);
std::sort(sorted_entries.begin(), sorted_entries.end(), by_row_then_col);
// 2. run-length merge duplicates, counting entries per row
std::vector<size_type> starts(nrows_ + 1, 0), indices;
std::vector<Value> data;
for (size_type k = 0; k < sorted_entries.size(); ) {
auto [r, c, v] = sorted_entries[k]; Value acc = v; ++k;
while (k < N && same (r,c) as sorted_entries[k]) { acc += get<2>(sorted_entries[k]); ++k; }
indices.push_back(c); data.push_back(acc); starts[r + 1]++;
}
// 3. prefix-sum the per-row counts into CSR row pointers
for (size_type i = 0; i < nrows_; ++i) starts[i + 1] += starts[i];
return compressed2D<Value, Parameters>(nrows_, ncols_, data.size(),
starts.data(), indices.data(), data.data());
}

Three properties are deliberate:

  • It works on a copy and is marked const. Compressing does not consume the COO buffer. A caller can compress(), keep accumulating more entries, and compress() again — useful when a matrix is built and solved in stages. The cost is one copy of the triplet array; the benefit is a reusable, side-effect- free staging object.
  • It sorts unconditionally. compress() does not consult sorted_ to skip the sort. That keeps it correct regardless of the object’s state at the cost of a redundant sort when the list is already ordered — a simplicity-over-cleverness trade for a step that already dominates by being O(nnz log nnz).
  • It builds row pointers by counting then prefix-summing — the standard COO→CSR construction: tally how many distinct entries land in each row (starts[r+1]++), then turn counts into offsets with a cumulative sum. The result satisfies every CSR invariant (sorted rows, unique entries, starts[nrows] == nnz) by construction, so the compressed2D it returns is immediately valid.

Decision 4 — duplicates accumulate (assembly semantics, baked in)

Section titled “Decision 4 — duplicates accumulate (assembly semantics, baked in)”

The run-length merge does acc += ...: repeated (r,c) triplets are summed. COO’s compress() therefore always has additive-assembly semantics, matching the finite-element use case where duplicates are separate physical contributions to the same entry.

This is a narrower contract than the inserter’s, which chooses between update_store (overwrite) and update_plus (accumulate) via a policy type. COO does not offer that choice: it accumulates, full stop. The division of labor is intentional — the inserter is the general, policy-parameterized front door; COO is the lightweight accumulation buffer whose one semantic is “sum contributions.” If last-write-wins is what you need, that is the inserter’s update_store, not COO.


Decision 5 — operator() is an honest O(nnz) linear scan

Section titled “Decision 5 — operator() is an honest O(nnz) linear scan”

Random element access exists, but it is deliberately naive:

value_type operator()(size_type r, size_type c) const {
Value sum = math::zero<Value>();
for (const auto& [er, ec, ev] : entries_) // scan EVERY triplet
if (er == r && ec == c) sum += ev; // sum matches (pre-compress)
return sum;
}

It scans the whole triplet list, summing every match — O(nnz) per lookup, and it reflects the accumulate semantics even before compress() runs. The comment in the source is candid: this is “mainly for testing.” COO is not a queryable matrix, and the interface says so by not pretending random access is cheap. Code that needs to read the matrix compresses to CSR first, where access is O(log nnz_row); code that needs to build it stays in COO. Like the sibling containers, an absent entry yields math::zero<value_type>(), so custom number types (posits, intervals, …) get the correct additive identity.


MTL5 offers two ways to assemble a compressed2D, and coordinate2D is one of them. They are complementary, not redundant:

coordinate2D (COO)compressed2D_inserter
Bufferone triplet vectorflat per-row slots + std::map overflow
Best input orderany orderroughly row-major
Duplicate policyalways sumupdate_store or update_plus (choose)
Reusable after buildyes — compress() is constno — RAII, finalizes once at scope exit
Extra tuningnoneslot_size per row
Natural sourceI/O, unstructured filldirect programmatic assembly

Choose COO when entries arrive out of order or from a file and you want the simplest possible staging buffer; choose the inserter when you generate entries in row order and want slot tuning or a choice of duplicate policy. Both converge on the same frozen CSR form.

One inherited constraint: because compress() instantiates compressed2D<Value, Parameters>, a col_major coordinate2D compiles for accumulation but fails to compress() — it trips CSR’s row-major static_assert (#355). In practice coordinate2D, like CSR, is row-major.


The same two external specializations as its siblings, with the sparse category:

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

category = tag::sparse and ashape = mat<Value> mean COO carries the same type-system identity as CSR. In practice, though, you rarely dispatch operations on a coordinate2D — it is a staging type, and the intended flow is to compress() first and let the operation layer work on the CSR result. The traits are there for uniformity and so generic code that inspects category/ashape treats all three matrix types consistently.


coordinate2D is the third corner of MTL5’s core matrix triangle. Each optimizes a different phase:

dense2Dcoordinate2D (COO)compressed2D (CSR)
Optimized fordense computebuildingreading / SpMV
Storageone aligned blockone triplet vectorthree arrays
Insert costO(1) in placeO(1) append, any ordernot supported
Read costO(1)O(nnz) scanO(log nnz_row)
Duplicatesn/aallowed, summed on compressnot stored
Ordering heldn/anone until sort/compressrows sorted (invariant)
Rolenumerical workhorseassembly stagingsolver / kernel input

The intended lifecycle for a sparse matrix is COO (or inserter) → compress → CSR → solve: accumulate cheaply and in any order, freeze once, then compute. coordinate2D owns the first step.


FileRole
mat/coordinate2D.hppthe COO container: insert, sort, compress, scan-based operator()
mat/compressed2D.hppthe CSR form compress() produces
mat/inserter.hppthe alternative CSR builder (slots + overflow, updater policy)
mat/parameter.hppthe shared parameters<> bundle
math/identity.hppmath::zero<T>() for the absent-element return

For the read-optimized target of compress() and the dense workhorse, see the compressed2D and dense2D architecture docs.