Right Product Polynomial Preconditioned GMRES

GMRES is one of the most popular algorithms for solving large nonsymmetrical linear systems. Unfortunately, the computational cost of full GMRES usually becomes unacceptable as the iteration number increases. To overcome the difficulty, restarting scheme or hybrid scheme of GMRES can be employed. Recently, the complementary behavior of restarted GMRES has attracted a wide interest. In particular, based on the study of complementary behavior, a product hybrid GMRES algorithm has been proposed, which improves the efficiency of hybrid scheme significantly.The product hybrid GMRES algorithm can be taken as a left preconditioning technique for solving linear systems. To implement the algorithm, a couple of GMRES polynomials are constructed, and then the product of the polynomials are used repeatedly via a Richardson iteration. However, if the restarting frequency is not small, the GMRES polynomials may undergo a great instability. In consequence, the Richardson iteration may diverge. In the present paper, another possibility is considered for using the product polynomial as a preconditioner. It is referred to as Right Product Polynomial Preconditioning. The preconditioned algorithm has two loops: in the inner loop the product polynomial is used repeatedly via a Richardson iteration; in the outer loop the GMRES iteration is used. Since the residual will not diverge with respect to the Euclidean norm, the new algorithm is safer than the product hybrid GMRES algorithm.Based on the complementary behavior of restarted GMRES, it is shown that under some assumptions, the preconditioned coefficient matrix can have a much lower condition number than that of the original matrix. Consequently, convergence of the residual can be significantly improved. Finally, numerical experiments are conducted to show the efficiency of the new algorithm.