Sparse Iterative Algorithm Software for Large-Scale MIMD Machines: An Initial Discussion and Implementation

John N. Shadid, Ray S. Tuminaro

Sandia National Laboratories
Albuquerque, New Mexico 87185

Abstract
The parallelization of sophisticated applications has dramatically increased in recent years. As machine capabilities rise, greater emphasis on modeling complex phenomena can be expected. Many of these applications involve the numerical approximation of systems of partial differential equations (PDEs) which require the solution of large sparse matrix equations. Therefore, we consider parallel iterative solvers for large sparse nonsymmetric systems, and issues related to parallel sparse matrix software. We describe a collection of parallel iterative solvers which use a distributed sparse matrix format developed to facilitate the interface between specific applications and a variety of iterative techniques. This format is a generalization of sparse matrix formats found on sequential machines, and is used to develop Krylov subspace techniques as well as multigrid methods. These methods have been used to solve a number of linear and nonlinear PDE problems on a 1024 processor NCUBE 2 hypercube. Over 1 Gigaflop sustained computation rates are achieved with many of these solvers demonstrating that high performance can be attained even when using sparse matrix data structures.