Modal preconditioning of Galerkin spectral methods: Dual bookkeeping for the Delves–Freeman iteration

Fourier–Galerkin discretizations of PDEs can often be preconditioned by a matrix that is the union of a dense M×MM×M matrix plus a large matrix that is either diagonal or banded with small bandwidth. This was suggested forty years ago by L.M. Delves. For our two-dimensional example, the preconditioned iteration converges geometrically fast to machine precision in less than ten iterations. If the residual of the partial differential equation is evaluated by Fast Fourier Transform (FFT), the cost scales almost linearly in the number of unknowns. On a 6144×61446144×6144 grid, the computation needed less than an hour in Matlab on a laptop. The dense block requires a total degree ordering; the FFT evaluation of the residual requires speedometer ordering of the Fourier coefficient matrix. We show that this dual bookkeeping is essential but not difficult.