Advanced Systems

Sparse Matrices & Iterative Methods

Efficient storage and solution techniques for large-scale systems where zeros dominate.

Application: Latent Semantic Analysis

Consider document analysis (NLP). We map terms to documents.

D1: "I love numerical analysis"

D2: "I do not love numerical analysis, but I love linear algebra."

	I	love	numerical	linear	algebra
D1	1	1	1	0	0
D2	1	2	0	1	1

In real world applications, this matrix $X$ is massive and mostly zeros.

Sparse Matrices

Definition

An $m \times n$ matrix is sparse if it has $\mathcal{O}(\min(m, n))$ nonzero entries. Roughly a constant number of nonzeros per row.

"Matrices that allow special techniques to take advantage of the large number of zero elements." — J. Wilkinson

The Economic Goal

Perform standard matrix computations without storing the zeros.

Dense Add: $\mathcal{O}(n^2)$
Sparse Add: $\mathcal{O}(nnz(A) + nnz(B))$

Storage Formats

COO (Coordinate Format)

Store $(row, col, value)$ tuples. Simple, good for entry.

A = [ 1 0 0 2 0 ; ... ]

AA = [ 1.0, 2.0, ... ]
JR = [ 1, 1, ... ]
JC = [ 1, 4, ... ]

CSR (Compressed Sparse Row)

Compress the row indices. Fast row access.

AA = [ values ... ]
JA = [ col_indices ... ]
IA = [ row_offsets ... ]

Length of AA, JA is $nnz$. Length of IA is $n+1$.

DIA
Diagonal

ELL
Ellpack

LIL
Linked List

SSK
Skyline

Interactive Example

Consider Matrix $A$:

\[ \begin{bmatrix} 7 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 0 & 6 & 4 \end{bmatrix} \]

CSR Representation

AA: [7, 1, 2, 2, 2, 2, 5, 5, 6, 4]

JA: [1, 2, 3, 2, 4, 4, 5, 5, 6]

IA: [1, 2, 4, 6, 7, 9]

Sparse Operations

Matrix-Vector ($z = Ax$)

% General Logic
z = 0
for i = 1 to m
    for col in A(i,:)
        z(i) += A(i,col) * x(col)
    end
end

Cost: $\mathcal{O}(nnz)$

Matrix-Matrix ($Z = AB$)

% Row-wise logic
Z = 0
for i = 1 to m
    for colA in A(i,:)
        for colB in B(colA,:)
            Z(i,colB) += A(i,colA) * B(colA,colB)
        end
    end
end

Problem: $Z$ is sparse but structure is unknown beforehand.

Iterative Methods

Instead of direct factorization (like LU), we iteratively improve an approximate solution $x_k$.

Basic Idea

Split $A = N + M$. Then $Ax = b \Rightarrow (N+M)x = b \Rightarrow Nx = b - Mx$.

$x_k = N^{-1}(b - M x_{k-1})$

Careful choice of $N$ and $M$ makes this effective.

🧠 Final Challenge +20 XP

In Compressed Sparse Row (CSR) format, what does the `IA` array store?