Direct Solution of Elliptic Equations by Block Cyclic Reduction and Factorization

Abstract

Poisson's and Helmholtz's equations are perhaps the most frequently occurring and important types of partial differential equations encountered in the atmospheric sciences. This paper presents a very fast, accurate technique for finding the numerical solution known as cyclic reduction and factoralization. This method has not heretofore been brought to the attention of the meteorological community at large. This direct method essentially reduces the solution of a separable two-dimensional elliptic equation on an N?M grid to N log2N tri-diagonal systems of order M which are solved by Gaussian elimination. In its simplest form, as described here, the cyclic reduction procedure can be applied if N is 2n?1, 2n2n=1, depending on boundary conditions. However, extensions of the method have been developed which have removed this restrictive limitation. The method is also easily generalized to higher dimensional problems. The mathematical development of the cyclic reduction method is presented here in complete detail, along with the modifications necessary to make it computationally stable. The results of two numerical experiments comparing optimized SOR versus the direct method for the solution of Poisson=s equation are presented. For Dirichlet boundary conditions the direct method is up to 50 times faster than successive over-relaxation (SOR) for N=M=128. For Neumann boundary conditions, the direct method has even a greater advantage over SOR. The margin of superiority increases as the size of the array increases.