Browse Prior Art Database

The Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equations

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

Publishing Venue

Software Patent Institute

Related People

D.C.S Allison: AUTHOR [+5]

Abstract

Polynomial systems consist of n polynomial functions in n variables, with real or complex coefficients. Finding zeros of such systems is challenging because there may be a large number of solutions, and Newton-type methods can rarely be guaranteed to find the complete set of solutions. There axe homotopy algorithms for polynomial systems of equations that are globally convergent from an arbitrary starting point with probability one, are guaranteed to find all the solutions, and are robust, accurate, and reasonably efficient. There is inherent parallelism at several levels in these algorithms. Several parallel homotopy algorithms with different granularities axe studied on several different parallel machines, using actual industrial problems from chemical engineering and solid modeling.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equations

D.C.S Allison, S. Harimoto, and L.T. Watson

TR 88 1-1988 The Granularity of Parallel Homotopy Algorithms for Polynomial Systems of Equations

D. C. S. Allison, S. Haximotot, and L. T. VVatsont

Department of Computer Science Virginia Polytechnic Institute 8r, State University Blacksburg, VA 24061

Abstract.

Polynomial systems consist of n polynomial functions in n variables, with real or complex coefficients. Finding zeros of such systems is challenging because there may be a large number of solutions, and Newton-type methods can rarely be guaranteed to find the complete set of solutions. There axe homotopy algorithms for polynomial systems of equations that are globally convergent from an arbitrary starting point with probability one, are guaranteed to find all the solutions, and are robust, accurate, and reasonably efficient. There is inherent parallelism at several levels in these algorithms. Several parallel homotopy algorithms with different granularities axe studied on several different parallel machines, using actual industrial problems from chemical engineering and solid modeling.

1. Introduction.

Solving nonlinear systems of equations is a central problem in numerical analysis, with enormous significance for science and engineering. A very special case, namely small polynomial systems of equations, occurs frequently enough in solid modeling, robotics, computer vision; chemical equilibrium computations, chemical process design, mechanical engineering, and other areas to justify special algorithms. To put polynomial systems in perspective and for the purpose of this discussion, 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 axe not counted. Large sparse non~fneax systems of equations, such as equilibrium. equations in structural me-chanics, have two characterizing aspects: highly nonlinear and recursive scaiax 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 v~zth a small amount of linear algebra. Finally, 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 special nature of polynomial systems and the power of homotopy algorithms axe often not...