Parallel unit tangent vector computation for homotopy curve tracking on a hypercube

摘要

Probability-one homotopy methods are a class of methods for solving nonlinear systems of equations that are globally convergent from an arbitrary starting point. The essence of all such 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 curve involves finding the unit tangent vectors 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 &rgr;a(λ,&khgr;) is in the kernel of the Jacobian matrix D&rgr;a(λ,&khgr;). Hence, tracking the zero curve of a homotopy map involves finding the kernel of the Jacobian matrix D&rgr;a(λ,&khgr;). The Jacobian matrix D&rgr;a is a n × (n+1) matrix with full rank. Since the accuracy of the unit tangent vector is very important, an orthogonal factorization instead of an LU factorization of the Jacobian matrix is computed. Two related orthogonal factorizations, namely QR and LQ factorization, are considered here. This paper presents computational results showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube. Since the purpose of this study is to find ways to parallelize homotopy algorithms, it is assumed that the matrices have a special structure such as that of the Jacobian matrix of a homotopy map. In particular, we are interested in relatively small and dense Jacobians.