Regenerative cascade homotopies for solving polynomial systems. (English) Zbl 1231.65190
Summary: 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.
MSC:
| 65M99 | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
Keywords:
witness superset; generic points; homotopy continuation; cascade homotopy; numerical algebraic geometry; polynomial system; numerical irreducible decomposition; algebraic setReferences:
| [1] | D.J. Bates, J.D. Hauenstein, A.J. Sommese, Efficient path tracking methods, Numer. Algorithms, in press, doi:10.1007/s11075-011-9463-8; D.J. Bates, J.D. Hauenstein, A.J. Sommese, Efficient path tracking methods, Numer. Algorithms, in press, doi:10.1007/s11075-011-9463-8 · Zbl 1230.65059 |
| [2] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Adaptive multiprecision path tracking, SIAM J. Numer. Anal., 46, 2, 722-746 (2008) · Zbl 1162.65026 |
| [3] | D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: Software for Numerical Algebraic Geometry, <www.nd.edu/∼;sommese/bertini>; D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: Software for Numerical Algebraic Geometry, <www.nd.edu/∼;sommese/bertini> · Zbl 1143.65344 |
| [4] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Stepsize control for adpative multiprecision path tracking, Contemp. Math., 496, 21-31 (2009) · Zbl 1181.65071 |
| [5] | D.J. Bates, L. Oeding, Toward a Salmon Conjecture. Available from: <arXiv:1009.6181 [arxiv.org/abs]>; D.J. Bates, L. Oeding, Toward a Salmon Conjecture. Available from: <arXiv:1009.6181 [arxiv.org/abs]> · Zbl 1262.14056 |
| [6] | Dayton, B. H.; Zeng, Z., Computing the multiplicity structure in solving polynomial systems, (ISSAC’05 (2005), ACM: ACM New York), 116-123, (electronic) · Zbl 1360.65151 |
| [7] | Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Regeneration homotopies for solving systems of polynomials, Math. Comput., 80, 345-377 (2011) · Zbl 1221.65121 |
| [8] | Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 1541-1555 (1995) · Zbl 0849.65030 |
| [9] | Laubenbacher, R. C.; Swanson, I., Permanental ideals, J. Sym. Comput., 30, 195-205 (2000) · Zbl 0966.13007 |
| [10] | T.-L. Lee, T.Y. Li, C.-H. Tsai, HOM4PS-2.0, Solving Polynomial Systems by the Polyhedral Homotopy Method, <www.math.msu.edu/∼;li>; T.-L. Lee, T.Y. Li, C.-H. Tsai, HOM4PS-2.0, Solving Polynomial Systems by the Polyhedral Homotopy Method, <www.math.msu.edu/∼;li> · Zbl 1167.65366 |
| [11] | Leykin, A.; Verschelde, J.; Zhao, A., Higher-order deflation for polynomial systems with isolated singular solutions, (Dickenstein, A.; Schreyer, F.-O.; Sommese, A. J., IMA. IMA, Algorithms in Algebraic Geometry, vol. 146 (2008), Springer), 79-97 · Zbl 1138.65038 |
| [12] | Leykin, A.; Verschelde, J.; Zhao, A., Newton’s method with deflation for isolated singularities of polynomial systems, Theor. Comput. Sci., 359, 111-122 (2006) · Zbl 1106.65046 |
| [13] | Li, T. Y., Numerical solution of polynomial system by homotopy continuation methods, (Handbook of Numerical Analysis, vol. XI (2003), North-Holland: North-Holland Amsterdam), 209-304 · Zbl 1059.65046 |
| [14] | Ojika, T., Modified deflation algorithm for the solution of singular problems. I.A system of nonlinear algebraic equations, J. Math. Anal. Appl., 123, 199-221 (1987) · Zbl 0625.65043 |
| [15] | Ojika, T.; Watanabe, S.; Mitsui, T., Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl., 96, 463-479 (1983) · Zbl 0525.65027 |
| [16] | Sommese, A. J.; Verschelde, J., Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complex., 16, 572-602 (2000) · Zbl 0982.65070 |
| [17] | Sommese, A. J.; Verschelde, J.; Wampler, C. W., Homotopies for intersecting solution components of polynomial systems, SIAM J. Numer. Anal., 42, 1552-1571 (2004) · Zbl 1108.13308 |
| [18] | A.J. Sommese, C.W. Wampler, Numerical algebraic geometry, in: J. Renegar, M. Shub, S. Smale (Eds.), The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32, 1996, pp. 749-763, Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah.; A.J. Sommese, C.W. Wampler, Numerical algebraic geometry, in: J. Renegar, M. Shub, S. Smale (Eds.), The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32, 1996, pp. 749-763, Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah. · Zbl 0856.65054 |
| [19] | Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific: World Scientific Singapore · Zbl 1091.65049 |
| [20] | Su, H.-J.; McCarthy, J. M.; Sosonkina, M.; Watson, L. T., Algorithm 857: POLSYS_GLP: a parallel general linear product homotopy code for solving polynomial systems of equations, ACM Trans. Math. Softw., 32, 4, 561-579 (2006) · Zbl 1230.65058 |
| [21] | Verschelde, J., Algorithm 795: PHC pack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 2, 251-276 (1999) · Zbl 0961.65047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
