Why store the zeros indirectly?
Suppose each row describes one user and each column one possible item. A user interacts with only a few items, but the number of possible items is very large. A dense table allocates an entry for every user–item pair, including the absent pairs. Matrix–vector products are central to least-squares and many iterative algorithms, so an implementation needs a way to access the observed entries without scanning the entire table.
We will use compressed sparse row (CSR) storage. Sparsity is a statement about the representation and the matrix, not a promise that all later results will also be sparse. In this section is an real matrix, and . Array positions are zero-based, and intervals include but exclude . Arithmetic claims are exact; floating-point accumulation and hardware costs require separate measurement.
Three arrays and their invariant
The representation consists of three arrays and an invariant that ties them to a matrix.
Definition 4.4.1
(CSR representation)
A CSR representation of an matrix with stored entries consists of arrays value and col of length and rowptr of length , satisfying the invariant:
rowptr[0] = 0,rowptr[m] = s, and the pointers are nondecreasing integers;- for in the half-open interval
[rowptr[i], rowptr[i+1]),col[k]is an integer in andvalue[k]is a contribution in row .
The represented matrix is
where an empty sum is zero. An empty row has equal consecutive pointers.
This convention permits duplicate column indices and explicit stored zeros; s counts stored entries, not necessarily the number of mathematically nonzero entries. Libraries differ in their definition of canonical CSR: a common convention requires sorted columns and combined duplicates but may still allow explicit zeros. Removing those zeros as well gives a stronger zero-free representation. These conventions can make equality and some operations easier to reason about, but sorting, combining and zero removal are additional construction work. The product below does not require canonical ordering.
Common mistake
(Reading a row's pointer interval as closed)
Row owns positions rowptr[i] up to, but not including, rowptr[i+1]. With rowptr = (0, 2, 2, 4), row owns positions and only. A loop that also visits position rowptr[i+1] gives row the entry at position , which belongs to row , and makes the empty row look nonempty. The half-open convention is what makes consecutive rows partition the positions .
Theorem 4.4.2
(Forward and transpose products from the same storage)
For valid CSR arrays, initialize and to zero. For every row and every stored position in that row, add value[k] * x[col[k]] to and add value[k] * y[i] to . On termination, and , including when columns repeat or rows are empty.
Proof
(Regroup the stored contributions)
For a fixed row , the algorithm obtains
The second equality groups the finite sum by column and uses the representation invariant. Likewise, for a fixed column the scatter accumulates
These are exactly the coordinates of and . Empty sums contribute zero. This proof is independent of the order in which a row's entries are stored. In floating-point arithmetic, changing that order can change rounded results.
Both computations are the same finite sum, read in two different groupings.
Proof X-ray
Which parts of the invariant the proof uses
The pointer conditions make the row intervals partition the positions , so every stored contribution is visited exactly once and attributed to the right row; the range condition on col makes every lookup in and every write to legal. The key move is regrouping one finite sum over stored positions: grouped by row it gives a coordinate of , grouped by column it gives a coordinate of the transpose product. Duplicate column indices need no special case, because the definition of the represented matrix already adds them, and the regrouping adds them in the same way. The argument uses commutativity and associativity of exact addition to ignore the visiting order; that is exactly the step that fails in floating point, where reordering can change the rounded sum.
Worked example 4.4.3
(An empty row and both products)
Let
The second row owns the empty interval . With , row sums give . With , scattering each row's contribution gives . The second coordinate of has no effect because its row is empty. As a check, both inner products and equal .
Concept lensStructural
The same arrays store the transpose by columns
Read the three arrays with rows and columns exchanged: rowptr becomes a column-pointer array and col a row-index array. They then form a compressed sparse column (CSC) representation of the matrix , because position in row contributes value[k] to entry of . No transposed copy is needed. The forward product gathers along each stored row, while the transpose product is the column-by-column scatter natural to that CSC matrix, which is why its writes can collide.
Stored entries and nonzero entries can differ, as the next edge case shows.
Worked example 4.4.4
(Duplicates that cancel)
For a matrix, let rowptr = [0, 2, 2, 3], col = [1, 1, 3] and value = [2, -2, 5]. Row owns positions , both in column , so . Row owns the empty interval . Row owns position , so . Thus only one entry is mathematically nonzero, although entries are stored. The product algorithm still gives the right answer: for it computes , and . Combining duplicates and removing zeros would leave a single stored entry.
A small implementation and its cost
The following function assumes the CSR invariant has already been validated at the data boundary. It traverses the stored data once and deliberately returns dense output vectors, including entries that remain zero. It does not silently sort or coalesce duplicates. The 0.0 initializers make the accumulations floating-point operations in ordinary Python, so even integer inputs can be rounded; the exact-arithmetic theorem describes the underlying operation rather than a bitwise guarantee for this code.
def csr_products(m, n, rowptr, col, value, x, y):
forward = [0.0] * m
transpose = [0.0] * n
for i in range(m):
for k in range(rowptr[i], rowptr[i + 1]):
j = col[k]
a = value[k]
forward[i] += a * x[j]
transpose[j] += a * y[i]
return forward, transpose
Proposition 4.4.5
(Cost of the CSR products)
Under a unit-cost random-access model, csr_products takes time and additional space for its outputs. The CSR arrays themselves occupy elements.
Proof
(Count the loop iterations)
Initializing the outputs costs writes. The outer loop runs times, and the inner loop for row runs rowptr[i+1] - rowptr[i] times. These counts telescope to rowptr[m] - rowptr[0] , so the inner body, which does a constant amount of work, runs times in total. The total is . The two output lists are the only new storage, of sizes and , and the CSR arrays have lengths , and .
The dense input uses entries. These statements count elements rather than bytes: value and index widths and memory alignment matter. Input vectors require elements; construction, validation, disk I/O, communication and transfers between devices are excluded. When is close to , index overhead can make CSR unattractive. For huge , even initializing the dense transpose output can dominate a very sparse traversal.
Parallelizing the row-wise forward product is straightforward when each worker owns different output rows. In the transpose product, however, distinct rows can write the same column. Concurrent unsynchronized updates can lose contributions. Use an appropriate reduction, atomic operation, or a column-oriented representation, and account for its memory, communication and floating-point ordering. These are implementation choices; none follows automatically from sparsity.
Common mistake
(Parallelizing the transpose product like the forward product)
Suppose two rows each have a stored entry in column , with values and , and . The correct coordinate is . If two workers each read the initial , compute their own sum and write it back without synchronization, one write can overwrite the other, leaving or . Splitting by rows is safe for the forward product only because each row writes its own output coordinate; the transpose product needs a reduction or atomic updates.
Counterexample mode
Sparse input does not make every intermediate sparse
Let be an matrix whose first row is and whose other entries are zero. It has only nonzeros out of possible entries, but has nonzero entries. Explicitly forming can therefore destroy the storage advantage. To evaluate , two sparse products may avoid storing that dense intermediate; this does not by itself fix conditioning or establish a solver's convergence.
The two-pass evaluation is easy to carry out on a small case.
Worked example 4.4.6
(Two sparse passes instead of a dense intermediate)
Take in the matrix above, so rowptr = [0, 3, 3, 3], col = [0, 1, 2] and value = [1, 1, 1], and let . The forward pass gives . A transpose pass with scatters to each column, giving . Directly, is the all-ones matrix and . The two passes touched stored entries each and never stored the entries of .
Practice with solutions
Quick check
(Using the matrix of the first worked example, compute for .)
Sum each row's stored contributions.
Solution · Answer
The three row sums are , for the empty row, and , so .
Quick check
(Give CSR arrays for with no duplicates and no stored zeros.)
List the nonzero entries row by row.
Solution · Answer
Row has in column and row has in column . Hence value = [7, 1], col = [2, 0] and rowptr = [0, 1, 2]; here and rowptr[2] = s as required.
Quick check
(A matrix has rows, columns and stored entries. How many entries does the row-pointer array have, and what does the time bound for the function count?)
Use the lengths in the definition and the cost proposition.
Solution · Answer
rowptr has entries. The bound is elementary initialization, row traversal and stored-entry operations, not a prediction of elapsed time or of the cost of constructing the arrays.