ANALYSIS OF SEMI-TOEPLITZ PRECONDITIONERS FOR FIRST-ORDER PDES

A semi-Toeplitz preconditioner for nonsymmetric, nondiagonally dominan t systems of equations is studied. The preconditioner solve is based o n a fast modified sine transform. As a model problem we study a system of equations arising from an implicit time discretization of a scalar hyperbolic partial differential equation (PDE). Analytical formulas f or the eigenvalues and the eigenvectors of the preconditioned system a re derived. The convergence of a minimal residual iteration is shown t o depend only on the spatial grid ratio and not on the number of unkno wns.