AMG works by using the algebraic properties of the operator matrix to select some of the equations as "coarse-grid" equations. As in geometric multigrid, the error is smoothed on the full (fine-grid) problem by relaxation, the residual is then transferred to the coarse equations, where the error can be computed at greatly reduced cost. The error is then transferred back to the fine grid, where it is used to correct the original approximation. Recursive application of this technique leads to a multigrid algorithm.
AMG thus consists of two distinct phases. First, a "setup" phase occurs, during which the selection of coarse- and fine-grid equations is made. The intergrid transfer operators are constructed in this phase. Next, the "solution" phase occurs, in which the multigrid cycling takes place.
Many of the problems of current interest are extremely large, with systems having millions of equations and unknowns. Efficient solution of such problems, therefore, will demand the application of parallel procesing technology. Multigrid lends itself well to parallelization, and as a result, the solution phase is easily parallelized, using the same techniques as are used in geometric multigrid. However, the fundamental algorithms of the setup phase are inherently serial in nature, and efforts to increase the efficiency through parallelization have not been terribly successful.
This paper describes new algorithms for parallel implementation of the setup phase. Much of the setup phase is essentially a graph coloring problem, and the algorithms are thus closely related to the question of parallel implementation of graph coloring algorithms. Discussion of the algorithms centers around the mapping of the original equations to the processors, the simultaneous coloring of the individual graphs within processors, and the need for communication to resolve conflicting assignments.