Regenerative cascade homotopies for solving polynomial systems

• Published in: Applied mathematics and computation 2011-10, Vol.218 (4), p.1240-1246
• Main Authors: Hauenstein, Jonathan D., Sommese, Andrew J., Wampler, Charles W.
• Format: Article
• Language: English
• Subjects: Algebraic set; Cascade homotopy; Cascades; Computation; Generic points; Homotopy continuation; Mathematical models; Numerical algebraic geometry; Numerical analysis; Numerical irreducible decomposition; Polynomial system; Randomization; Regeneration; Regenerative; Slicing; Witness superset
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2011.06.004

A key step in the numerical computation of the irreducible decomposition of a polynomial system is the computation of a witness superset of the solution set. In many problems involving a solution set of a polynomial system, the witness superset contains all the needed information. Sommese and Wampler gave the first numerical method to compute witness supersets, based on dimension-by-dimension slicing of the solution set by generic linear spaces, followed later by the cascade homotopy of Sommese and Verschelde. Recently, the authors of this article introduced a new method, regeneration, to compute solution sets of polynomial systems. Tests showed that combining regeneration with the dimension-by-dimension algorithm was significantly faster than naively combining it with the cascade homotopy. However, in this article, we combine an appropriate randomization of the polynomial system with the regeneration technique to construct a new cascade of homotopies for computing witness supersets. Computational tests give strong evidence that regenerative cascade is superior in practice to previous methods.