Alternating Direction Methods on Multiprocessors

Abstract

We propose several implementations of the Alternating Direction Method (ADM) for solving parabolic partial differential equations on multiprocessors. A complexity analysis of these implementations shows that 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. Previously, we showed that we could obtain linear speedups for moderate numbers of processors in a ring architecture. In this paper we discuss extensions to a large number of processors in a 2-D grid architecture and a hypercube.