A framework for polynomial preconditioners based on fast transforms II: PDE applications

The solution of systems of equations arising from systems of time-dependent partial differential equations (PDEs) is considered. Primarily, first-order PDEs are studied, but second-order derivatives are also accounted for. The discretization is performed using a general finite difference stencil in space and an implicit method in time. The systems of equations are solved by a preconditioned Krylov subspace method. The preconditioners exploit optimal and superoptimal approximations by low-degree polynomials in a normal basis matrix, associated with a fast trigonometric transform. Numerical experiments for high-order accurate discretizations are presented. The results show that preconditioners based on fast transforms yield efficient solution algorithms, even for large quotients between the time and space steps. Utilizing a spatial grid ratio less than one, the arithmetic work per grid point is bounded by a constant as the number of grid points increases. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.