``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

                                   Abstract

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.