{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/30718"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/30718","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Parallel Sparse Linear Algebra for Homotopy Methods","abstract":"Globally convergent homotopy methods are used to solve difficult nonlinear systems of equations by tracking the zero curve of a homotopy map. Homotopy curve tracking involves solving a sequence of linear systems, which often vary greatly in difficulty. In this research, a popular iterative solution tool, GMRES(k), is adapted to deal with the sequence of such systems. The proposed adaptive strategy of GMRES(k) allows tuning of the restart parameter k based on the GMRES convergence rate for the given problem. Adaptive GMRES(k) is shown to be superior to several other iterative techniques on analog circuit simulation problems and on postbuckling structural analysis problems. Developing parallel techniques for robust but expensive sequential computations, such as globally convergent homotopy methods, is important. The design of these techniques encompasses the functionality of the iterative method (adaptive GMRES(k)) implemented sequentially and is based on the results of a parallel performance analysis of several implementations. An implementation of adaptive GMRES(k) with Householder reflections in its orthogonalization phase is developed. It is shown that the efficiency of linear system solution by the adaptive GMRES(k) algorithm depends on the change in problem difficulty when the problem is scaled. In contrast, a standard GMRES(k) implementation using Householder reflections maintains a constant efficiency with increase in problem size and number of processors, as concluded analytically and experimentally. The supporting numerical results are obtained on three distributed memory homogeneous parallel architectures: CRAY T3E, Intel Paragon, and IBM SP2.","abstract_html":"Globally convergent homotopy methods are used to solve difficult nonlinear systems of equations by tracking the zero curve of a homotopy map. Homotopy curve tracking involves solving a sequence of linear systems, which often vary greatly in difficulty. In this research, a popular iterative solution tool, GMRES(k), is adapted to deal with the sequence of such systems. The proposed adaptive strategy of GMRES(k) allows tuning of the restart parameter k based on the GMRES convergence rate for the given problem. Adaptive GMRES(k) is shown to be superior to several other iterative techniques on analog circuit simulation problems and on postbuckling structural analysis problems. Developing parallel techniques for robust but expensive sequential computations, such as globally convergent homotopy methods, is important. The design of these techniques encompasses the functionality of the iterative method (adaptive GMRES(k)) implemented sequentially and is based on the results of a parallel performance analysis of several implementations. An implementation of adaptive GMRES(k) with Householder reflections in its orthogonalization phase is developed. It is shown that the efficiency of linear system solution by the adaptive GMRES(k) algorithm depends on the change in problem difficulty when the problem is scaled. In contrast, a standard GMRES(k) implementation using Householder reflections maintains a constant efficiency with increase in problem size and number of processors, as concluded analytically and experimentally. The supporting numerical results are obtained on three distributed memory homogeneous parallel architectures: CRAY T3E, Intel Paragon, and IBM SP2.","abstract_has_math":false,"creators":["Driver, Maria Sosonkina"],"institution":"Virginia Tech","degree_name":"Ph. D.","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":"Computer Science","school":null,"contributors":[],"advisors":[],"committee_chairs":["Watson, Layne T."],"committee_members":["Jones, Mark T.","Heath, Lenwood S.","Allison, Donald C. S.","Beattie, Christopher A."],"year":1997,"date_issued":"1997-09-05","date_published":"1997-09-05","updated_at":"2026-07-22T22:20:43Z","subjects":["Krylov subspace methods","scientific computing","iterative methods"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-81897-131850"],"render_values":[{"text":"etd-81897-131850","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/30718","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Watson, Layne T."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Jones, Mark T.","Heath, Lenwood S.","Allison, Donald C. S.","Beattie, Christopher A."]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science"]},{"key":"dc:creator","label":"Author","values":["Driver, Maria Sosonkina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T20:22:34Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T20:22:34Z","1998-09-19"]},{"key":"dc:date.issued","label":"Date","values":["1997-09-05"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Krylov subspace methods","scientific computing","iterative methods"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-81897-131850"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/30718"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Globally convergent homotopy methods are used to solve difficult nonlinear systems of equations by tracking the zero curve of a homotopy map. Homotopy curve tracking involves solving a sequence of linear systems, which often vary greatly in difficulty. In this research, a popular iterative solution tool, GMRES(k), is adapted to deal with the sequence of such systems. The proposed adaptive strategy of GMRES(k) allows tuning of the restart parameter k based on the GMRES convergence rate for the given problem. Adaptive GMRES(k) is shown to be superior to several other iterative techniques on analog circuit simulation problems and on postbuckling structural analysis problems. Developing parallel techniques for robust but expensive sequential computations, such as globally convergent homotopy methods, is important. The design of these techniques encompasses the functionality of the iterative method (adaptive GMRES(k)) implemented sequentially and is based on the results of a parallel performance analysis of several implementations. An implementation of adaptive GMRES(k) with Householder reflections in its orthogonalization phase is developed. It is shown that the efficiency of linear system solution by the adaptive GMRES(k) algorithm depends on the change in problem difficulty when the problem is scaled. In contrast, a standard GMRES(k) implementation using Householder reflections maintains a constant efficiency with increase in problem size and number of processors, as concluded analytically and experimentally. The supporting numerical results are obtained on three distributed memory homogeneous parallel architectures: CRAY T3E, Intel Paragon, and IBM SP2."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Parallel Sparse Linear Algebra for Homotopy Methods"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Watson, Layne T."],"dc:contributor.committeemember":["Jones, Mark T.","Heath, Lenwood S.","Allison, Donald C. S.","Beattie, Christopher A."],"dc:contributor.department":["Computer Science"],"dc:creator":["Driver, Maria Sosonkina"],"dc:date.accessioned":["2014-03-14T20:22:34Z"],"dc:date.available":["2014-03-14T20:22:34Z","1998-09-19"],"dc:date.issued":["1997-09-05"],"dc:description.abstract":["Globally convergent homotopy methods are used to solve difficult nonlinear systems of equations by tracking the zero curve of a homotopy map. Homotopy curve tracking involves solving a sequence of linear systems, which often vary greatly in difficulty. In this research, a popular iterative solution tool, GMRES(k), is adapted to deal with the sequence of such systems. The proposed adaptive strategy of GMRES(k) allows tuning of the restart parameter k based on the GMRES convergence rate for the given problem. Adaptive GMRES(k) is shown to be superior to several other iterative techniques on analog circuit simulation problems and on postbuckling structural analysis problems. Developing parallel techniques for robust but expensive sequential computations, such as globally convergent homotopy methods, is important. The design of these techniques encompasses the functionality of the iterative method (adaptive GMRES(k)) implemented sequentially and is based on the results of a parallel performance analysis of several implementations. An implementation of adaptive GMRES(k) with Householder reflections in its orthogonalization phase is developed. It is shown that the efficiency of linear system solution by the adaptive GMRES(k) algorithm depends on the change in problem difficulty when the problem is scaled. In contrast, a standard GMRES(k) implementation using Householder reflections maintains a constant efficiency with increase in problem size and number of processors, as concluded analytically and experimentally. The supporting numerical results are obtained on three distributed memory homogeneous parallel architectures: CRAY T3E, Intel Paragon, and IBM SP2."],"dc:description.degree":["Ph. D."],"dc:identifier.other":["etd-81897-131850"],"dc:identifier.uri":["http://hdl.handle.net/10919/30718"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Krylov subspace methods","scientific computing","iterative methods"],"dc:title":["Parallel Sparse Linear Algebra for Homotopy Methods"],"dc:type":["Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Ph. D."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:20:43Z"}