{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69586"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69586","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Polynomial Preconditioning for Conjugate Gradient Methods","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ashby, Steven Flynn"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Saylor, Paul E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:26:01Z","date_published":"2014-12-15T19:26:01Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Mathematics","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8815316"],"render_values":[{"text":"(UMI)AAI8815316","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69586","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Saylor, Paul E."]},{"key":"dc:creator","label":"Author","values":["Ashby, Steven Flynn"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:26:01Z","10000-01-01","1988"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69586","(UMI)AAI8815316"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-15T19:26:01Z (GMT). No. of bitstreams: 1 8815316.pdf: 5464110 bytes, checksum: 4a624791c7540347675b5ba5d5bd0f7a (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69752 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","138 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Polynomial Preconditioning for Conjugate Gradient Methods"]}]}],"canonical_facts":{"dc:contributor":["Saylor, Paul E."],"dc:creator":["Ashby, Steven Flynn"],"dc:date":["2014-12-15T19:26:01Z","10000-01-01","1988"],"dc:description":["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.","Made available in DSpace on 2014-12-15T19:26:01Z (GMT). No. of bitstreams: 1 8815316.pdf: 5464110 bytes, checksum: 4a624791c7540347675b5ba5d5bd0f7a (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69752 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","138 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69586","(UMI)AAI8815316"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Polynomial Preconditioning for Conjugate Gradient Methods"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:01Z"}