Files in this item



application/pdf8815316.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


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
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
Description:138 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988.
Other Identifier(s):(UMI)AAI8815316
Date Available in IDEALS:2014-12-15
Date Deposited:1988

This item appears in the following Collection(s)

Item Statistics