Circulant preconditioners for second order hyperbolic equations

Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations in two dimensions are considered. We propose and analyze the use of circulant preconditioners for the solution of linear systems via preconditioned iterative methods such as the conjugate gradient method. Our motivation is to exploit the fast inversion of circulant systems with the Fast Fourier Transform (FFT). For second-order hyperbolic equations with initial and Dirichlet boundary conditions, we prove that the condition number of the preconditioned system is of O(α) or O(m), where α is the quotient between the time and space steps and m is the number of interior gridpoints in each direction. The results are extended to parabolic equations. Numerical experiments also indicate that the preconditioned systems exhibit favorable clustering of eigenvalues that leads to a fast convergence rate.