Yale Center for Parallel Supercomputing

Department of Computer Science

Yale University

New Haven, CT 06520-8285 USA

Multigrid methods are often used for the solution of systems of equations arising from the discretization of elliptic partial differential equations. Such problems are often the compute intensive kernels for many numerical problems arising in science and engineering. The solution of three--dimensional problems, which lead to very large systems of equations, is particulary well suited to solution by multigrid methods.

The large size of the problems to be solved has led to the increasing use of parallel computers, for example clusters or LANs of workstations. However, in practice, most workstations are connected by relatively slow connections such as ethernet.

In this dissertation, we investigate some of the issues involved in the solution of elliptic problems using multigrid methods. We shall focus on the solution of these problems on clusters of workstations. We shall define a class of algorithms to accelerate the multigrid smoother on such clusters. These methods subsume the latency inherent in the communication by using redundant computation to combine a large number of small messages.

Alternating direction methods, which are often used as smoothers in the serial case, suffer from a high parallel overhead because of the need to transpose data in each smoothing iteration. We suggest modifications of these methods which are parallelizable and maintain the rate of convergence. These modifications are also applicable to alternating direction line SOR iterative methods.

Lastly, we shall deal with the theoretical issues involved in transferring the error in multigrid algorithms from one grid to another, possibly unrelated, grid. We derive sharp upper and lower bounds on the condition number of this procedure.

Dedication

I have measured out my life with coffee spoons.

-- T. S. Elliot

I would like to thank a number of people who made this dissertation possible. Foremost, I would like to thank my parents without whose support this would never have been possible. I would like to thank Martin Schultz for giving me the opportunity to pursue my own ideas and offering help whenever called upon. I would also like to thank Craig Douglas for providing a continual stream of ideas and suggestions, not to mention \LaTeX \mbox{} style pointers. I would also like to thank all the wonderful people at the Computer Science Department, especiallyLinda Bourne, Cathy Esposito, Judy Smith and last but not the least Prof. Zuck for making the stay in the department a pleasant one. I would also like to thank Prof. Rokhlin for allowing me to use the Sparc10 workstations used to collect a large part of the experimental data in this thesis.

I would like to thanks everyone who made my life in New Haven interesting and enjoyable: Aage Bendiksen, Akash Deep, Anna Primrose, Ashish Deshpande, Bhaskar Ghosh, Gary Sandling, Greg Candy, Pedro Marun, Rajiv Mirani, Marc Jourdenais, Satish Pai, Scott Berryman, Sharad Kapur, Sheng Liang, Masha and Boris Khesin and all the wonderful folks at 276 Prospect Street.

This work was supported in part by the Office of Naval Research under grant number ONR N00014--J--91--1576.

Contributed December 9, 1996.