chapter  2
48 Pages

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.