The random product homotopy and deficient polynomial systems (Q1110271)

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.