``Transpose Free'' Alternating Direction Smoothers for Serial and Parallel Multigrid Methods

C. C. Douglas
Department of Mathematics
University of Kentucky
715 Patterson Office Tower
Lexington, KY 40506-0027, USA
S. Malhotra
Scientific Computing Associates
One Century Tower
265 Church Street
New Haven, CT 06510-7010, USA

M. H. Schultz
Department of Computer Science
Yale University
P.O. Box 20-8285
New Haven, CT 06520-8285, USA


Alternating Direction Implicit (ADI) methods are very good smoothers for multigrid. Like multigrid itself, ADI propagates information very quickly across a grid. On parallel processors, ADI is very inefficient due to the tridiagonal solves in each of the spatial directions. In one direction, the data typically resides in one processor. In the other directions, the data spans processor memories on distributed memory machines.

In this paper, a ``transpose free'' variant of ADI is considered which eliminates the drawback of ADI on parallel processors. In addition, it is quite useful on serial computers. We provide convergence rates for a model problem and numerical results for variable coefficient elliptic problems in two and three dimensions.

Key words: multigrid, alternating direction implicit methods, iterative methods, parallel computing, elliptic partial differential equations.

Contributed September 30, 1997.