A Review of Numerous Parallel Multigrid Methods

Craig C. Douglas
IBM T. J. Watson Research Center
Yorktown Heights, NY, USA and
Computer Science Department
Yale University
New Haven, CT, USA


Multigrid methods originated earlier this century, in the personnel computing era. Someone who needed to compute an approximation to the solution of a partial differential equation during that era would fill a room with people. After using very simple mechanical calculators to compute parts of the approximation, these people would pass their parts to the other people in the room who needed them. Except for the very different time scales and approximate solution accuracy, this process is similar to computing on today's distributed memory parallel computers.

Parallel multilevel methods are shown to be the natural precursors to standard multilevel methods based on the personnel computing era of earlier this century. They are also the natural successors to standard multilevel methods in the age of computers. What makes six parallel multilevel methods practical and impractical is discussed in the context of the three algorithms that encapsulate them.

Contributed December 5, 1995.