Iteratively Solving Large Sparse Systems on Parallel Computers.

Abstract

Large systems of linear equations arise frequently as building blocks in many areas of scientific computing. Often, these linear systems are somehow structured or sparse, i.e., only a small number of the entries of the coefficient matrix are nonzero. In this note, numerical techniques for the solution of such linear systems are surveyed starting with a description of direct methods. When direct methods lead to excessive fill-in or when the coefficient matrix is not explicitly available, iterative methods enter the picture. These methods involve the coefficient matrix solely in the form of matrix-vector multiplications eliminating the problems of direct methods. After a summary of classical iterative methods based on relaxation of coordinates, the focus is on modern iterative methods making use of projection techniques. In particular, Krylov subspace methods are explained with an emphasis on their underlying structure rather than on their implementations details. Additional topics that are indispensable in the context of parallel computing such as reducing synchronization overhead and graph partitioning are also covered.