Semicirculant Preconditioners for First-order Systems of PDEs

Dr. Kurt Otto

We consider solving time-dependent and time-independent systems of first-order PDEs in 2D using CG-like iterative methods. The systems are preconditioned using semicirculant preconditioners. Analytical formulas for the eigenvalues are derived for scalar model problems with correct boundary conditions and constant coefficients. It is proved that, under certain conditions on the grid, the spectrum of the time-independent problem asymptotically becomes two finite curve segments, which are independent of the number of gridpoints. Using the information on the spectra, the convergence of minimizing iterative methods like GMRES is analyzed. Based on semicirculant preconditioners we also construct a memory efficient direct solver for first-order systems of PDEs with proper boundary conditions and constant coefficients in one space direction. This solver could be used as a preconditioner for general problems. The convergence properties are empirically verified both for the model problems, and for more realistic problems, e.g., the Navier-Stokes equations for a channel flow.