The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation

Summary Discretization of the Poisson equation on a rectangle by finite differences using the standard five-point stencil yields a linear system of algebraic equations, which can be solved rapidly by the cyclic reduction method. In this method a sequence of tridiagonal linear systems is solved. The matrices of these systems commute, and we investigate numerical aspects of their ordering. In particular, we present two new ordering schemes that avoid overflow and loss of accuracy due to underflow. These ordering schemes improve the numerical performance of the subroutine HWSCRT of FISHPAK. Our orderings are also applicable to the solution of Helmholtz's equation by cyclic reduction, and to related numerical schemes, such as FACR methods.Dedicated to the memory of Peter HenriciResearch supported in part by the National Science Foundation under Grant DMS-870416