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

5.4.13 · Coding › Scientific Computing (Python)

WHY sparse at all?

WHY it matters: Ek dense $1 0^{6} \times 1 0^{6}$ matrix ko $1 0^{12}$ floats $= 8$ TB chahiye — yeh possible hi nahi hai. Agar har row mein ~5 nonzeros hain, toh $nnz = 5 \times 1 0^{6}$ , ~120 MB mein store ho jaata hai. Same problem, $\sim 1 0^{5} \times$ kam memory.

Teen formats jo tumhe zaroor pata hone chahiye

1. COO — Coordinate (the "scratchpad")

2. CSR — Compressed Sparse Row

3. CSC — Compressed Sparse Column

CSR ko scratch se derive karna (Feynman-style)

Lo $A = 1003000200600040000500 .$

Step 1 — nonzeros ko row by row list karo. Kyun? CSR ki ordering convention hai "har row ko left→right scan karo." Row0: $(0, 10)$ . Row1: $(1, 20)$ . Row2: $(0, 30), (2, 40), (3, 50)$ . Row3: $(1, 60)$ .

Toh data = [10, 20, 30, 40, 50, 60], indices = [0, 1, 0, 2, 3, 1].

Step 2 — har row mein nonzeros count karo. Counts $= [1, 1, 3, 1]$ . Kyun? indptr inhi ka cumulative sum hai, jo humein boundaries batata hai.

Step 3 — cumulative sum, 0 se shuru karo. $indptr = [0, 0 + 1, 1 + 1, 2 + 3, 5 + 1] = [0, 1, 2, 5, 6] .$ Yeh step kyun? Row $i$ data[indptr[i]:indptr[i+1]] mein rehta hai. Row 2 check karo: data[2:5]=[30,40,50] ✓. Aakhri entry $= nnz = 6$ .

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

Worked example: code mein banao aur use karo

import numpy as np
from scipy.sparse import coo_matrix, csr_matrix
from scipy.sparse.linalg import spsolve
 
# COO mein banao (easy), CSR mein convert karo (fast)
rows = [0, 1, 2, 2, 2, 3]
cols = [0, 1, 0, 2, 3, 1]
vals = [10,20,30,40,50,60]
A = coo_matrix((vals, (rows, cols)), shape=(4,4)).tocsr()
 
print(A.indptr)    # [0 1 2 5 6]   <- humari derivation se match karta hai
print(A.indices)   # [0 1 0 2 3 1]
print(A.data)      # [10 20 30 40 50 60]

.tocsr() kyun? COO fast arithmetic ya solves nahi kar sakta; CSR kar sakta hai.

$A x = b$ solve karna

from scipy.sparse import diags
from scipy.sparse.linalg import spsolve, cg
 
n = 1000
# 1D Poisson: tridiagonal [-1, 2, -1]
A = diags([-1, 2, -1], [-1, 0, 1], shape=(n, n), format='csc')
b = np.ones(n)
 
x_direct = spsolve(A, b)          # sparse LU (CSC use karta hai)
x_iter, info = cg(A, b)           # conjugate gradient (sirf SPD ke liye)

spsolve ke liye CSC kyun? Sparse LU factorization columns process karta hai; CSC pass karne se internal conversion bachti hai. cg yahan kyun? Yeh $A$ symmetric positive definite hai, isliye Conjugate Gradient fast converge karta hai aur dense factorization kabhi form nahi karta.

Worked example Solver chunna — WHAT/WHY

Situation	Solver	Kyun
General sparse, exact answer	`spsolve` (LU)	direct, robust
Symmetric positive-definite	`cg`	sasta, sirf $A x$ chahiye
General, large, iterative	`gmres`, `bicgstab`	kam memory
Least squares (non-square)	`lsqr`, `lsmr`	$∥ A x - b ∥$ minimize karo
Direct solvers mein fill-in hoti hai (zeros factorization ke dauran nonzero ho jaate hain); iterative solvers isse avoid karte hain lekin preconditioner ki zaroorat pad sakti hai.

Common mistakes (steel-manned)

Active recall

Recall Quick self-test (answers cover karo)

CSR define karne wale teen arrays kaunse hain? → data, indices, indptr.
indptr ki length? → $n + 1$ .
Row $i$ ke nonzeros kahan rehte hain? → data[indptr[i]:indptr[i+1]].
Direct solvers kaun sa format prefer karte hain? → CSC.
SpMV cost? → $O (nnz)$ .

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek giant spreadsheet jo almost saari khali boxes se bhari hai. Har khali box likhne ki jagah, tum sirf woh boxes likhte ho jisme koi number hai — aur ek chhoti si note saath rakhte ho jisme likha ho "row 2 yahan se shuru hoti hai, row 3 yahan se." Woh note hai indptr: yeh bookmarks ki tarah hai jo batata hai ki har row ke numbers kahan se shuru hote hain, taaki tum seedha kisi bhi row par jump kar sako. Kyunki tumne saari blank jagah skip kar di, computer bahut kam padhta hai aur bahut jaldi khatam karta hai.

Sparse matrices kaun sa problem solve karte hain?

Jo matrices mostly zeros hoti hain woh O(n²) memory/compute waste karti hain; sparse storage sirf nonzeros + coordinates rakhta hai, O(nnz) cost deta hai.

CSR format mein kaunse teen arrays hote hain?

data (nonzeros row-by-row), indices (har nonzero ka column index), indptr (length n+1, row-start offsets).

CSR mein row i ke nonzeros kaise nikalte hain?

data[indptr[i]:indptr[i+1]] at columns indices[indptr[i]:indptr[i+1]].

CSR indptr ki length aur last value kya hoti hai?

Length n+1; last value nnz (total nonzeros) ke barabar hoti hai.

CSC, CSR se kaise alag hai?

CSC column-by-column store karta hai: indices mein row indices hote hain, indptr column starts mark karta hai; fast column slicing aur direct solvers use karte hain ise.

Sparse matrix COO (ya LIL/DOK) mein kyun banate hain phir convert karte hain?

COO/LIL mein insertion sasta hai; CSR/CSC mein insertion O(nnz) ka hai. Ek baar banao, ek baar convert karo.

CSR mein sparse matrix-vector product y=Ax ki cost kya hai?

O(nnz), har row ke slice mein data[k]*x[indices[k]] sum karte hain.

Sparse matrix kab use NAHI karni chahiye?

Jab density zyada ho (≳10%): index overhead (2·nnz ints) sparse ko dense se bada aur slow bana sakti hai.

Sparse solve karne wala scipy function kaun sa hai aur woh kaun sa format pasand karta hai?

spsolve (sparse LU); CSC input prefer karta hai.

cg (conjugate gradient) kab valid hai, aur otherwise kya use karein?

cg ko symmetric positive-definite A chahiye; general matrices ke liye gmres/bicgstab use karo.

Fill-in kya hoti hai?

Woh zeros jo LU/Cholesky factorization ke dauran nonzero ho jaate hain, memory badhata hai; iterative solvers isse avoid karte hain.

Modern scipy.sparse mein matrix multiply aur elementwise multiply kaise karte hain?

A @ x matrix product ke liye; A.multiply(B) elementwise ke liye.

Connections

Dense matrices (NumPy ndarray) — woh baseline jisko sparse improve karta hai.
LU decomposition aur Cholesky decomposition — spsolve under the hood yahi karta hai.
Conjugate Gradient method / Krylov subspace methods — iterative cg, gmres.
Preconditioning — iterative sparse solvers ko accelerate karta hai.
Finite element method / PDE discretization — sparse systems ka main source.
Graph adjacency matrices — graphs naturally sparse hote hain.
Big-O complexity — kyun O(nnz) beats O(n²).