Parallel algorithms for the iterative solution of large sparse linear systems

Abstract

In this thesis we are concerned with iterative parallel algorithms for solving finite difference equations arising from boundary value problems. We propose various new methods based on approximate inverses. The Jacobi iterative method for the solution of linear equations is highly parallel. Its slow convergence rate, however, has initiated the study of a variety of acceleration techniques. We introduce the “Diagonal-Block” and the "Least Squares" techniques for calculating approximate inverses which lead naturally to generalized Jacobi methods that are well suited to parallel processing. In addition, the calculations required to establish the iterative process can be done in parallel. A convergence theorem for a one-dimensional model problem is given. Gauss-Seidel versions of these methods are also considered. These versions converge faster but often at the cost of decreased parallelism. Preconditioning has been successfully used in conjunction with the conjugate gradient method. Many such techniques use an approximation M to the matrix A of the linear system under consideration and solve a system of the form M z = d at each iteration. If, however, an approximate inverse M[superscript -1] is used, the solution z = M[superscript -1] d only involves a matrix-vector multiplication v/hich is well suited to parallel computation. We examine the Diagonal-Block and Least-Squares techniques for preconditioning the conjugate gradient method. Numerical results are presented. The proposed Jacobi like and Gauss-Seidel like methods are compared with parallel Gauss-Seidel methods in a class of parallel algorithms proposed by Evans and Barlow (1982). The preconditioned conjugate gradient methods are compared with the plain conjugate gradient method. In all cases the speed of convergence increased substantially, but often at the expense of increased computational work. In some cases it was necessary to assume the number of processors to be on the order of N ( the number of unknowns ) in order to gain an advantage from parallel processing.