Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube

ABSTRACT

Polynomial systems of equations frequently arise in many applications such as solid modelling, robotics, computer vision, chemistry, chemical engineering, and mechanical engineering. Locally convergent iterative methods such as quasi-Newton methods may diverge or fail to find all meaningful solutions of a polynomial system. Recently a homotopy algorithm has been proposed for polynomial systems that is guaranteed globally convergent (always converges from an arbitrary starting point) with probability one, finds all solutions to the polynomial system, and has a large amount of inherent parallelism. There are several ways the homotopy algorithms can be decomposed to run on a hypercube. The granularity of a decomposition has a profound effect on the performance of the algorithm. The results of decompositions with two different granularities are presented. The experiments were conducted on an iPSC-16 hypercube using actual industrial problems.

REFERENCES

• 1: E. ALLGOWER AND K. GEORG, Simplicial and continuation methods for approximating fixed points, SIAM Rev., 22 (1980), pp. 28-85.
• 2: D. C. S. ALLISON, S. HA}tIMOTO, AND L. T. WATSON, The Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equation, Manuscript.
• 3: S. C. BILLUPS, An augmented Jacobian matrix algorithm for tracking homotopy zero curves, M.S. Thesis, Dept. of Computer Sci., VPI&SU, Blacksburg, VA, Sept., 1985.
• 4: R. H. BYRD, R. B. SCHNABEL, AND G. A. SHULTZ, Using parallel function evaluation to improve Hessian approximation for unconstrained optimization, Technical Report CS-CU-361-87, Dept. of Computer Science, University of Colorado, Boulder, Colorado 80309, 1987.
• 5: S. N. CHOW, J. MALLET-PARET, AND j. A. YORKE, Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Comput., 32 (1978), pp. 887-899.
• 6: M. COSNAaD, Y. ROBERT, AND D. TRYSTaAN, Comparison ofparallel diagonalization methods for solving dense linear systems, Sessions of the French Acad. of Sci. on Math., Nov., 1985, p. 781ff.
• 7: J. E. DENNIS JR., AND R. B. SCHNABEL, A view of unconstrained optimization, Tech. Rep. CU- CS-376-87, Dept. of Computer Science, University of Colorado, Boulder, Colorado 80309, 1987.
• 8: G. H. ELLIS AND L. T. WATSON, A parallel algorithm for simple roots of polynomials, Comput. Math. Appl., 10 (1984), pp.107-121.
• 9: R. A. FINKEL, Large-grain Parallelism - Three case studies, in The characteristics of parallel algorithms, L. H. Jamieson, D. B. Gannon, and R. J. Douglass, eds., (1987), pp. 21-63.
• 10: W. GENTZSCH AND G. SCHAFER, Solution of large linear systems on vector computers, Parallel Computing 83, North Holland, Amsterdam, 1984, pp. 159-166.
• 11: D. HELLEa, A survey of parallel algorithms in numerical linear algebra, SIAM Rev., 20 (1978), pp. 740-777.
• 12: Milan Kubíček, Algorithm 502: Dependence of Solution of Nonlinear Systems on a Parameter [C5], ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.98-107, March 1976 [doi>10.1145/355666.355675]
• 13: A. P. MOaGAN, A transformation to avoid solutions at infinity for polynomial systems, Appl. Math. Comput., 18 (1986), pp. 77-86.
• 14: -----, A homotopy for solving polynomial systems, Appl. Math. Comput., 18 (1986), pp. 87-92.
• 15: -----, Solving polynomial systems using continuation for engineering and scientific problems, Prentice-Hall, Englewood Cliffs, NJ, 1987.
• 16: Alexander P. Morgan , Layne T. Watson, Globally Convergent Parallel Algorithm for Zeros of Polynomial Systems, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1986
• 17: Wolfgang Pelz , Layne T. Watson, Message Length Effects for Solving Polynomial Systems on a Hypercube, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1986
• 18: D. A. REED AND M. L. PATRTCK, A model of asynchronous itemtive algorithms for solving large sparse linear systems, Proc. 1984 Internat. Conf. on Parallel Processing, August 21-24, 1984, pp. 402-410.
• 19: 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]
• 20: T. A. Rice. AND L. J. SIEGEL, A parallel algorithm for finding the roots of a polynomial, Proc. Internat. Conf. Parallel Processing, Bellaire, MI, Aug. 24-27, pp. 57-61, 1982.
• 21: R. B. SCHNASEL, AND P. D. FgANK, Solving systems of nonlinear equations by tensor methods, Tech. Rep. CU-CS-334-86, Dept. of Computer Science, Univ. of Colorado, Boulder, Colorado 80309, June, 1986.
• 22: R. B. SCHNABEL, Concurrent function evaluations in local and global optimization, Tech. Rep. CS-CU-345-86, Dept. of Computer Science, Univ. of Colorado, Boulder, Colorado 80309, 1986.
• 23: H. SCHWANDT, Newton-like interval methods for large nonlinear systems of equations on vector computers, Computer Phys. Comm., 37 (1985), pp. 223-232.
• 24: H. J. SIPS, A parallel processor for nonlinear recurrence systems, Proc. 1st Internat. Conf. on Supercomputing Systems, IEEE Computer Society Press, Los Alamitos, CA, 1984, pp. 660-671.
• 25: Layne T. Watson , Dan Fenner, Algorithm 555: Chow-Yorke Algorithm for Fixed Points or Zeros of C2 Maps [C5], ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.252-259, June 1980 [doi>10.1145/355887.355899]
• 26: L. T. WATSON, A globally convergent algorithm for computing fixed points of C2 maps, Appl. M~th. Comput., 5 (1979), pp. 297-311.
• 27: L. T. WATSON, S. C. BILLUPS, AND A. P. MORGAN, HOMPACK: A suite of codes for globally convergent homotopy algorithms, Tech. Rep. 85-34, Dept. of Industrial and Operations Eng., Univ. of Michigan., Ann Arbor, MI, 1985.
• 28: L. T. WATSON, ?(umerical linear algebra aspects of globally convergent homotopy methods, Tech. Rep. TR-85-14, Dept. of Computer Sci., VPI&SU, Blacksburg, VA, 1985.
• 29: R E White, Parallel algorithms for nonlinear problems, SIAM Journal on Algebraic and Discrete Methods, v.7 n.1, p.137-149, Jan. 1986 [doi>10.1137/0607017]
• 30: R E White, A nonlinear parallel algorithm with application to the Stefan problem, SIAM Journal on Numerical Analysis, v.23 n.3, p.639-652, June 1986 [doi>10.1137/0723040]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Theory