Solving Sparse Matrix Systems in Rust

And introducing sparse21 on crates.io

This chapter of Software Makes Hardware dives into two topics:

• Part 1 introduces sparse-matrix solvers: where they’re needed, how they work, and popular algorithms & data structures that solve them efficiently.
• Part 2 provides a short intro to the Rust language, and surveys its pros & cons for the problem at hand.

All of the code shown here is available in the sparse21 crate on crates.io, Rust’s built-in package repository.

Part 1: Sparse Matrix Solvers

Figure 1: Example pattern of non-zero elements in a sparse matrix. Copyright Apple developer documentation.

Tons of physical problems boil down to solving systems of linear equations. In a past chapter of SwMakesHw, we introduced one such problem: (analog) circuit simulation. It can be broken into two areas: (a) linearizing non-linear systems of equations, and (b) solving those linear systems. Sparse-matrix methods are a powerful tool for part (b), along with a wide variety of other problems in the sciences, engineering, and graph analysis.

Linear Systems