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

Before we can talk about CSR, CSC, indptr, or spsolve, we need to earn every symbol the parent note throws at you. Three names to hold loosely for now (each fully unpacked in later Deep Dives):

CSR = Compressed Sparse Row — a layout that stores the non-zeros row by row.
CSC = Compressed Sparse Column — the same idea but column by column.
spsolve = SciPy's ==sparse solve== function: hand it a sparse matrix $A$ and a vector $b$ , and it returns the $x$ with $A x = b$ .

This page assumes you have seen nothing else. We build each idea, anchor it to a picture, and only then use its notation.

0. What is a matrix, really?

Picture a spreadsheet. Every cell has an address: which row, which column. The number in row $i$ , column $j$ is written $A_{ij}$ (read "A-sub-i-j"). By near-universal convention in programming, counting starts at 0, not 1 — so the top-left cell is $A_{00}$ .

Figure — scipy.sparse — sparse matrix formats (CSR, CSC), sparse solvers

$i$ = the row index — how far down (the red arrow points down the rows).
$j$ = the column index — how far across (the blue arrow points across the columns).
The pair $(i, j)$ is the cell's coordinate, its full address.

Why the topic needs this: every sparse format is nothing but a clever way to remember, for each stored number, its coordinate $(i, j)$ . If you are shaky on "row index vs column index," none of CSR (Compressed Sparse Row) will land.

1. The shape symbols: $n$ , $m$ , and $n \times n$

Picture: the grid is $n$ tall and $m$ wide. In the parent note you meet things like a $1 0^{6} \times 1 0^{6}$ matrix — that just means one million rows and one million columns, a square grid.

Recall Why do the solvers assume square?

Solving $A x = b$ ::: means "find the input $x$ that the grid $A$ turns into the output $b$ ." That only makes sense when there are as many equations (rows) as unknowns (columns) — i.e. $n = m$ , a square matrix.

2. "Mostly zeros": nnz, density $ρ$ , $≪$ and $\sim$

Why $n^{2}$ ? A square grid has $n$ rows each with $n$ cells, so $n \times n = n^{2}$ cells total. That is the count we are trying not to pay for.

Every case, so you never get surprised:

$ρ = 0$ : the grid is all zeros — store nothing.
$ρ$ small (say $0.005$ ): the sweet spot — sparse wins hugely.
$ρ \approx 0.1$ : the break-even zone — sparse and dense cost about the same.
$ρ \to 1$ : nearly full — sparse is worse (it pays extra to store coordinates for numbers that were going to be there anyway). This is exactly the "sparse isn't always smaller" mistake in the parent.

Why the topic needs this: $ρ$ is the single number that decides whether you should use scipy.sparse at all.

3. Big-O: the language of "how much does it cost?"

Picture two curves as $n$ increases: a straight line ( $O (n)$ ) and a fast-bending parabola ( $O (n^{2})$ ). For a million rows the parabola is a million times taller than the line — that gap is the entire reason we bother with sparsity.

Dense storage / dense work: $O (n^{2})$ — one cost per cell.
Sparse storage / sparse work: $O (nnz)$ — one cost per stored number only.

Why the topic needs this: every claim in the parent ("memory $\sim 1 0^{5} \times$ less," "SpMV is $O (nnz)$ ") is a Big-O comparison. Without this symbol you cannot read those claims.

4. Arrays and indexing: `data[k]`, slices `a:b`

Picture a row of numbered mailboxes; a slice is grabbing a contiguous run of them, stopping one short of the last label.

Why the topic needs this: CSR's headline trick is "row $i$ 's non-zeros are data[indptr[i]:indptr[i+1]]." That is pure slice notation. If a:b is fuzzy, that line is unreadable.

5. Cumulative sum (the heart of `indptr`)

Example the parent uses: counts of non-zeros per row are $[1, 1, 3, 1]$ . Running total, starting at $0$ : $0, 0 + 1 = 1, 1 + 1 = 2, 2 + 3 = 5, 5 + 1 = 6.$ Result: $[0, 1, 2, 5, 6]$ .

Picture bookmarks in a book: bookmark $i$ marks the page where chapter $i$ starts. The distance between two neighbouring bookmarks tells you how long that chapter is. Here "chapters" are rows and "pages" are stored non-zeros — this list of bookmarks is exactly indptr, and its last value is the grand total $nnz = 6$ .

Recall Why is

indptr length $n + 1$ and not $n$ ? You need one bookmark before each of the $n$ rows ::: plus one final bookmark marking the end of the last row, so $n + 1$ bookmarks in total. The last one always equals $nnz$ .

Why the topic needs this: indptr is a cumulative sum, and understanding it as "row-start bookmarks" is the whole reason CSR gets $O (1)$ row access.

6. Summation $\sum$ and the mat–vec product $y = A x$

Picture row $i$ of the grid sliding down over the column $x$ , pairing up cell-by-cell, multiplying, and summing into one number $y_{i}$ .

Why the topic needs this: " $A x$ " is the operation sparse matrices are optimised for, and the parent's SpMV (sparse matrix–vector product) formula is exactly this sum restricted to the stored non-zeros of each row. Iterative solvers like Conjugate Gradient method do nothing but repeated $A x$ products.

7. The solve $A x = b$ and its two toolkits

Two families do this, and the parent uses both — here is the plain-words picture of each:

Direct solvers (e.g. LU decomposition, Cholesky decomposition): factor $A$ into simpler triangular pieces, then unwind. Exact, but factoring can create new non-zeros ("fill-in").
Iterative solvers (e.g. Conjugate Gradient method, part of the broader Krylov subspace methods): start from a guess and improve it step by step using only $A x$ products, often sped up with Preconditioning. Low memory, no fill-in.

You do not need to master these yet — later Deep Dives do. Here you only need to know the symbols: $A$ , $x$ , $b$ , and that "solve" means "invert the arrow." The parent's spsolve is one concrete direct solver of this kind.

Why the topic needs this: solving $A x = b$ is the destination of the whole topic — sparse formats, SpMV, and Big-O all exist so this solve is affordable at a million rows. Every solver name in the parent (spsolve, cg, gmres) is just a different way of doing this one thing.

8. Contrast anchor: the dense matrix

Everything above earns its keep by comparison with a plain Dense matrices (NumPy ndarray), which stores all $n \times m$ cells including every zero. Sparse formats exist to store only section 2's non-zeros with only the coordinates from section 0.

Prerequisite map

Each foundation on the left feeds the sparse-matrix topic on the right: coordinates and dimensions let us name non-zeros, $ρ$ and Big-O tell us when sparsity wins, slices + cumulative sum are the CSR arrays, and the $\sum$ -based mat–vec is what we make fast.

Equipment checklist

Cover the right side and answer each before moving to D2.

What does $A_{ij}$ mean, and what does $i$ vs $j$ point to? ::: The number in row $i$ , column $j$ ; $i$ = row (down), $j$ = column (across), both 0-based.
What do CSR and CSC stand for? ::: Compressed Sparse Row and Compressed Sparse Column.
What does spsolve do? ::: Takes a sparse matrix $A$ and vector $b$ and returns the $x$ solving $A x = b$ .
What is $n^{2}$ counting for a square matrix? ::: The total number of cells: $n$ rows times $n$ columns.
Define $nnz$ and density $ρ$ . ::: nnz = count of non-zero cells; $ρ = nnz / (n m)$ , the fraction that are non-zero.
What do $≪$ and $\sim$ mean? ::: $≪$ = "very much less than"; $\sim$ = "of roughly this size / order of magnitude."
When does sparse storage stop being worth it? ::: When $ρ$ approaches $\sim 0.1$ or higher; near $ρ = 1$ sparse is bigger and slower than dense.
What does data[2:5] return? ::: Entries at positions 2, 3, 4 — the right end 5 is excluded.
Compute the cumulative sum of counts $[1, 1, 3, 1]$ starting at 0. ::: $[0, 1, 2, 5, 6]$ .
Why is the cumulative-sum array length $n + 1$ ? ::: One bookmark before each of the $n$ rows plus one final end-marker equal to nnz.
What does $j = 0 \sum m - 1 A_{ij} x_{j}$ compute, and over what range? ::: Output entry $y_{i}$ of $y = A x$ , summing over every column $j$ from 0 to $m - 1$ .
What is SpMV? ::: Sparse matrix–vector product: computing $y = A x$ touching only the non-zeros.
What does "solve $A x = b$ " ask for? ::: The unknown input vector $x$ that the matrix $A$ turns into the known output $b$ .
What does $O (n)$ vs $O (n^{2})$ describe? ::: How work grows with problem size — linearly vs quadratically, ignoring constants.