## Files in this item

FilesDescriptionFormat

application/pdf

8815316.pdf (5MB)
(no description provided)PDF

## Description

 Title: Polynomial Preconditioning for Conjugate Gradient Methods Author(s): Ashby, Steven Flynn Doctoral Committee Chair(s): Saylor, Paul E., Department / Program: Computer Science Discipline: Computer Science Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics Computer Science Abstract: The solution of a linear system of equations, Ax = b, arises in many scientific applications. If A is large and sparse, an iterative method is required. When A is hermitian positive definite (hpd), the conjugate gradient method of Hestenes and Stiefel is popular. When A is hermitian indefinite (hid), the conjugate residual method may be used. If A is ill-conditioned, these methods may converge slowly, in which case a preconditioner is needed. In this thesis we examine the use of polynomial preconditioning in CG methods for both hermitian positive definite and indefinite matrices. Such preconditioners are easy to employ and well-suited to vector and/or parallel architectures.We first show that any CG method is characterized by three matrices: an hpd inner product matrix B, a preconditioning matrix C, and the hermitian matrix A. The resulting method, CG(B,C,A), minimizes the B-norm of the error over a Krylov subspace. We next exploit the versatility of polynomial preconditioners to design several new CG methods. To obtain an optimum preconditioner, we solve a constrained minimax approximation problem. The preconditioning polynomial, C($\lambda$), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix, $p\sb{m}$(A). An adaptive procedure for dynamically determining the optimum preconditioner from the CG iteration parameters is also discussed. Finally, in a variety of numerical experiments, conducted on a Cray X-MP/48, we demonstrate the effectiveness of polynomial preconditioning. Issue Date: 1988 Type: Text Description: 138 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988. URI: http://hdl.handle.net/2142/69586 Other Identifier(s): (UMI)AAI8815316 Date Available in IDEALS: 2014-12-15 Date Deposited: 1988
﻿