On Fourier-Toeplitz Methods for Separable Elliptic Problems

Abstract

Some verv fast numerical methods have been developed in recent years for the solution of elliptic differential equations which allow for separation of variables.In this paper, a Fourier-Toeplitz method is developed as an alternative to the well-known methods of Hockney and Buneman.It is based on the fast Fourier transform and Toeplitz factorizations.The use of Toeplitz factorizations combined with the Sherman-Morrison formula is also systematically explored for linear systems of algebraic equations with band matrices of Toeplitz, or almost Toeplitz form.Finally, results of numerical experiments are described. Introduction.In recent years, some very fast and accurate methods have been developed for the direct solution of the sparse systems of linear algebraic equations which arise when elliptic problems are solved by finite difference or finite element methods.Several of these algorithms implement, in very efficient ways, the idea of separation of variables.The best known of these are due to Hockney [15], [16] and Buneman [5], [6].In this paper, we will present an alternative to Hockney's and Buneman's methods for the solution of elliptic problems with constant coefficients on rectangular regions and on infinite parallel strips.Our method, like Hockney's, is based on the use of the fast Fourier transform for one of the variables, but it uses an alternative way of solving the resulting systems of linear algebraic equations.These systems can be represented with band matrices of Toeplitz form or as low-rank perturbations of such matrices.The systems are solved by a combination of Toeplitz factorizations and applications of the Sherman-Morrison formula or its block version, the Woodbury formula (cf.Householder [17]).By using the Toeplitz structure, we are able to take greater advantage of the special structure of the matrices than when Gaussian elimination is used.This leads to a considerable saving in storage.We note that the odd-even reduction method has similar advantages but that it can be used only for a subset of the problems which we can handle.We include a discussion of the use of Toeplitz factorizations for more general band matrices.The method requires considerably much less storage than the Cholesky and Gauss elimination methods and it is also found to be quite competitive, in terms of arithmetic operations, in certain cases.For earlier work on Toeplitz methods, cf.Bakes [