Polynomial preconditioning with the minimum residual polynomial.

Abstract

Krylov subspace methods are often used to solve large, sparse systems of linear equations Ax=b. Preconditioning can help accelerate the Krylov iteration and reduce costs for solving the problem. We study a polynomial preconditioner p(A) based upon the minimum residual polynomial from GMRES. The polynomial can improve the eigenvalue distribution of A for better convergence. We demonstrate a power basis method of generating the polynomial and how it can be unstable. Then we develop a new method to generate the polynomial which uses harmonic Ritzvalues as roots. We discuss sources of roundoff error and give a procedure to make the polynomial stable through adding extra copies of roots. Furthermore, we implement the polynomial into the software Trilinos. We use this implementation to test the polynomial composed with other preconditioners and give considerations for parallel computing.