Combinatorial Problems in Solving Linear Systems
In this short review paper, we examine the interplay between the solution of sparse linear systems and combinatorics. Most of this strong association comes from the identification of sparse matrices with graphs so that most algorithms dealing with sparse matrices have a close or exact analogue to an algorithm on a graph. We examine these analogues both in the case of
the direct solution of sparse linear equations and their solution by iterative methods, particularly focusing on preconditioning.