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

---

The scenario matrix

Every example is tagged with the cell of this table it covers. By the end, every cell has a green tick.

#	Case class	What is unusual here	Example that covers it
C1	Standard build + verify indptr	the "normal" case	Ex 1
C2	Empty row (all zeros in a row)	indptr repeats a value	Ex 2
C3	Duplicate COO entries	must be summed on convert	Ex 3
C4	Degenerate density (nearly dense)	sparse costs more	Ex 4
C5	SpMV by hand, row-slice formula	verify $y_i$ sum	Ex 5
C6	SPD system → cg	symmetric positive-definite	Ex 6
C7	Non-symmetric system → spsolve/gmres	cg would be wrong	Ex 7
C8	Singular (degenerate) matrix	no unique solution	Ex 8
C9	Real-world word problem: graph	adjacency → reachability	Ex 9
C10	Exam twist: reconstruct $A$ from raw arrays	reverse the format	Ex 10

Prerequisites used along the way: Dense matrices (NumPy ndarray), LU decomposition, Conjugate Gradient method, Graph adjacency matrices, Big-O complexity.

---

Ex 1 — The standard build (C1)

Forecast: row counts are $[1,1,3,1]$, so indptr should be their running total starting at 0.

1. List nonzeros row by row. Why this step? CSR's rule is "scan each row left→right", so the storage order is fixed by the rows. Row0 $(0,10)$; Row1 $(1,20)$; Row2 $(0,30),(2,40),(3,50)$; Row3 $(1,60)$. → data = [10,20,30,40,50,60], indices = [0,1,0,2,3,1].
2. Count per row → cumulative-sum. Why? indptr[i] must equal how many nonzeros came before row $i$, so a running total is exactly the boundary list. Counts $[1,1,3,1]$ → indptr = [0,1,2,5,6].

Verify: data[indptr[2]:indptr[3]] = data[2:5] = [30,40,50] — the three entries of row 2. ✓ Last value of indptr $=6=\text{nnz}$. ✓

---

Ex 2 — An empty row (C2)

Forecast: row 1 has zero nonzeros, so its "start" and the next "start" must be the same number.

1. List nonzeros. Why? Same left→right rule. Row0 $(0,5)$; Row1 (nothing); Row2 $(1,7),(2,8)$. → data=[5,7,8], indices=[0,1,2].
2. Cumulative counts. Counts $[1,0,2]$. Why the 0? An empty row adds nothing, so the cumulative total does not advance. indptr = [0, 1, 1, 3].

3. Read back row 1. data[indptr[1]:indptr[2]] = data[1:1] = []. Why empty? A zero-width slice — exactly what "no nonzeros" should return.

Verify: length of indptr $=4=n+1$ with $n=3$. ✓ Last value $=3=\text{nnz}$. ✓

---

Ex 3 — Duplicate COO entries (C3)

Forecast: COO is a scratchpad that allows duplicates; conversion should sum them, so $C_{00}=3+4=7$.

1. Write the triples. Why COO? It is the only format that tolerates the same $(i,j)$ twice — the parent note flagged this as its build-time superpower. $(0,0,3),(0,0,4),(1,1,9)$.
2. Convert to CSR. Why does summing happen now? CSR requires each column index to appear once per row; the constructor collapses duplicates by addition. $C=\left(\begin{array}{cc}7& 0\\ 0& 9\end{array}\right)$, data=[7,9], indices=[0,1], indptr=[0,1,2].

Verify: $C_{00}=7$, $C_{11}=9$, $\text{nnz}=2$. ✓

---

Ex 4 — Degenerate density: sparse is worse (C4)

Forecast: CSR stores $2\text{nnz}+(n+1)$ numbers. With so many nonzeros this may exceed the dense $n^2$.

1. Dense cost. Why the baseline? Dense matrices (NumPy ndarray) stores every cell: $n\cdot m=100\times 100=10000$ numbers.
2. CSR cost. Why this formula? One data + one indices per nonzero, plus indptr of length $n+1$: $2\text{nnz}+(n+1)=2(9500)+101=19101.$

Verify: $19101>10000$ — sparse is nearly double the memory here. ✓ Confirms the parent's rule: use sparse only when $\rho \lesssim 0.1$.

---

Ex 5 — Sparse mat–vec by hand (C5)

Forecast: Row 2 is the busy one: $30\cdot 1+40\cdot 3+50\cdot 4$ dominates.

The parent's formula: $y_i={\sum }_{k=\text{indptr}[i]}^{\text{indptr}[i+1]-1}\text{data}[k]\cdot x[\text{indices}[k]].$

1. Row 0: slice data[0:1]=[10] at cols [0] → $10\cdot x_0=10\cdot 1=10$. Why the slice? indptr[0:1]=[0,1] bounds it.
2. Row 1: data[1:2]=[20] at col [1] → $20\cdot 2=40$.
3. Row 2: data[2:5]=[30,40,50] at cols [0,2,3] → $30\cdot 1+40\cdot 3+50\cdot 4=30+120+200=350$.
4. Row 3: data[5:6]=[60] at col [1] → $60\cdot 2=120$.

So $y=(10,40,350,120{)}^{\mathsf{T}}$. Why is this $O(\text{nnz})$? We touched each of the 6 nonzeros exactly once — never the zeros (see Big-O complexity).

Verify: dense check $Ax=(10,40,350,120{)}^{\mathsf{T}}$. ✓

---

Ex 6 — SPD system with Conjugate Gradient (C6)

Forecast: this matrix is symmetric and (as the tridiagonal Laplacian) positive-definite, so CG applies and should give a clean rational answer.

1. Check SPD. Why check first? CG assumes symmetric positive-definite; using it blindly is the parent's fourth mistake. Symmetric: $A=A^{\mathsf{T}}$ ✓. Positive-definite: leading minors are $2,3,4$ — all $>0$ ✓.
2. Solve. Why by hand is fine? Only $3\times 3$; the sparse solver would return the same. Gaussian elimination gives $x={\left(\frac{3}{2},2,\frac{3}{2}\right)}^{\mathsf{T}}.$

3. Why CG in practice? Why not LU? For the real $n=10^6$ version, CG only needs the product $Ax$ (which is $O(\text{nnz})$) and never forms a dense factor — no fill-in.

Verify: $Ax=(2\cdot \frac{3}{2}-2,-\frac{3}{2}+4-\frac{3}{2},-2+2\cdot \frac{3}{2})=(1,1,1)$. ✓

---

Ex 7 — Non-symmetric system: cg is illegal here (C7)

Forecast: $M\ne M^{\mathsf{T}}$, so CG is invalid; use spsolve (sparse LU) or gmres.

1. Reject CG. Why? $M_{01}=2$ but $M_{10}=0$ — not symmetric, so CG's core assumption fails and it may diverge.
2. Back-substitute (it's upper-triangular). Why triangular helps? LU's whole game is to reach a triangular system, then solve cheaply. Row 2: $3x_1=9\Rightarrow x_1=3$. Row 1: $x_0+2(3)=5\Rightarrow x_0=-1$. $x=(-1,3{)}^{\mathsf{T}}.$

Verify: $Mx=(1(-1)+2(3),3(3))=(5,9)$. ✓

---

Ex 8 — Singular / degenerate system (C8)

Forecast: row 2 is exactly $2\times$ row 1, so $\det S=0$ — the matrix is singular, no unique solution.

1. Compute the determinant. Why? A direct solver needs an invertible $A$; $\det =0$ means LU hits a zero pivot. $\det S=1\cdot 4-2\cdot 2=0$.
2. Interpret. Why not just an error? The two equations $x_0+2x_1=3$ and $2x_0+4x_1=6$ are the same line — infinitely many solutions (e.g. $x=(3,0)$ or $(1,1)$). spsolve warns of a singular matrix / returns nan or inf.

Verify: both $(3,0)$ and $(1,1)$ satisfy $Sx=b$: $S(3,0)=(3,6)$ and $S(1,1)=(3,6)$. ✓ (Two distinct solutions ⇒ not unique.)

---

Ex 9 — Real-world word problem: a friendship graph (C9)

Forecast: $A_{ij}^2$ counts walks of length 2 from $i$ to $j$; the diagonal counts "there-and-back" (equal to each node's degree).

1. Build $A$. Why sparse? A real social graph has millions of nodes but each person has a handful of friends — the classic sparse case. $A=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right).$
2. Square it. Why $A^2$? Matrix-multiply chains edges: $(A^2{)}_{ij}={\sum }_k{A}_{ik}{A}_{kj}$ counts a friend-of-a-friend route $i\to k\to j$. Use A @ A (the parent warned: @, never * for old-style ambiguity). $A^2=\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 2& 0& 1\\ 1& 0& 2& 0\\ 0& 1& 0& 1\end{array}\right).$

3. Read it. Why the diagonal? $(A^2{)}_{11}=2$ = person 1's degree (2 friends), i.e. two "out-and-back" walks. $(A^2{)}_{02}=1$: person 0 reaches person 2 in exactly one 2-hop route (via person 1).

Verify: $(A^2{)}_{02}=1$, diagonal $=(1,2,2,1)=$ degrees. ✓

---

Ex 10 — Exam twist: reconstruct $A$ from raw arrays (C10)

Forecast: indptr=[0,1,1,3] has a repeated 1 → row 1 is empty (same trap as Ex 2).

1. Split by row using indptr. Why? indptr[i]:indptr[i+1] is exactly row $i$'s slice.
   • Row 0: [0:1] → value $7$ at col indices[0]=2.
   • Row 1: [1:1] → empty.
   • Row 2: [1:3] → values $8,9$ at cols indices[1:3]=[0,1].
2. Assemble. Why place by (row, col)? data[k] sits at row (from the slice it fell in) and column indices[k]. $A=\left(\begin{array}{ccc}0& 0& 7\\ 0& 0& 0\\ 8& 9& 0\end{array}\right).$

Verify: $\text{nnz}=3=$ last indptr. ✓ Nonzero positions $(0,2),(2,0),(2,1)$ with values $7,8,9$. ✓

---

Active recall

Recall Which solver for which matrix?

• Symmetric positive-definite ::: Conjugate Gradient (cg).
• Non-symmetric, exact ::: spsolve (LU) or gmres.
• Singular ($\det =0$) ::: no unique solution — no direct solver works.

Recall Trap checks

• Empty row in CSR shows up as… ::: a repeated value in indptr (never a missing slot).
• Duplicate COO triples become… ::: summed on .tocsr().
• Sparse beats dense only when… ::: density $\rho \lesssim 0.1$; near-dense it uses more memory.