TABLE OF CONTENTS This chapter is concerned with yet another approach to the solution of the linear equations that occur when the Poisson equation is discretized by finite differences. This approach is an alternative to the direct methods of Chapter 11 and to the iterative schemes of Chapters 12 14. We intend to present two techniques for the very fast approximation of ? 2 u = f, one in a rectangle and the other in a disc. These techniques share two features. Firstly, they originate in numerical solution of the Poisson equation hence their sobriquet, fast Poisson solvers . Secondly, the secret of their efficacy rests in a clever use of the fast Fourier transform (FFT).
In the present section we assume that the Poisson equation (8.13) with Dirichlet boundary conditions (8.14) is solved in a rectangle with either the five-point formula (8.15) or the nine-point formula (8.28) (or, for that matter, the modified nine-point formula (8.32) the matrix of the linear system does not depend on whether the nine-point method has been modified). In either case we assume that the linear equations have been assembled in natural ordering.
Suppose that the grid is m 1 m 2. The linear system A x = b canbewritteninthe block-TST form (recall from Section 12.2 that TST stands for Toeplitz, symmetric and tridiagonal )
where x ? and b ? correspond to the variables and to the portion of b
