Skip to content
Tutorials Center
My learning

Topics

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

Sparse Linear Algebra and Graph Algorithms

Solve huge sparse systems with spsolve and cg, find a few eigenvalues with eigsh and svds, and run shortest paths, components and spanning trees with csgraph.

A sparse matrix is only useful if you can do something with it. Storing a million-row matrix with five non-zeros per row is cheap, but a dense solver would still try to build all one trillion entries. SciPy therefore has a second set of tools that work directly on sparse storage: scipy.sparse.linalg for solving systems and computing eigenvalues, and scipy.sparse.csgraph for graph algorithms where the sparse matrix is the graph.

This lesson builds on Sparse Matrices, where you met the CSR and CSC formats. We will solve a tridiagonal system two ways (direct and iterative), pull a few eigenvalues out of a large matrix, and then treat a matrix as a weighted graph.

flowchart TD
    A["Sparse problem"] --> B{"What do you need?"}
    B -->|"solve A x = b"| C{"Symmetric positive<br/>definite and huge?"}
    C -->|"no or medium size"| D["spsolve / splu"]
    C -->|"yes"| E["cg (iterative)"]
    B -->|"a few eigenvalues"| F["eigsh (symmetric)<br/>eigs (general)"]
    B -->|"a few singular values"| G["svds"]
    B -->|"paths, components, trees"| H["csgraph"]

Choose the routine by the question you are asking, not by the matrix format.

Direct solving with spsolve

spsolve(A, b) solves A x = b by sparse LU factorization. It prefers CSC format; if you pass something else, SciPy converts it and may warn. The test problem below is the classic one-dimensional Poisson equation: a tridiagonal matrix with 2 on the diagonal and -1 next to it. It describes, for example, the shape of a loaded string.

Python spsolve on a tridiagonal system

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 dense solve of the same 2000 by 2000 problem would copy four million numbers and cost billions of operations; the sparse solve touches about six thousand numbers. When you must solve with the same matrix and many different right-hand sides one after another, factor once with splu(A) and call .solve(b) repeatedly, exactly as lu_factor does for dense matrices.

Warning: Sparse LU can suffer from fill-in: the factors may contain many more non-zeros than the original matrix. Tridiagonal and banded matrices have almost none, but matrices that come from 2D or 3D grids fill in a lot. If memory explodes, try an iterative solver.

Iterative solving with cg

Direct solvers give an exact answer (up to rounding) but need the factorization in memory. Iterative solvers only need to multiply the matrix by a vector, so they use very little memory, and they stop when the answer is "good enough". The conjugate gradient method, cg, is the standard choice when the matrix is symmetric and positive definite (SPD), which covers most discretized physics problems.

cg(A, b, rtol=..., callback=...) returns the solution and an integer info: 0 means success, a positive number means it ran out of iterations. A callback receives the current iterate at every step, which is the easy way to count iterations.

Python Conjugate gradients and preconditioning

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 number of iterations grows as the matrix gets harder (a larger condition number; see Matrices, Solving Systems and Inverses). A preconditioner M approximates the inverse of A cheaply and can cut the iteration count dramatically. For this particular matrix the diagonal is constant, so the Jacobi preconditioner changes nothing; on matrices with a wildly varying diagonal it helps a lot. Do not expect cg to work on matrices that are not symmetric positive definite: use gmres or bicgstab instead.

A few eigenvalues with eigsh and svds

A full eigendecomposition costs O(nยณ) and needs a dense matrix. Often you only want the largest few eigenvalues (dominant modes) or the smallest few (lowest frequencies). eigsh handles symmetric matrices, eigs general ones, and both use the Lanczos/Arnoldi family of methods that only need matrix-vector products. svds does the same for singular values.

The 1D Poisson matrix has known eigenvalues, 2 โˆ’ 2cos(kฯ€/(n+1)) for k = 1โ€ฆn, so we can check our answers.

Python eigsh and svds

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.

Two details trip people up. First, results are not sorted in a guaranteed way, so sort them yourself. Second, asking for the smallest eigenvalues with which="SM" converges painfully slowly; the shift-invert mode (sigma=0, which="LM") turns "smallest" into "largest of the inverse" and finishes in a moment. You can also set sigma to any number to find the eigenvalues closest to it.

Graphs as sparse matrices

A weighted graph with n nodes is just an n by n matrix: entry (i, j) holds the weight of the edge from i to j. Most graphs have far fewer edges than node pairs, so the matrix is sparse, and scipy.sparse.csgraph runs classic algorithms directly on it. In a sparse graph, a missing entry means "no edge", not "edge of weight zero". If you need zero-weight edges, use a dense array with a different marker such as np.inf.

If you want the theory behind these algorithms, the data-structures track covers them in depth: Graph Representations, Dijkstra's Algorithm, Connected Components and Minimum Spanning Tree. Here we focus on calling the SciPy versions.

Python Shortest paths on a small road network

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.

dijkstra needs non-negative weights; shortest_path(method="BF") (Bellman-Ford) accepts negative ones; "FW" (Floyd-Warshall) computes every pair, and "auto" chooses for you. Unreachable nodes get distance inf and predecessor -9999, which is why the loop above stops at any negative predecessor.

Traversal: breadth-first and depth-first order

Shortest paths are not the only question you ask a graph. Sometimes you want a visiting order from a start node: which nodes can I reach, and in what sequence? csgraph provides two traversals:

  • breadth_first_order(G, i_start, directed=True, return_predecessors=True) visits the start node, then all its neighbors, then their neighbors, and so on, level by level. It finds the fewest-edges route to every reachable node and ignores edge weights.
  • depth_first_order(G, i_start, ...) follows one branch as deep as it can before backing up.

Both return the visiting order as an array (only reachable nodes appear) and, with return_predecessors=True, a predecessor array: pred[j] is the node from which j was first reached, and -9999 marks the start node and unreachable nodes. Following the predecessors backwards from any node rebuilds the path to it. The related functions breadth_first_tree and depth_first_tree return the traversal as a sparse tree. A graph can also be made from a dense adjacency matrix: csgraph_from_dense(A, null_value=0) converts it, and csgraph_to_dense(G) goes the other way.

Python Visiting order, predecessors and a tree from a start node

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.

Breadth-first search visits node 0, then its neighbors 1 and 2, then theirs, so the route to node 5 has the fewest edges possible (two edges: 0 to 2 to 5). Depth-first search dives down one branch first, so its order looks different, but both reach the same six nodes and never reach node 6. The tree has one edge fewer than the number of reached nodes, as every tree does.

Components and spanning trees

connected_components labels each node with the id of its component. For directed graphs, connection="weak" ignores edge direction while "strong" requires a path both ways. minimum_spanning_tree returns a new sparse graph containing the cheapest set of edges that still connects every node of a component.

Python Components and a minimum spanning tree

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.

Because the graph has two islands, the result is a spanning forest with n - components edges: 7 nodes and 2 components give 5 edges. The directed chain 0 โ†’ 1 โ†’ 2 โ†’ 3 is one weak component but four strong ones, because you cannot walk backwards.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which sparse format does spsolve prefer for its matrix argument?

    spsolve uses a sparse LU factorization that works on CSC (or CSR converted to CSC). Passing another format makes SciPy convert it and may produce a warning.
  2. 2. When is the conjugate gradient method cg appropriate?

    cg is designed for symmetric positive definite systems. For non-symmetric systems use gmres or bicgstab instead.
  3. 3. What is the best way to get the smallest few eigenvalues of a large sparse symmetric matrix with eigsh?

    Shift-invert turns the smallest eigenvalues into the largest of the inverse operator, which the Lanczos method finds quickly. which='SM' converges slowly.
  4. 4. In a sparse csgraph input, what does a missing entry mean?

    Sparse zeros are not stored and are treated as absent edges. If you need real zero-weight edges, use a dense array with another marker for 'no edge'.
  5. 5. A directed chain 0 -> 1 -> 2 -> 3 is analyzed with connected_components. What do you get?

    Ignoring direction, all four nodes are linked (one weak component). A strong component needs paths both ways, so each node is on its own.

Summary

  • spsolve solves sparse systems directly (CSC preferred); use splu to reuse a factorization, and watch out for fill-in.
  • cg is an iterative solver for symmetric positive definite matrices; check info, count steps with a callback and add a preconditioner M for hard problems.
  • eigsh and svds return only a few eigenvalues or singular values; use sigma=0, which="LM" for the smallest ones and sort the output yourself.
  • scipy.sparse.csgraph treats a sparse matrix as a graph where missing entries mean no edge: dijkstra/shortest_path, connected_components and minimum_spanning_tree cover the common tasks.

Next up: points in space, nearest neighbours and geometry in Spatial Algorithms.