6.7 Fast Fourier Transform

In this section i will always denote

We begin by showing how to solve the two-dimensional Poisson's equation in a way requiring multiplication by the matrix of eigenvectors of T _N. A straightforward implementation of this matrix-matrix multiplication would cost O( N ³) = O( n ^3/2) operations, which is expensive. Then we show how this multiplication can be implemented using the FFT in only O( N ² log N) = O( n log n) operations, which is within a factor of logn n of optimal.

This solution is a discrete analogue of the Fourier series solution of the original differential equation (6.1) or (6.6). Later we will make this analogy more precise.

Let T _N = Z ? Z ^T be the eigendecomposition of T _N, as defined in Lemma 6.1. We begin with the formulation of the two-dimensional Poisson's equation in equation (6.11):

Substitute T _N = Z ?Z ^T and multiply by the Z ^T on the left and Z on the right to get

or

where V ? = Z ^TVZ and F ? = Z ^TFZ. The ( j, k)th entry of this last equation is

which can be solved for v ? _jk to get

This yields the first version of our algorithm.