Dissertation/Thesis Abstract

Performance evaluation of inexact GMRES
by Winkles, Nathan E., Ph.D., The University of Alabama, 2011, 122; 3478682
Abstract (Summary)

Iterative methods are aimed at sparse linear systems that arise in many applications (e.g., PDEs, biology, computer science, technology, engineering, etc). These applications give rise to matrices that differ in terms of structure and characteristics, and these ultimately impact the solvers. The Generalized Minimal Residual Method (GMRES) is a widely used solver due to its robustness. The inexact GMRES algorithm is a variant of the GMRES algorithm where matrix-vector products are performed inexactly, either out of necessity or deliberately, in view of trading accuracy for speed. Recent studies have shown that relaxing matrix-vector products this way can be justified theoretically and experimentally. Research so far has focused on decreasing the workload per iteration without significantly affecting the accuracy. But relaxing the accuracy per iteration is susceptible to increase the number of iterations, thereby increasing the overall runtime, which could potentially end up greater than that of the exact GMRES if there were not enough savings in the matrix-vector products. In this dissertation, we assess the benefit of the inexact approach in terms of actual CPU time derived from realistic problems, and we provide cases that shed instructive insights into results affected by the buildup of the inexactness. Such information is of vital importance to practitioners who need to decide if switching their vested work-flow to the inexact approach is worth the effort and the risk that might come with it. Our assessment is drawn from extensive numerical experiments on the Alabama Supercomputing Facility that gauge the effectiveness of the inexact scheme and its suitability to certain problems depending on how much inexactness is allowed in the matrix-vector products. We present many different applications throughout this dissertation and we show different structures and characteristics of matrices which are useful in the sense that linear system solvers sometimes do not converge to the correct solution if the matrices do not have specific properties. We apply some incomplete preconditioning techniques to our inexact scheme and we show that we could accelerate the convergence or even recover convergence that was lost from the restarted GMRES.

Indexing (document details)
Advisor: Sidje, Roger B.
Commitee: Hadji, Layachi, Halpern, David, Wu, Zhijian, Young, David
School: The University of Alabama
Department: Mathematics
School Location: United States -- Alabama
Source: DAI-B 73/02, Dissertation Abstracts International
Subjects: Applied Mathematics, Mathematics
Keywords: Gmres, Inexact krylov methods, Matrix-vector products, Preconditioned gmres
Publication Number: 3478682
ISBN: 9781124965055