###
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.