Regenerative cascade homotopies for solving polynomial systems |
| |
Authors: | Jonathan D Hauenstein Andrew J Sommese Charles W Wampler |
| |
Institution: | a Department of Mathematics, Mailcode 3368, Texas A&M University, College Station, TX 77843, United States b Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, United States c General Motors Research and Development, Mail Code 480-106-224, 30500 Mound Road, Warren, MI 48090, United States |
| |
Abstract: | 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. |
| |
Keywords: | Witness superset Generic points Homotopy continuation Cascade homotopy Numerical algebraic geometry Polynomial system Numerical irreducible decomposition Algebraic set |
本文献已被 ScienceDirect 等数据库收录! |
|