Abstract

In modern large-scale supercomputing applications, Algebraic MultiGrid (AMG) is a leading choice for solving matrix equations. However, the high cost of communication relative to that of computation is a concern for the scalability of traditional implementations of AMG on emerging architectures. This paper introduces two new algebraic multilevel algorithms, Algebraic MultiGrid Domain Decomposition (AMG-DD) and Algebraic MultiGrid Range Decomposition (AMG-RD), that replace traditional AMG V-cycles with a fully overlapping domain decomposition approach. While the methods introduced here are similar in spirit to the geometric methods developed by Brandt and Diskin, Mitchell, and Bank and Holst, they differ primarily in that they are purely algebraic: AMG-RD and AMG-DD trade communication for computation by forming global composite ``grids" based only on the matrix, not the geometry. (As is the usual AMG convention, ``grids" here should only be taken in the algebraic sense, regardless of whether or not it corresponds to any geometry.) Another important distinguishing feature of AMG-RD and AMG-DD is their novel residual communication process that enables effective parallel computation on composite grids, avoiding the all-to-all communication costs of the geometric methods. The main purpose of this paper is to study the potential of these two algebraic methods as possible alternatives to existing AMG approaches for future parallel machines. To this end, this paper develops some theoretical properties of these methods and reports on serial numerical tests of their convergence properties over a spectrum of problem parameters.