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

ABSTRACT

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(&lgr;,&khgr;) is in the kernel of the Jacobian matrix D&rgr;a(&lgr;,&khgr;). Hence, tracking the zero curve of a homotopy map involves finding the kernel of the Jacobian matrix D&rgr;a(&lgr;,&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.

REFERENCES

• 1: Allgower, E. and Georg, K. 1980. Simplicial and continuation methods for approximating fixed points, SIAM Rev., 22, 28-85.
• 2: D. C. S. Allison , A. Chakraborty , L. T. Watson, Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1463-1472, January 1989, Pasadena, California, United States [doi>10.1145/63047.63103]
• 3: Billups, S. C. 1985. An augmented Jacobian matrix algorithm for tracking homotopy zero curves, M.S. Thesis, Dept. of Computer Sci., VPI & SU, Blacksburg, VA.
• 4: Chamberlain, R.M., and Powell, M.J.D. 1986. QI~ factorization for linear least squares problems on the Hypercube, Tech. Rep. CCS 86/10, Dept. of Science and Technology, Christian Michelson Institute, Bergen, Norway.
• 5: Chu, E., and George, A. 1988. QR factorizations of a dense matrix on a Hypercube multiprocessor, Tech. Rep. ORNL/TM-10691, Mathematical Sciences Section, Oak Ridge National Laboratory, Oak Ridge, TN.
• 6: S. C. Eisenstat , M. T. Heath , C. S. Henkel , C. H. Romine, Modified cyclic algorithms for solving triangular systems on distributed-memory multiprocessors, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.589-600, May 1988 [doi>10.1137/0909038]
• 7: Michael T. Heath , Charles H. Romine, Parallel solution of triangular systems on distributed-memory multiprocessors, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.558-588, May 1988 [doi>10.1137/0909037]
• 8: Guangye Li , Thomas F. Coleman, A New Method for Solving Triangular Systems on Distributed Memory Message-Passing Multiprocessors, Cornell University, Ithaca, NY, 1987
• 9: Alexander P. Morgan , Layne T. Watson, Globally Convergent Parallel Algorithm for Zeros of Polynomial Systems, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1986
• 10: Wolfgang Pelz , Layne T. Watson, Message Length Effects for Solving Polynomial Systems on a Hypercube, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1986
• 11: Pothen, A. Somesh, J., and Vemulapati, U. 1987. Orthogonal factorizations on a distributed multiprocessor, In Proceedings - Hypercube Multiprocessors 1987, M. T. Heath, ed., SIAM, Philadelphia, PA, 587-596.
• 12: A. Pothen , P. Raghavan, Distributed orthogonal factorization, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1610-1620, January 1989, Pasadena, California, United States [doi>10.1145/63047.63122]
• 13: Werner C. Rheinboldt , John V. Burkardt, Algorithm 596: a program for a locally parameterized, ACM Transactions on Mathematical Software (TOMS), v.9 n.2, p.236-241, June 1983 [doi>10.1145/357456.357461]
• 14: Wang, C. Y. 1988. Buoyant rotating disc, manuscript and private communication.
• 15: Watson, L. T. 1979. A globally convergent algorithm for computing fixed points of C2 maps, Appl. Math. Comput., 5, 297-311.
• 16: Layne T Watson, Numerical linear algebra aspects of globally convergent homotopy methods, SIAM Review, v.28 n.4, p.529-545, Dec. 1986 [doi>10.1137/1028157]
• 17: Layne T. Watson , Stephen C. Billups , Alexander P. Morgan, ALGORITHM 652: HOMPACK: a suite of codes for globally convergent homotopy algorithms, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.281-310, Sept. 1987 [doi>10.1145/29380.214343]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms