×

Comparison of probabilistic algorithms for analyzing the components of an affine algebraic variety. (English) Zbl 1410.65205

Summary: Systems of polynomial equations arise throughout mathematics, engineering, and the sciences. It is therefore a fundamental problem both in mathematics and in application areas to find the solution sets of polynomial systems. The focus of this paper is to compare two fundamentally different approaches to computing and representing the solutions of polynomial systems: numerical homotopy continuation and symbolic computation. Several illustrative examples are considered, using the software packages Bertini and Singular.

MSC:

65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
14Q15 Computational aspects of higher-dimensional varieties
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alt, H., Über die erzeugung gegebener ebener kurven mit hilfe des gelenkvierecks, Z. Angew. Math. Mech., 3, 1, 13-19, (1923) · JFM 49.0567.03
[2] Bates, D. J.; Hauenstein, J. D.; McCoy, T.; Peterson, C.; Sommese, A. J., Recovering exact results from inexact numerical data in algebraic geometry, Exp. Math., 22, 1, 38-50, (2013) · Zbl 1284.14084
[3] Bates, D. J.; Hauenstein, J. D.; Peterson, C.; Sommese, A. J., A numerical local dimension test for points on the solution set of a system of polynomial equations, SIAM J. Numer. Anal., 47, 3608-3623, (2009) · Zbl 1211.14066
[4] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J., Efficient path tracking methods, Numer. Algorithms, 58, 4, 451-459, (2011) · Zbl 1230.65059
[5] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: software for numerical algebraic geometry. <www.bertini.nd.edu>, 2006.
[6] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Adaptive multiprecision path tracking, SIAM J. Numer. Anal., 46, 722-746, (2008) · Zbl 1162.65026
[7] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Stepsize control for adaptive multiprecision path tracking, Contemp. Math., 496, 21-31, (2009) · Zbl 1181.65071
[8] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Numerically solving polynomial systems with Bertini, SIAM, 2013.
[9] Dayton, B.; Zeng, Z., Computing the multiplicity structure in solving polynomial systems, (Proceedings of ISSAC 2005, (2005), ACM New York), 116-123 · Zbl 1360.65151
[10] Decker, W.; Greuel, G.-M.; Pfister, G., Primary decomposition: algorithms and comparisons, (Algorithmic Algebra and Number Theory, (1999), Springer Berlin), 187-220 · Zbl 0932.13019
[11] W. Decker, G.-M. Greuel, G. Pfister, H. Schönemann, Singular 3-1-3—a computer algebra system for polynomial computations. <www.singular.uni-kl.de>, 2011.
[12] Decker, W.; Pfister, G., A first course in computational algebraic geometry, (2012), Cambridge University Press
[13] Greuel, G.-M.; Pfister, G., A singular introduction to commutative algebra, (2008), Springer Berlin · Zbl 1344.13002
[14] Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, J. Symb. Comput., 6, 149-167, (1988) · Zbl 0667.13008
[15] Herzberg, A.; Murty, R., Sudoku squares and chromatic polynomials, Not. AMS, 54, 708-717, (2007) · Zbl 1156.05301
[16] Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Regeneration homotopies for solving systems of polynomials, Math. Comput., 80, 345-377, (2010) · Zbl 1221.65121
[17] Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Regenerative cascade homotopies for solving polynomial systems, Appl. Math. Comput., 218, 1240-1246, (2011) · Zbl 1231.65190
[18] Hauenstein, J. D.; Sottile, F., Algorithm 921: alphacertified: certifying solutions to polynomial systems, ACM Trans. Math. Softw., 38, 4, 28, (2012) · Zbl 1365.65148
[19] Hosten, S.; Sullivant, S., Ideals of adjacent minors, J. Algebra, 277, 615-642, (2004) · Zbl 1073.13007
[20] Innocenti, C., Polynomial solution to the position analysis of the 7-link assur kinematic chain with one quaternary link, Mech. Mach. Theory, 30, 1295-1303, (1995)
[21] Kobayashi, H.; Suzuki, H.; Sakai, Y., Numerical calculation of the multiplicity of a solution to algebraic equations, Math. Comput., 67, 257-270, (1998) · Zbl 0999.65038
[22] 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
[23] Leykin, A.; Verschelde, J.; Zhao, A., Higher-order deflation for polynomial systems with isolated singular solutions, (Algorithms in algebraic geometry, IMA Vol. Math. Appl., vol. 146, (2008), Springer New York), 79-97 · Zbl 1138.65038
[24] Li, T.-Y., Numerical solution of polynomial systems by homotopy continuation methods, Handbook of numerical analysis, vol. XI, (2003), North-Holland Amsterdam, pp. 209-304 · Zbl 1059.65046
[25] Lee, T. L.; Li, T. Y.; Tsai, C. H., HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing, 83, 109-133, (2008) · Zbl 1167.65366
[26] Manolescu, N. I., A method based on baranov trusses, and using graph theory to find the set of planar jointed kinematic chains and mechanisms, Mech. Mach. Theory, 8, 3-22, (1973)
[27] 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
[28] 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
[29] Ritt, J. F., Differential equations from the algebraic standpoint, Amer. Math. Soc. Colloq. Publ., vol. 14, (1932), AMS Providence, RI · JFM 58.0445.06
[30] Ritt, J. F., Differential algebra, Amer. Math. Soc. Colloq. Publ., vol. 33, (1950), AMS Providence, RI · Zbl 0037.18501
[31] Shimoyama, T.; Yokoyama, K., Localization and primary decomposition of polynomial ideals, J. Symb. Comput., 22, 247-277, (1996) · Zbl 0874.13022
[32] Sommese, A. J.; Verschelde, J., Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complexity, 16, 572-602, (2000) · Zbl 0982.65070
[33] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Using monodromy to decompose solution sets of polynomial systems into irreducible components, (Applications of algebraic geometry to coding theory, physics and computation, NATO Sci. Ser. II Math. Phys. Chem., vol. 36, (2001), Kluwer Acad. Publ. Dordrecht), 297-315 · Zbl 0990.65051
[34] Sommese, A. J.; Wampler, C. W., Numerical algebraic geometry, (The mathematics of numerical analysis, Lectures in Appl. Math., vol. 32, (1996), AMS Providence, RI), 749-763 · Zbl 0856.65054
[35] Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, (2005), World Scientific Publishing Co., Pte. Ltd. Hackensack, NJ · Zbl 1091.65049
[36] B. Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, 2002. · Zbl 1101.13040
[37] Su, H.-J.; McCarthy, J. M.; Sosonkina, M.; Watson, L. T., Algorithm 857: POLSYSGLP - a parallel general linear product homotopy code for solving polynomial systems of equations, ACM Trans. Math. Softw., 32, 561-579, (2006) · Zbl 1230.65058
[38] Verschelde, J., Algorithm 795: phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 251-276, (1999) · Zbl 0961.65047
[39] Wampler, C. W.; Morgan, A. P.; Sommese, A. J., Complete solution of the nine-point path synthesis problem for four-bar linkages, ASME J. Mech. Design, 114, 153-159, (1992)
[40] Wampler, C. W.; Morgan, A. P.; Sommese, A. J., Complete solution of the nine-point path synthesis problem for four-bar linkages - closure, ASME J. Mech. Des., 119, 150-152, (1997)
[41] Wilkinson, J. H., The evaluation of the zeros of ill-conditioned polynomials, Numer. Math., 1, 150-180, (1959) · Zbl 0202.43701
[42] Wright, A. H., Finding all solutions to a system of polynomial equations, Math. Comput., 44, 125-133, (1985) · Zbl 0567.55002
[43] Wu, W. J., Basic principles of mechanical theorem proving in elementary geometries, J. Syst. Sci. Math. Sci., 4, 207-235, (1984)
[44] Wunderlich, W., Höhere koppelkurven, Ost. Ing. Arch., 17, 162-165, (1963) · Zbl 0124.39806
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.