The Efficient Parallel Iterative Solution of Large Sparse Linear Systems

The development of efficient, general-purpose software for the iterative solution of sparse linear systems on parallel MIMD computers depends on recent results from a wide variety of research areas. Parallel graph heuristics, convergence analysis, and basic linear algebra implementation issues must all be considered.In this paper, we discuss how we have incorporated these results into a general-purpose iterative solver. We present two recently developed asynchronous graph coloring heuristics. Several graph reduction heuristics are described that are used in our implementation to improve individual processor performance. The effect of these various graph reduction schemes on the solution of sparse triangular systems is categorized. Finally, we report on the performance of this solver on two large-scale applications: a piezoelectric crystal finite-element modeling problem, and a nonlinear optimization problem to determine the minimum energy configuration of a three-dimensional superconductor model.