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.