When does storing fewer entries actually help?

Intuition: zeros can carry structure

A diagonal matrix has many zeros, yet only its diagonal values contribute products to a matrix-vector multiplication. A sparse representation records where the contributing values are rather than reserving a value slot for every coordinate. This can save space and arithmetic work when zeros are common.

The grid shows the aggregated dense matrix, with explicit zero-based [row,column] labels. Click or tap a cell to toggle its aggregate between structural zero and one. To enter another exact value, edit the COO triples. The same canonical state controls the grid, storage arrays, inspector and multiplication trace; there is no separate decorative matrix.

Sparse overhead matters. A nearly full 3×3 matrix can consume more ideal packed storage in COO or CSR than in dense form. Those representations also have different access patterns. Fewer stored values is not a universal wall-clock speed guarantee.

Definition: bounded dense, COO and CSR data

This explorer uses m rows and n columns, each from one through three. A dense representation has mn value slots. COO, coordinate storage, records triples (row,column,value). CSR, compressed sparse row storage, uses a value array, a parallel column-index array and a row-pointer array of length m+1.

For row i, CSR entries run from indptr[i] up to, but excluding, indptr[i+1]. Equal consecutive pointers describe an empty row. Indices are zero-based in these programs and views; in one-based mathematical notation they would be shifted by one.

Raw COO may contain duplicates and explicit zeros. This chapter’s canonical policy sums duplicates exactly, sorts by row then column, and removes only exact aggregated zeros. A near-zero diagnostic never alters the structure. Shape, coordinates, finite values and vector length are validated before deriving storage or products.

Mechanics: one matrix, two actual multiplication paths

The canonical state holds the declared shape, raw COO text, vector and diagnostic threshold. The model derives the dense exact rational matrix and canonical COO/CSR arrays. It computes the sparse result by actually traversing CSR nonzeros, and independently computes a dense result through the accepted exact matrix API.

Each sparse product record contains its row, column, coefficient, x[column], product, accumulator before and accumulator after. The column index selects a vector component; the row pointer selects where the output sum belongs. Swapping those meanings would give the wrong operation even if a storage diagram looked plausible.

For a grid toggle, all raw duplicates at the selected coordinate are replaced together. Removing a currently nonzero aggregate removes that coordinate; toggling an exact aggregate zero adds one. Other raw entries retain their exact decimal values. Empty COO text explicitly represents an all-zero matrix.

Derivation: sparse multiplication and ideal packed costs

The mathematical product is

$(Ax)_i=\sum_{j=0}^{n-1}A_{ij}x_j.$

For a canonical sparse matrix, exact zero terms contribute nothing. CSR evaluates only the stored coefficients between the two row pointers, accumulating each result into that row. Its coefficient multiplications number nnz rather than mn; this counts a specific arithmetic operation, not all indexing, allocation or traversal overhead.

Assume numerical values occupy eight bytes and indices occupy four bytes. Ignoring container, alignment and shape metadata,

$B_d=8mn,\qquad B_{\mathrm{COO}}=16\operatorname{nnz},$ $B_{\mathrm{CSR}}=12\operatorname{nnz}+4(m+1).$

These are ideal Float64/int32 packed-array costs. The explorer computes exact rational references; its BigInt objects do not occupy eight bytes each. Converting those values to actual numerical storage can introduce the representation effects from earlier chapters.

Worked examples: a diagonal and an empty row

For A=diag(2,3,4) and x=(1,2,3), the exact output is (2,6,12). Canonical COO contains (0,0,2), (1,1,3), (2,2,4). CSR data=[2,3,4], column indices=[0,1,2], and indptr=[0,1,2,3]. There are three stored coefficient products rather than nine dense coefficient products.

The ideal costs are 72 dense bytes, 48 COO bytes and 52 CSR bytes. CSR pays four row pointers; that overhead is significant for a tiny matrix. A full 3×3 matrix with nine nonzeros instead costs 144 COO bytes or 124 CSR bytes, compared with 72 dense bytes.

Remove the middle diagonal entry. The middle output becomes zero and CSR indptr becomes [0,1,1,2]. The repeated one correctly describes row 1 as empty. It does not mean column 1 is absent from every other row.

The duplicate-cancellation preset has raw (0,0,2), (0,0,−2), (1,2,3) and an explicit zero. The first pair sums to exact zero. Only coordinate (1,2) survives, giving result (0,9,0) and row pointers [0,0,1,1].

Executable reference code

The pedagogical program aggregates raw coordinates with a Fraction dictionary, constructs CSR, and evaluates products through its pointers. The NumPy version builds an actual dense array with additive coordinate insertion and independently evaluates the product. No SciPy or compiled sparse backend is needed. Compare the indices, storage costs and matrix-vector products in the sparse and dense representations.

"""Bounded COO aggregation and actual CSR matvec; exact reference values use Fraction."""
from fractions import Fraction as F
def sparse(rows,cols,entries,vector):
    assert 1<=rows<=3 and 1<=cols<=3 and len(vector)==cols and len(entries)<=18
    coordinates={}
    for row,col,value in entries:
        assert 0<=row<rows and 0<=col<cols
        coordinates[row,col]=coordinates.get((row,col),F(0))+F(str(value))
    canonical=[(row,col,value) for (row,col),value in sorted(coordinates.items()) if value]
    data=[];indices=[];indptr=[0]
    for row in range(rows):
        for r,col,value in canonical:
            if r==row:data.append(value);indices.append(col)
        indptr.append(len(data))
    result=[]
    for row in range(rows):
        accumulator=F(0)
        for position in range(indptr[row],indptr[row+1]):
            term=data[position]*F(str(vector[indices[position]]))
            accumulator+=term
            print('row',row,'column',indices[position],'product',term,'accumulator',accumulator)
        result.append(accumulator)
    return canonical,data,indices,indptr,result
if __name__=='__main__':
    c,data,indices,ptr,result=sparse(3,3,[(0,0,'2'),(0,0,'-2'),(1,2,'3'),(2,2,'0')],[1,2,3])
    assert c==[(1,2,F(3))] and ptr==[0,0,1,1] and result==[0,9,0]
    assert sparse(3,3,[],[1,2,3])[-1]==[0,0,0]
    assert 8*3*3==72 and 16*3==48 and 12*3+4*4==52
    print('CSR',data,indices,ptr,'result',result)

"""NumPy dense cross-check of small COO/CSR; no SciPy backend or speed claim."""
import numpy as np
from sparse_matrices import sparse
if __name__=='__main__':
    entries=[(0,0,2),(0,0,-2),(1,2,3),(2,2,0)]
    a=np.zeros((3,3),dtype=np.float64)
    for row,col,value in entries:a[row,col]+=value
    x=np.array([1.,2.,3.]);answer=a@x
    exact=sparse(3,3,entries,[1,2,3])[-1]
    np.testing.assert_array_equal(answer,np.array(list(map(float,exact))))
    assert np.count_nonzero(a)==1 and np.all(a[0]==0) and np.all(a[2]==0)
    print('dense',a,'matvec',answer,'packed dense bytes',a.nbytes)
    # Exact-reference BigInt/Fraction objects and Python containers have separate memory costs.

Explore: structure is an equality, not a tolerance

Select small but nonzero: 1e-8 lies below the default diagnostic threshold 1e-6, yet its coordinate stays in canonical storage and contributes to the exact product. Increasing the diagnostic threshold can change the near-zero count without changing nnz, CSR pointers or the mathematical product.

Compare diagonal, empty middle row, duplicate cancellation, full and all-zero examples. Predict the pointers and byte counts before reading them. An all-zero matrix still needs m+1 CSR pointers in this cost model.

Edit a coordinate outside the declared shape or supply a vector of the wrong length. The state is rejected with a message rather than silently resizing or truncating. To change a dimension, first make the entries and vector compatible with the new shape; the explorer does not discard data to repair an edit.

Common mistakes and counterexamples

A duplicate coordinate does not necessarily overwrite a previous one. This chapter explicitly sums duplicates; another API must state its own policy. An explicit stored zero can consume space even though it contributes no mathematical product; canonicalization removes it here.

A value close to zero is not a structural zero. Thresholding it would change the matrix and its product, and should be a separate, justified approximation. CSR pointers are exclusive row boundaries, while column indices select input components. Confusing those two arrays breaks multiplication.

Numerical considerations

The small teaching model uses exact rational intended entries and products. It is suited to checking coordinate meaning and zero structure without accidental cancellation in a numerical accumulator. Actual Float64 sparse arrays would additionally require conversion and accumulation error analysis.

Storage costs explicitly describe hypothetical packed numerical arrays. They exclude exact-reference object memory, raw duplicate storage, allocator overhead and runtime bookkeeping. Sparse access can also have worse locality or indexing costs than a dense operation. Operations saved do not establish a performance improvement on an unspecified workload.

Engineering and ML connections

Sparse structure appears in graph adjacency, discretized differential equations, sparse features and selected model architectures. A format choice should follow the pattern of nonzeros, repeated operations and access needs. Preserve shape and index conventions across data loading and multiplication; numerical thresholding must be recorded as a changed mathematical object.

Inspect the corresponding representation and error policy before interpreting a computed value.

Exercises

Predict first, then calculate or test the stated claim. Every answer includes corrective feedback and a worked solution.

Summary and checkpoints

Construct COO and CSR from a small dense matrix, identify an empty row from repeated pointers, combine duplicates under the stated exact policy and replay real sparse products. Explain the packed byte assumptions and why a small nonzero or fewer multiplications does not imply a free accuracy or speed guarantee.