The random product homotopy and deficient polynomial systems
type: Item
instance of: scholarly article
title: The random product homotopy and deficient polynomial systems
zbMATH Open document ID: 0656.65055
DOI: 10.1007/BF01400351
author: James A. Yorke
author: Tien-Yien Li
author: Timothy Sauer
published in: Numerische Mathematik
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/133208
review text: Bezout's theorem tells us that, with probability one, a system of n polynomial equations such that the i-th equation has degree \(d_ i\) has \(d=\prod^{n}_{i=1}d_ i\) solutions in complex n-space. However, many, if not most, polynomial systems occurring in practice are not general, but are deficient in the sense that not all possible combinations of products of variables appear, and the actual number of solutions is considerably less than d. Examples are given and the cause of the deficiency is highlighted in this paper. Naively applied continuation methods for finding solutions to polynomial systems require the same amount of work whether the system is deficient or not. In this paper, a general technique for such continuation methods is considered which takes account of the special structure of the terms in deficient systems, and thus computes all roots with considerably less effort. The technique appears to be more general than that in the authors' earlier paper [SIAM J. Numer. Anal. 24, 435-451 (1987; Zbl 0625.65039)]. The homotopies the technique leads to in the examples may also be obtained using ``m-homogeneous'' technique of \textit{A. Morgan} and \textit{A. Sommese} [Appl. Math. Comput. 24, 115-138 (1987; Zbl 0635.65058)]. In fact, the two techniques may be equivalent, though different language is used in the exposition and proofs. In either case, the important thing is to match the ``structure at infinity'' in projective space of the polynomial system to be solved with that of an initial guess polynomial system for which the solutions are known.
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 26C10
Mathematics Subject Classification ID: 65H17
zbMATH DE Number: 4072267
zbMATH Keywords: random product homotopy
zbMATH Keywords: homotopy continuation method
zbMATH Keywords: isolated solutions
zbMATH Keywords: homotopy methods
zbMATH Keywords: m-homogeneous technique
zbMATH Keywords: continuation methods
zbMATH Keywords: polynomial systems
zbMATH Keywords: deficient systems
zbMATH Keywords: structure at infinity
reviewed by: Ralph Baker Kearfott
describes a project that uses: HOMPACK
MaRDI profile type: Publication
cites work: Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations
cites work: Q3862960
cites work: Homotopy Method for General $\lambda $-Matrix Problems
cites work: Q3917180
cites work: Finding all solutions to polynomial systems and other systems of equations
cites work: Q4143433
cites work: Q3703206
cites work: Q3324935
cites work: Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
cites work: Numerical Solution of a Class of Deficient Polynomial Systems
cites work: The local structure of a chaotic attractor in four dimensions
cites work: Q5611879
cites work: A homotopy for solving polynomial systems
cites work: On Steplength Algorithms for a Class of Continuation Methods
cites work: Algorithm 652
cites work: Finding All Solutions to a System of Polynomial Equations
cites work: Q3328651
Recommended article: Q3477888
Recommended article: Solving Deficient Polynomial Systems with Homotopies which Keep the Subschemes at Infinity Invariant
Recommended article: Solving systems of polynomial equations by bounded and real homotopy
Recommended article: An efficient start system for multi-homogeneous polynomial continuation
Recommended article: A simple homotopy for solving deficient polynomial systems
Recommended article: Numerical Solution of a Class of Deficient Polynomial Systems
Recommended article: A new start system for solving deficient polynomial systems using continuation
Recommended article: On the solutions to polynomial systems obtained by homotopy methods
Recommended article: Numerical homotopies to compute generic points on positive dimensional algebraic sets
Recommended article: Homotopies and polynomial system solving I
description: scientific article; zbMATH DE number 4072267