The effect of ordering on the convergence of the conjugate gradient method for solving preconditioned shifted linear systems

Abstract

In this paper we study the effect of ordering in the preconditioning of shifted linear systems with matrices depending on a parameter, i.e., A ε χ ε = b ε with A ε = M + ε N symmetric positive definite. We construct two types of preconditioners, both of them dependent on ". We start from a factorized approximate inverse or from an incomplete Cholesky factorization of matrix M, respectively. Although the beneficial effect of the ordering on the convergence of iterative solvers with these preconditioners have been widely studied, there is no evidence of this effect when they are updated in shifted linear systems. To show this, some classical ordering algorithm such as Reverse Cuthill-McKee, Minimum Neighbouring and Multicoloring, are considered. Several numerical experiments are presented in order to show the reduction of computational cost and number of iteration of the preconditioned conjugate gradient method when some standard ordering schemes are applied.