{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/39354"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/39354","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Parallel homotopy curve tracking on a hypercube","abstract":"Probability-one homotopy methods are a class of methods for solving non-linear systems of equations that are globally convergent with probability one from an arbitrary starting point. The essence of these algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy zero curve requires calculating the unit tangent vector at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map ρ<sub>α</sub>(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρ<sub>α</sub>(λ,x). Hence, tracking a zero curve of a homotopy map involves evaluating the Jacobian matrix and finding the one-dimensional kernel of the n x (n + 1) Jacobian matrix with rank n. Since accuracy is important, an orthogonal factorization of the Jacobian matrix is computed. The QR and LQ factorizations are considered here. Computational results are presented showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube, in the context of parallel homotopy algorithms for problems with small, dense Jacobian matrices. This study also examines the effect of different component complexity distributions and the size of the Jacobian matrix on the different assignments of components to the processors, and determines in what context one assignment would perform better than others.","abstract_html":"Probability-one homotopy methods are a class of methods for solving non-linear systems of equations that are globally convergent with probability one from an arbitrary starting point. The essence of these algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy zero curve requires calculating the unit tangent vector at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map ρ&lt;sub&gt;α&lt;/sub&gt;(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρ&lt;sub&gt;α&lt;/sub&gt;(λ,x). Hence, tracking a zero curve of a homotopy map involves evaluating the Jacobian matrix and finding the one-dimensional kernel of the n x (n + 1) Jacobian matrix with rank n. Since accuracy is important, an orthogonal factorization of the Jacobian matrix is computed. The QR and LQ factorizations are considered here. Computational results are presented showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube, in the context of parallel homotopy algorithms for problems with small, dense Jacobian matrices. This study also examines the effect of different component complexity distributions and the size of the Jacobian matrix on the different assignments of components to the processors, and determines in what context one assignment would perform better than others.","abstract_has_math":false,"creators":["Chakraborty, Amal"],"institution":"Virginia Tech","degree_name":"Ph. D.","degree_level":"doctoral","degree_discipline":"Computer Science and Applications","degree_department":"Computer Science and Applications","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Watson, Layne T.","Ribbens, Calvin J.","Beattie, Christopher A.","Abrams, Marc","Allison, Donald C. S."],"year":1990,"date_issued":"1990-05-06","date_published":"1990-05-06","updated_at":"2026-07-22T22:19:35Z","subjects":[],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-09162005-115011"],"render_values":[{"text":"etd-09162005-115011","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/39354","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Watson, Layne T.","Ribbens, Calvin J.","Beattie, Christopher A.","Abrams, Marc","Allison, Donald C. S."]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science and Applications"]},{"key":"dc:creator","label":"Author","values":["Chakraborty, Amal"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T21:18:54Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T21:18:54Z","2005-09-16"]},{"key":"dc:date.issued","label":"Date","values":["1990-05-06"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Applications"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"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-09162005-115011"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/39354"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Probability-one homotopy methods are a class of methods for solving non-linear systems of equations that are globally convergent with probability one from an arbitrary starting point. The essence of these algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy zero curve requires calculating the unit tangent vector at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map ρ<sub>α</sub>(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρ<sub>α</sub>(λ,x). Hence, tracking a zero curve of a homotopy map involves evaluating the Jacobian matrix and finding the one-dimensional kernel of the n x (n + 1) Jacobian matrix with rank n. Since accuracy is important, an orthogonal factorization of the Jacobian matrix is computed. The QR and LQ factorizations are considered here. Computational results are presented showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube, in the context of parallel homotopy algorithms for problems with small, dense Jacobian matrices. This study also examines the effect of different component complexity distributions and the size of the Jacobian matrix on the different assignments of components to the processors, and determines in what context one assignment would perform better than others."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["BTD"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Parallel homotopy curve tracking on a hypercube"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Watson, Layne T.","Ribbens, Calvin J.","Beattie, Christopher A.","Abrams, Marc","Allison, Donald C. S."],"dc:contributor.department":["Computer Science and Applications"],"dc:creator":["Chakraborty, Amal"],"dc:date.accessioned":["2014-03-14T21:18:54Z"],"dc:date.available":["2014-03-14T21:18:54Z","2005-09-16"],"dc:date.issued":["1990-05-06"],"dc:description.abstract":["Probability-one homotopy methods are a class of methods for solving non-linear systems of equations that are globally convergent with probability one from an arbitrary starting point. The essence of these algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy zero curve requires calculating the unit tangent vector at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map ρ<sub>α</sub>(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρ<sub>α</sub>(λ,x). Hence, tracking a zero curve of a homotopy map involves evaluating the Jacobian matrix and finding the one-dimensional kernel of the n x (n + 1) Jacobian matrix with rank n. Since accuracy is important, an orthogonal factorization of the Jacobian matrix is computed. The QR and LQ factorizations are considered here. Computational results are presented showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube, in the context of parallel homotopy algorithms for problems with small, dense Jacobian matrices. This study also examines the effect of different component complexity distributions and the size of the Jacobian matrix on the different assignments of components to the processors, and determines in what context one assignment would perform better than others."],"dc:description.degree":["Ph. D."],"dc:format.medium":["BTD"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["etd-09162005-115011"],"dc:identifier.uri":["http://hdl.handle.net/10919/39354"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Parallel homotopy curve tracking on a hypercube"],"dc:type":["Dissertation"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Computer Science and Applications"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Ph. D."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:35Z"}