scipy.sparse — sparse matrix formats (CSR, CSC), sparse solvers: Visual walkthrough

We will compress this exact matrix (call it $A$ ): $A = 1003000200600040000500 .$

Before any symbols: a matrix here just means a rectangular table of numbers arranged in rows (going across) and columns (going down). We label rows and columns starting at $0$ — so the top-left box is "row $0$ , column $0$ ". That top-left box holds $10$ .

Step 1 — See the waste

WHAT: We colour the grid — nonzeros bright, zeros faded.

WHY: The whole reason CSR exists is that $10$ of these $16$ boxes carry no information. Storing them is like mailing $10$ empty envelopes. If we can describe the matrix using only the $6$ full boxes, we save memory. This is the entire motivation — everything after is bookkeeping to make that idea precise.

PICTURE: Faded grey cells are the zeros we intend to delete. Bright cells are the $6$ survivors.

Step 2 — Read the survivors in a fixed order

WHAT: We sweep a reading arrow through the bright cells in CSR order and write the values in a single strip.

WHY row-first? Because the operation CSR is built to be fast at — multiplying the matrix by a vector — naturally processes one row at a time. Choosing row-order now makes that later loop trivial. (If we cared about columns instead, we would choose CSC; that is a sibling page.)

Following the arrow:

Row $0$ : value $10$ at column $0$ .
Row $1$ : value $20$ at column $1$ .
Row $2$ : values $30, 40, 50$ at columns $0, 2, 3$ .
Row $3$ : value $60$ at column $1$ .

This gives our first array, read straight off the arrow: $the values data = [r 0 10, r 1 20, r 2 30, 40, 50, r 3 60] .$

Here each number under the brace shows which row it came from — but notice data itself does not store the row. We will fix that in Steps 3–4.

Step 3 — Remember which column each value sat in

WHAT: Right under each value in the strip, we tack on its column number.

WHY: data alone is ambiguous — the value $30$ could sit in any column. Pairing each value with its column pins down the horizontal position. We still owe the vertical position (the row); that is the clever part, saved for Step 4.

Reading the column of each survivor in the same left-to-right, top-to-bottom order: $indices = [100, 201, 300, 402, 503, 601] .$

Each subscript shows which value that column belongs to. Now data[k] lives in column indices[k] — but which row?

Step 4 — The lazy way to record rows: count, don't repeat

WHAT: Count the bright cells in each row.

WHY: If we know each row's count, we know exactly where one row's block of values ends and the next begins — without ever writing the row number more than needing a single boundary marker. Counts are cheaper than repeated labels.

$counts = [row 0 1, row 1 1, row 2 3, row 3 1] .$

Each number is how many bright cells that row contributed to data.

Step 5 — Turn counts into bookmarks: the `indptr` array

WHAT: Start a tally at $0$ ; add each row's count in turn, writing down the total before each addition and the final total at the end.

WHY a running total? Because a running total answers the real question directly: "at what slot in the data strip does each row start?" The count of row $0$ is $1$ , so row $1$ must start at slot $1$ ; add row $1$ 's count $1$ and row $2$ starts at slot $2$ ; and so on. These start-positions are the bookmarks that let us flip straight to any row.

Building it from the counts $[1, 1, 3, 1]$ : $indptr = [start 0, = 1 0 + 1, = 2 1 + 1, = 5 2 + 3, = 6 5 + 1] = [0, 1, 2, 5, 6] .$

The leading $0$ : row $0$ always starts at the very first slot.
The trailing $6$ : equals $nnz$ — it marks the end of the last row (nothing lives at or past slot $6$ ).
Length is $4 + 1 = 5$ : one more than the number of rows, because we need both a "start" and an "end" boundary, and consecutive rows share boundaries.

Step 6 — The recovery rule: read any row back out

WHAT: Use two neighbouring bookmarks to cut out exactly one row's block.

WHY: This is the payoff of Steps 4–5. Because indptr[i] and indptr[i+1] fence off row $i$ 's slice, jumping to any row costs a constant number of operations — you do not scan the whole matrix. This is what "fast row access" means.

Check with row $2$ ( $i = 2$ ): indptr[2]=2, indptr[3]=5, so the slice is positions $2, 3, 4$ : $data[2:5] = [30, 40, 50], indices[2:5] = [0, 2, 3] .$ That reads: "row $2$ has $30$ in column $0$ , $40$ in column $2$ , $50$ in column $3$ " — exactly the original matrix. ✓

Step 7 — Edge cases you must not get surprised by

Case A — an empty row. Suppose row $1$ had been all zeros. Then its count is $0$ , and the running total does not advance: $indptr = [0, row 0 end 1, row 1 end — same! 1, \dots]$ Here indptr[1]==indptr[2]==1, so the slice data[1:1] is empty — length $0$ . The rule still works: an empty slice correctly means "row $1$ has no nonzeros." Two equal consecutive indptr values are the signature of an empty row.

Case B — the all-zero matrix ( $4 \times 4$ of zeros). Every count is $0$ , so $data = [], indices = [], indptr = [0, 0, 0, 0, 0] .$ data and indices are empty; indptr is still length $n + 1 = 5$ , all zeros. Nothing is stored except the $5$ bookmarks — the minimum possible.

Case C — a fully dense row. If a row had all $4$ columns nonzero, its count is $4$ and its slice spans $4$ slots. Nothing special breaks — CSR just stores more. This is the warning from the parent: if every row is dense, CSR stores $2 nnz + (n + 1)$ numbers, which exceeds the dense $n \cdot m$ ; sparse only wins when zeros are plentiful.

Step 8 — Watch the mat–vec product ride the rows

WHAT: Multiply $A$ by a vector $x = [1, 1, 1, 1]$ , one output row at a time.

WHY this shows CSR's purpose: the sum runs exactly over one row's slice — the same slices Step 6 built. No zeros are ever visited, so the total work is $O (nnz)$ , not $O (n^{2})$ . Row-major storage is precisely what makes this loop clean and cache-friendly. This is why the parent's mnemonic says "Row to ride the vector."

Computing $y = A x$ with $x = [1, 1, 1, 1]$ :

$y_{0}$ : row $0$ slice = $[10]$ at col $[0]$ → $10 \cdot x_{0} = 10$ .
$y_{1}$ : $[20]$ at col $[1]$ → $20 \cdot x_{1} = 20$ .
$y_{2}$ : $[30, 40, 50]$ at cols $[0, 2, 3]$ → $30 + 40 + 50 = 120$ .
$y_{3}$ : $[60]$ at col $[1]$ → $60$ .

So $y = [10, 20, 120, 60]$ — with zero wasted multiplications.

The one-picture summary

This final figure compresses the whole journey: the original grid on the left, the three arrows (throw away zeros → read row-order → count into bookmarks) leading to the three skinny arrays on the right, with the recovery slice for row $2$ highlighted.

Recall Feynman retelling — explain the whole walkthrough in plain words

Picture a nearly-empty spreadsheet. First I paint only the boxes that actually hold a number and cross out all the blanks — that's the "see the waste" idea. Then I read the painted boxes in one strict order: left-to-right along each row, top row first; I copy their values into one thin strip (data) and, right beside it, a strip of which column each came from (indices). Now I know the horizontal spot of every number but not its row. The clever bit: instead of writing the row number over and over, I just count how many painted boxes each row has, then keep a running total of those counts — that running total (indptr) is a set of bookmarks saying "row 0 starts at slot 0, row 1 at slot 1, row 2 at slot 2…". To read any row back, I look up its bookmark and the next one and cut out the strip between them. Empty rows show up as two identical bookmarks (an empty cut), and an all-zero matrix leaves both value-strips empty with just the bookmarks. Finally, when I multiply the matrix by a vector, I ride along each row's cut, multiply each value by the vector entry in its column, and add — never once touching a blank box. That's why it's fast: work equals number of painted boxes, not the size of the whole grid.

Recall Quick numeric self-check

indptr for our $A$ ? ::: $[0, 1, 2, 5, 6]$
Row $2$ 's values via slicing? ::: data[2:5] = [30,40,50]
$y = A x$ with $x = [1, 1, 1, 1]$ ? ::: $[10, 20, 120, 60]$
Signature of an empty row in indptr? ::: two equal consecutive entries
indptr of an all-zero $4 \times 4$ ? ::: $[0, 0, 0, 0, 0]$

Related vault topics: Dense matrices (NumPy ndarray), LU decomposition, Cholesky decomposition, Conjugate Gradient method, Big-O complexity, PDE discretization, Graph adjacency matrices.