Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 38 ยท Sparse, Spatial and Image Data

Sparse Matrices

Store mostly-zero data efficiently with scipy.sparse: COO, CSR, CSC and LIL formats, sparse arrays versus matrices, conversions, memory savings, products and common pitfalls.

Many large matrices are almost entirely zeros. A table of which of 100,000 users watched which of 50,000 films has a tiny fraction of non-zero cells. The links between web pages, the word counts of documents, the connections in a road network and the equations that arise from physical simulations are all like this. Storing every zero wastes memory and time: a dense 100,000 by 100,000 matrix of 64-bit floats needs 80 GB, but if each row has only five non-zero entries, a sparse representation fits in a few megabytes.

scipy.sparse provides several storage formats that remember only the non-zero entries and their positions. Choosing the right format for the job (building, slicing, multiplying) is the main skill, and this lesson shows each format, how to convert between them, how much memory you save, and the pitfalls to avoid. The next lesson, Sparse Linear Algebra and Graph Algorithms, puts these matrices to work.

flowchart LR
    B["building / editing"] --> L["LIL, DOK, COO"]
    L -->|"tocsr()"| R["CSR<br/>fast row slicing,<br/>matrix-vector products"]
    L -->|"tocsc()"| C["CSC<br/>fast column slicing,<br/>solvers"]
    R <-->|"tocsc() / tocsr()"| C
    R --> A["arithmetic and linear algebra"]
    C --> A

Build in a flexible format, convert once to CSR or CSC for computation.

Arrays versus matrices

SciPy has two parallel APIs. The older sparse matrices (csr_matrix, coo_matrix, ...) behave like np.matrix: the * operator is matrix multiplication and results are always two-dimensional. The newer sparse arrays (csr_array, coo_array, ...) behave like NumPy arrays: * is element-wise and @ is matrix multiplication. New code should use the array classes, which is what this lesson does; the formats and methods are otherwise identical.

Building a sparse array

The simplest way to describe a sparse array is COO (coordinate) format: three lists with the row index, column index and value of each non-zero entry. It is very easy to build from data, but it does not support arithmetic well, so you normally convert it afterwards. Entries that appear twice are summed during conversion, a feature that makes COO ideal for assembling things like counts or finite-element matrices.

Python From coordinates to a matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

sparse.diags_array is the usual way to build banded matrices such as the second-difference matrix at the end of the example. sparse.random_array makes random test matrices with a chosen density.

Inside CSR: three arrays

CSR (compressed sparse row) is the workhorse format. It stores the non-zero values row by row in three arrays:

  • data: the non-zero values, in row order;
  • indices: the column index of each value;
  • indptr: for each row, where its entries start in data. Row i occupies data[indptr[i]:indptr[i + 1]].

Because rows are contiguous, CSR can slice rows quickly and multiply by a vector in one pass over data. CSC (compressed sparse column) is the same idea with the roles of rows and columns swapped: it slices columns quickly and is the preferred input for many direct solvers.

Python Looking at the CSR arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The indptr array has one more entry than there are rows, and an empty row simply repeats the previous pointer. Seeing this layout makes the performance rules below obvious.

The memory saving

To measure what a sparse matrix really costs, add up data.nbytes + indices.nbytes + indptr.nbytes. A dense float64 matrix always costs rows * columns * 8 bytes, whatever the values.

Python How much memory does sparsity save?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sparse storage only pays off when the matrix really is sparse. Every stored entry costs about 12 bytes (an 8-byte value plus a 4-byte index), compared with 8 bytes for a dense cell, so beyond roughly 10 to 30% non-zeros the dense array is both smaller and faster. For those, use NumPy.

Fast products

The operation sparse matrices are built for is multiplying by a vector (or a dense matrix): the cost is proportional to the number of stored entries instead of the full size. Use @; the result of sparse @ dense_vector is a plain dense NumPy array.

Python Sparse matrix-vector products

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the product A @ A has more non-zero entries than A: multiplying sparse matrices can fill in zeros, so repeated products of a sparse matrix can quickly become nearly dense.

LIL and DOK for incremental building

Changing the sparsity structure of a CSR matrix is expensive, because inserting one entry shifts the arrays after it. SciPy even warns you. For editing entry by entry use LIL (a list of rows) or DOK (a dictionary keyed by coordinates), then convert when finished. Both are slow for arithmetic. A typical script builds in LIL or COO and works in CSR or CSC.

Python Edit in LIL, compute in CSR

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A related trap: assigning zero to an entry does not shrink the matrix. The zero remains stored until you call eliminate_zeros().

Which format when?

Format Strong at Weak at
COO Assembling from coordinates, summing duplicates, fast conversion Arithmetic, indexing and slicing
CSR Row slicing, matrix-vector products, most arithmetic Changing the structure, column slicing
CSC Column slicing, direct solvers, factorizations Changing the structure, row slicing
LIL Setting entries one at a time, row slicing Arithmetic, memory use
DOK Random single-entry access and updates Arithmetic, slicing, large data

If you are unsure, build in COO and convert with .tocsr(). Check A.format after an operation: SciPy sometimes returns a different format than you passed in, and some solvers convert silently, which can cost time.

Pitfalls to avoid

  1. toarray() on a big matrix allocates the full dense array; a matrix that fits sparsely can easily exhaust memory when densified.
  2. Operations that make every entry non-zero such as adding a constant. With sparse arrays A + 1 is refused for this reason. Handle such cases mathematically (for example keep the constant as a separate term).
  3. Fill-in from products and inverses: inv(A) of a sparse matrix is usually dense. Solve systems instead of inverting, as you will see in the next lesson.
  4. Loops over entries in Python. Work with whole data, indices and indptr arrays or with vectorized operations.
  5. Mixing formats and expecting speed. Row slicing on CSC and column slicing on CSR both work but are slow.
Python A few of the traps in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines show the old and new semantics side by side. Choose one API and stay with it within a project so that * always means the same thing.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A 100,000 x 100,000 float64 matrix has 500,000 non-zero entries. Roughly how does sparse CSR storage compare with dense storage?

    Dense needs 80 GB. CSR needs about 12 bytes per entry plus a row-pointer array, a few megabytes in total.
  2. 2. Which format is best for building a matrix from a list of (row, column, value) triples?

    COO stores exactly such triples, sums duplicates on conversion, and converts quickly to CSR or CSC.
  3. 3. What does indptr[i] to indptr[i + 1] describe in a CSR matrix?

    indptr holds, for each row, the start of its entries in data and indices; the next pointer marks the end.
  4. 4. With csr_array, what does A * B do?

    Sparse arrays follow NumPy semantics: * is element-wise and @ is matrix multiplication. The older csr_matrix uses * for matrix multiplication.
  5. 5. Why is it a bad idea to compute the inverse of a large sparse matrix?

    Even simple sparse matrices often have completely dense inverses. Solve the system with a sparse solver instead.

Summary

  • scipy.sparse stores only non-zero entries; use the array classes (csr_array, coo_array, ...) where * is element-wise and @ is matrix multiplication.
  • COO is for assembling from coordinates (duplicates are summed); LIL and DOK allow cheap edits; CSR and CSC are for computation, with fast row and column slicing respectively.
  • CSR keeps data, indices and indptr; row i lives in data[indptr[i]:indptr[i + 1]].
  • Sparse storage pays off only for genuinely sparse data, typically well below 10 to 30% non-zeros.
  • Sparse matrix-vector products cost time proportional to nnz; products of sparse matrices can fill in.
  • Avoid toarray() on large matrices, scalar additions, inverses and Python loops over entries; remove stored zeros with eliminate_zeros().

Next up: solve equations and analyze graphs with sparse matrices in Sparse Linear Algebra and Graph Algorithms.