An Introduction to Sparse Linear Algebra: Storage, Solvers, and Open Problems

Abstract

Sparse linear algebra is the study of linear systems Ax = b in which the matrix A contains overwhelmingly many zero entries. Such systems arise throughout applied mathematics and engineering from the discretization of partial differential equations on large grids, to network analysis, circuit simulation, and structural mechanics and their efficient solution is a cornerstone of scientific computing. In this survey we trace the development of sparse matrix methods from their mathematical foundations through to the current frontiers of research. We begin by defining sparsity and its practical consequences, discuss the principal storage formats (COO, CSR, CSC, and friends), then survey direct solvers based on matrix factorizations and the reordering heuristics that make them tractable. We then turn to iterative Krylov subspace meth-ods, which remain a central tool for the largest systems. We conclude by sketching several open problems that are actively discussed today, including unresolved questions about Krylov convergence, finite-precision behavior, and sparse computation at scale.

Domains and classifications

Version history

Expositio keeps public paper versions together so readers can see the current PDF while still understanding how the record has changed.