Sparse matrices

Store only what is not zero

Many large matrices are almost all zeros. A grid for pricing an option has a row for each price level, and each row touches only its two neighbours. A matrix like that is called sparse. Storing every zero wastes memory and time. scipy.sparse keeps only the non-zero entries. The format csr_matrix (compressed sparse row) uses three lists. data holds the non-zero values row by row, indices holds the column of each value, and indptr says where each row starts and ends inside data: row $i$ is data[indptr[i]:indptr[i+1]]. The last number of indptr is the count of non-zeros, nnz.

Different formats suit different jobs. coo_matrix stores plain (row, column, value) triples and is the easy way to build a matrix. csr_matrix is fast for row slices and for the product $A\mathbf x$ , which costs about nnz multiplications instead of $n^2$ . csc_matrix is the same idea by columns, and dia_matrix stores diagonals, ideal for banded matrices. For a system $A\mathbf x=\mathbf b$ , sparse.linalg.spsolve uses the zeros to be much faster than a dense solve. Sparse is not always better: if more than about a third of the entries are non-zero, the bookkeeping costs more than it saves. In finance, sparsity appears in pricing grids, in factor models where most loadings are zero, and when you keep only the strong correlations.

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

Reading a CSR matrixTake the

4\times4

matrix with rows

(5,0,0,1)

(0,0,2,0)

(0,0,0,0)

and

(3,0,0,4)

. In CSR, data=[5,1,2,3,4], indices=[0,3,2,0,3] and indptr=[0,2,3,3,5]. Row

2

is empty because indptr[2]=indptr[3]=3, and nnz=5. Multiplying by

(1,1,1,1)

adds up each row, giving

(6,2,0,7)

with only

5

multiplications. A tridiagonal matrix with

n=1000

, like a finite-difference pricing grid, has

2{,}998

non-zeros out of

1{,}000{,}000

entries, a density of

0.30\%

. It needs about

40

KB in CSR against

8

MB dense. On real data, the correlations of

55

stocks from the shared price file form a

55\times55

matrix. Keeping only entries with

|\rho|>0.5

leaves

249

3{,}025

entries,

8.2\%

, and the CSR copy takes

3.2

KB against

24.2

KB dense. At

|\rho|>0.6

only

4.3\%

remain.

Three lists: data, indices and indptr describe a CSR matrix, and indptr[-1] is the number of non-zeros.
Build in COO, compute in CSR: triples are easy to assemble, row-based storage is fast for products and solves.
Sparse pays only when mostly zero: a dense matrix is better when many entries are non-zero.

Lab · what's graded

Counting non-zeros10 pts
How many values in a row10 pts
The density of a grid10 pts
A sparse product15 pts
Which format for which job15 pts
A tridiagonal system10 pts
When sparse pays and when it does not30 pts

Store only what is not zero

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

Reading a CSR matrixTake the

4\times4

matrix with rows

(5,0,0,1)

(0,0,2,0)

(0,0,0,0)

and

(3,0,0,4)

. In CSR, data=[5,1,2,3,4], indices=[0,3,2,0,3] and indptr=[0,2,3,3,5]. Row

2

is empty because indptr[2]=indptr[3]=3, and nnz=5. Multiplying by

(1,1,1,1)

adds up each row, giving

(6,2,0,7)

with only

5

multiplications. A tridiagonal matrix with

n=1000

, like a finite-difference pricing grid, has

2{,}998

non-zeros out of

1{,}000{,}000

entries, a density of

0.30\%

. It needs about

40

KB in CSR against

8

MB dense. On real data, the correlations of

55

stocks from the shared price file form a

55\times55

matrix. Keeping only entries with

|\rho|>0.5

leaves

249

3{,}025

entries,

8.2\%

, and the CSR copy takes

3.2

KB against

24.2

KB dense. At

|\rho|>0.6

only

4.3\%

remain.

Three lists: data, indices and indptr describe a CSR matrix, and indptr[-1] is the number of non-zeros.
Build in COO, compute in CSR: triples are easy to assemble, row-based storage is fast for products and solves.
Sparse pays only when mostly zero: a dense matrix is better when many entries are non-zero.

Lab · what's graded

Counting non-zeros10 pts
How many values in a row10 pts
The density of a grid10 pts
A sparse product15 pts
Which format for which job15 pts
A tridiagonal system10 pts
When sparse pays and when it does not30 pts

Store only what is not zero

Lab · what's graded

Log in to run your code.

Sparse matrices

Store only what is not zero

Lab · what's graded

Log in to run your code.