Alternating direction methods on multiprocessors. Research report

This document proposes a few implementation of the Alternating Direction Method for solving parabolic partial differential equations on multiprocessors. A careful complexity analysis of these implementations shows that, contrary to what is generally believed, the method can be made highly efficient on parallel architectures by using pipelining and variations of the classical Gaussian elimination algorithm for solving tridiagonal systems. In an earlier work the authors showed that they could obtain linear speedups for moderate numbers of processors in a ring architecture. This paper discusses extensions to a large number of processors in a 2-D grid architecture and a hypercube.