SOLVING LARGE SYSTEMS OF LINEAR EQUATIONS ON PARALLEL COMPUTERS

Michele Benzi Department of Mathematics and Computer Science

Emory University

Atlanta, GA

ABSTRACT. Solving very large systems of linear equations is central to many numerical simulations, and is easily the most time-consuming part of the computation. The most common source of large matrix problems remains the discretization (and linearization) of partial differential equations of elliptic and parabolic type. Other areas where large and sparse linear systems arise frequently include the design and computer analysis of circuits, power system networks, chemical engineering processes, macroeconomics models, queueing systems, and others.

One common approach is to design specialized algorithms that are optimal (or nearly so) for a narrow class of problems. Another approach is to developed general-purpose, purely algebraic methods (and software) that achieve reasonable efficiency on a wide range of problems. In this talk I will limit myself to the second approach.

Many sophisticated techniques have been developed in the last fifty years using tools from linear algebra, graph theory, and approximation theory. Currently, the search for efficient solution algorithms is being driven by the need to solve huge systems (with millions and even billions of unknowns!) on massively parallel computers. In this talk I will review some recently proposed methods for solving large-scale sparse linear systems on parallel machines. The emphasis will be on Krylov subspace methods and algebraic preconditioners based on sparse approximate inverses.