There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. Variants of the conjugate gradient algorithm along with different preconditioners are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned conjugate gradient method used in HOMPACK. In addition, a parallel version of Craig's method with incomplete LU factorization preconditioning is implemented on a shared memory parallel computer with various levels and degrees of parallelism (e.g., linear algebra, function and Jacobian matrix evaluation, etc.). An in-depth study is presented for each of these levels with respect to the speedup in execution time obtained with the parallelism, the time spent implementing the parallel code and the extra memory allocated by the parallel algorithm. / Master of Science

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 ρ_α(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρ_α(λ,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.