Return to search

Parallel homotopy curve tracking on a hypercube

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. / Ph. D.

Identiferoai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/39354
Date16 September 2005
CreatorsChakraborty, Amal
ContributorsComputer Science and Applications, Watson, Layne T., Ribbens, Calvin J., Beattie, Christopher A., Abrams, Marc, Allison, Donald C. S.
PublisherVirginia Tech
Source SetsVirginia Tech Theses and Dissertation
LanguageEnglish
Detected LanguageEnglish
TypeDissertation, Text
Formatv, 128 leaves, BTD, application/pdf, application/pdf
RightsIn Copyright, http://rightsstatements.org/vocab/InC/1.0/
RelationOCLC# 22252084, LD5655.V856_1990.C532.pdf

Page generated in 0.0022 seconds