HIGH-DIMENSIONAL HOMOTOPY CURVE TRACKING ON A SHARED-MEMORY MULTIPROCESSOR

Results are reported for a series of experiments involving numerical c urve tracking on a shared-memory parallel computer. Several algorithms exist for finding zeros or fixed points of nonlinear systems of equat ions that are globally convergent for almost all starting points, that is, with probability one. The essence of all such algorithms is the c onstruction of an appropriate homotopy map and then the tracking of so me smooth curve in the zero set of this homotopy map. HOMPACK is a mat hematical software package implementing globally, convergent homotopy algorithms with three different techniques for tracking a homotopy zer o curve, and has separate routines for dense and sparse Jacobian matri ces. The HOMPACK algorithms for sparse Jacobian matrices use a precond itioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix. a required linear algebra step for h omotopy curve tracking. A parallel version of HOMPACK is implemented o n a shared-memory parallel computer with various levels and degrees of parallelism (e.g.. linear algebra, function, and Jacobian matrix eval uation), and a detailed study is presented for each of these levels wi th respect to the speedup in execution time obtained with the parallel ism, the time spent implementing the parallel code, and the extra memo ry allocated by the parallel algorithm.