Browse Prior Art Database

Granularity Issues for Solving Polynomial Systems via Globally Convergent Algorithms on a Hyperoube

IP.com Disclosure Number: IPCOM000128718D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 16 page(s) / 48K

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 text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 16

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...