Grid independent convergence using multilevel circulant preconditioning: Poisson's equation (Q2132425)

The iterative solution of the discrete Poisson equation in \(d\) dimensions is considered. The discrete domain is embedded into an extended domain and the resulting system of linear equations is solved using a fixed point iteration combined with a multilevel circulant preconditioner. The main aim of this work is to show that Strang's idea of using circulant preconditioning for Toeplitz systems can be successfully extended to the multilevel case for Poisson's equation. The numerical results show that the rate of convergence is independent of the grid's step sizes and of the number of spatial dimensions, despite the fact that the iteration operator is not bounded as the grid is refined. The embedding technique and the preconditioner is derived with inspiration from theory of boundary integral equations. The same theory is also used to explain the behaviour of the preconditioned iterative method.