×

High-dimensional homotopy curve tracking on a shared-memory multiprocessor. (English) Zbl 0749.65032

Authors’ summary: Results are reported for a series of experiments involving numerical curve tracking on a shared-memory parallel computer. Several algorithms exist for finding zeros of fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, that is, with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then the tracking of 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. A parallel version of HOMPACK is implemented on a shared- memory parallel computer with various levels and degrees of parallelism (e.g., linear algebra, function, and Jacobian matrix evaluation), and a detailed 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.

MSC:

65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65Y05 Parallel numerical computation

Software:

HOMPACK; PITCON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower, E.L., and Georg, K. 1990. Introduction to Numerical Continuation Methods. Springer-Verlag, Berlin. · Zbl 0717.65030
[2] Allison, D.C.S., Chakraborty, A., and Watson, L.T. 1988. Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube. In Proc., Third Conf. on Hypercube Concurrent Computers and Applications (Pasadena, Calif.), ACM, pp. 1463-1472.
[3] Billups, S.C. 1985. An augmented Jacobian matrix algorithm for tracking homotopy zero curves. M.S. thesis, Dept. of Comp. Sci., Va. Polytechnic Institute & State Univ., Blacksburg, Va.
[4] Chakraborty, A., Allison, D.C.S., Ribbens, C.J., and Watson, L.T. 1989. Parallel orthogonal decompositions of rectangular matrices for curve tracking on a hypercube. In Proc., Fourth Conf. on Hypercube Concurrent Computers and Applications (Monterey, Calif.), ACM, pp. 651-654.
[5] Chow, S.N., Mallet-Paret, J., and Yorke, J.A. 1978. Finding zeros of maps: Homotopy methods that are constructive with probability one. Math. Comput., 32: 887-899. · Zbl 0398.65029 · doi:10.1090/S0025-5718-1978-0492046-9
[6] Craig, EJ. 1954. Iteration procedures for simultaneous equations. Ph.D. thesis, Mass. Institute of Technology, Cambridge, Mass.
[7] deSa, C., Irani, K.M., Ribbens, C.J., Watson, L.T., and Walker, H.F. To appear. Preconditioned iterative methods for homotopy curve tracking. SIAM J. Stat. Comput. · Zbl 0747.65035
[8] Elman, H.C. 1982. Iterative methods for large, sparse, nonsymmetric systems of linear equations. Ph.D. thesis, Comp. Sci. Dept., Yale Univ., New Haven, Conn.
[9] Fadeev, D.K., and Fadeeva, V.N. 1963. Computational Methods of Linear Algebra. Freeman, London.
[10] Hestenes, M.R. 1956. The conjugate gradient method for solving linear equations. In Proc., Symp. Appl. Math., vol. 6, Numer. Anal. (New York), AMS, pp. 83-102. · Zbl 0072.14102
[11] Hestenes, M.R., and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bureau of Standards, 49: 409-435. · Zbl 0048.09901
[12] Irani, K.M. 1990. Preconditioned sequential and parallel conjugate gradient algorithms for homotopy curve tracking. M.S. thesis, Dept. of Comp. Sci., Va. Polytechnic Institute & State Univ., Blacksburg, Va.
[13] Irani, K.M., Kamat, M.P., Ribbens, C.J., Walker, H.F., and Watson, L.T. 1991. Experiments with conjugate gradient algorithms for homotopy curve tracking. SIAM J. Optim., 1: 222-251. · Zbl 0757.65057 · doi:10.1137/0801016
[14] Rheinboldt, W.C., and Burkardt, J.V. 1983. Algorithm 596: A program for a locally parameterized continuation process. ACM Trans. Math. Software, 9: 236-241. · doi:10.1145/357456.357461
[15] Varga, R.S. 1962. Matrix Iterative Analysis. Prentice-Hall, New York. · Zbl 0133.08602
[16] Watson, L.T. 1979. A globally convergent algorithm for computing fixed points of C 2maps. Appl. Math. Comput., 5: 297-311. · Zbl 0445.65032 · doi:10.1016/0096-3003(79)90020-1
[17] Watson, L.T. 1986. Numerical linear algebra aspects of globally convergent homotopy methods. SIAM Rev., 28: 529-545. · Zbl 0608.65028 · doi:10.1137/1028157
[18] Watson, L.T., Billups, S.C., and Morgan, A.P. 1987. Algorithm 652: HOMPACK: A suite of codes for globally convergent homotopy algorithms. ACM Trans. Math. Software, 13: 281-310. · Zbl 0626.65049 · doi:10.1145/29380.214343
[19] Young, D.M. 1971. Iterative Solution of Large Linear Systems. Academic Press, New York. · Zbl 0231.65034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.