Compressed sparse row matrices with stored-entry semantics

Let $F$ be a field, and let $m,n,s\in \mathbb{N}$, where $\mathbb{N}$ includes $0$. A compressed sparse row (CSR) record for an $m$ by $n$ matrix over $F$ consists of integer arrays $r=(r_0,\dots ,r_m)$ and $c=(c_0,\dots ,c_{s-1})$, and a value array $v=(v_0,\dots ,v_{s-1})\in F^s$, satisfying

$r_0=0,0=r_0\le r_1\le \cdots \le r_m=s,0\le c_t<n(0\le t<s)\mathrm{.}$

For each row $i<m$, its stored entries are the indices $t$ with $r_i\le t<r_{i+1}$. The row is empty exactly when $r_i=r_{i+1}$. Repeated column indices within one row and stored values $v_t=0_F$ are permitted; each such entry remains a separate stored entry.

The represented matrix $A\in M_{m\times n}(F)$ is defined entrywise by

$A_{ij}:={\sum }_{r_i\le t<r_{i+1}}{\mathbf{1}}_{c_t=j}{v}_t(0\le i<m,0\le j<n),$

where ${\mathbf{1}}_{c_t=j}$ is $1_F$ when $c_t=j$ and $0_F$ otherwise, and an empty sum is $0_F$. Repeated entries in column $j$ are therefore added. The number $s$ is the stored-entry count; it is not in general the number of nonzero entries of $A$.

A CSR record is canonical when no row repeats a column and no stored value is zero. In that case every nonzero matrix entry is stored exactly once and $s=\mathrm{nnz}(A)$, where $\mathrm{nnz}(A)$ denotes the number of nonzero entries of $A$. If $m=0$, the endpoint conditions force $s=0$ and the row-pointer array has its single entry $r_0=0$. If $n=0$, the column-index condition forces $s=0$ as well.