Granularity Issues for Solving Polynomial Systems via Globally Convergent Algorithms on a Hyperoube
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Publishing Venue
Software Patent Institute
Related People
D.C.S. Allison: AUTHOR [+5]
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 mean-ingful 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 decom-posed 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.
THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.
Granularity Issues for Solving Polynomial Systems via Globally Convergent Algorithms on a Hyperoube
D.C.S. Allison, Amal Chakraborty, and Layne T. Watson
TR 88 Granularity Issues For Solving Polynomial Systems via Globally Convergent Algorithms on a Hypercube
D. C. S. Allison, Amal Chakrabortyf and Layne T. Watsont
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 mean-ingful 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 decom-posed 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.
1. Introduction.
Solving nonlinear systems of equations has enormous significance for science and engineering.
A very special case, namely small polynomial systems of equations, occurs frequently in solid
modelling, robotics, computer vision, chemical equilibrium computations, chemical process
design, and mechanical engineering. There are three classes of nonlinear systems of equations:
(1) large systems with sparse Jacobian matrices, (2) small transcendental (nonpolynomial)
systems with dense Jacobian matrices, and (3) small polynomial systems with dense Jacobian
matrices. Sparsity for small problems is not significant, and large systems with dense Jacobian
matrices are intractable, so these two classes are not considered.
Large sparse nonlinear systems of equations, such as equilibrium equations in structural me- chanics, have two aspects: highly nonlinear and recursive scalar computations, and large matrix, vector operations. There is a great amount of parallelism in both aspects, but the nature of the parallelism is very different (or so it seems). Small dense. transcendental systems of equations pose a major challenge, since they involve recursive, scalar intensive computation with a small amount of linear algebra. It has been argued that the communication overhead of hypercube machines makes them unsuited for such problems, but the issue is still open and algorithmic breakthroughs are yet possible. Polynomial systems axe unique in that they have many solutions, of which several may be physically meaningful, and there exist homotopy algorithms guaranteed to find all these meaningful solutions. The very sp...