Numerical Analysis of Some Preconditioners and Associated Error Estimators for Solving Linear Systems

Abstract

Convergence of iterative algorithms in solving large linear systems is largely affected by the condition number of the matrix. Preconditioners reduce the condition number of the system matrix, thereby letting the linear system converge in fewer iterations. First, we perform a theoretical study on the expected iterations saved due to a general purpose preconditioner as a function of matrix size, tolerance, condition number and the linear solver (CG or GM-RES). A metric is suggested for evaluating gains with respect to the iterations required in preconditioned and non-preconditioned systems, and experimental analysis of the same will be presented. These experiments explore split Jacobi and Incomplete Cholesky preconditioners for symmetric positive definite (SPD) matrices. The second part of this work focuses on the role of error estimators in realizing the gains of a preconditioner. We apply error estimators for non-preconditioned and preconditioned solvers and compare their significance in both cases.