Computing all space curve solutions of polynomial systems by polyhedral methods. (English) Zbl 1453.13084
Gerdt, Vladimir P. (ed.) et al., Computer algebra in scientific computing. 18th international workshop, CASC 2016, Bucharest, Romania, September 19–23, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9890, 73-86 (2016).
Summary: A polyhedral method to solve a system of polynomial equations exploits its sparse structure via the Newton polytopes of the polynomials. We propose a hybrid symbolic-numeric method to compute a Puiseux series expansion for every space curve that is a solution of a polynomial system. The focus of this paper concerns the difficult case when the leading powers of the Puiseux series of the space curve are contained in the relative interior of a higher dimensional cone of the tropical prevariety. We show that this difficult case does not occur for polynomials with generic coefficients. To resolve this case, we propose to apply polyhedral end games to recover tropisms hidden in the tropical prevariety.
For the entire collection see [Zbl 1346.68010].
For the entire collection see [Zbl 1346.68010].
MSC:
| 13P15 | Solving polynomial systems; resultants |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
| 14T15 | Combinatorial aspects of tropical varieties |
| 65H10 | Numerical computation of solutions to systems of equations |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
Newton polytope; polyhedral end game; polyhedral method; polynomial system; Puiseux series; space curve; tropical basis; tropical prevariety; tropismReferences:
| [1] | Adrovic, D., Verschelde, J.: Computing Puiseux series for algebraic surfaces. In: van der Hoeven, J., van Hoeij, M. (eds.) Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), pp. 20–27. ACM (2012) · Zbl 1323.68578 · doi:10.1145/2442829.2442837 |
| [2] | Adrovic, D., Verschelde, J.: Polyhedral methods for space curves exploiting symmetry applied to the cyclic n-roots problem. In: Gerdt, V.P., Koepf, W., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2013. LNCS, vol. 8136, pp. 10–29. Springer, Heidelberg (2013) · Zbl 1412.13030 · doi:10.1007/978-3-319-02297-0_2 |
| [3] | Bernshteǐn, D.: The number of roots of a system of equations. Funct. Anal. Appl. 9(3), 183–185 (1975) · Zbl 0328.32001 · doi:10.1007/BF01075595 |
| [4] | Bogart, T., Jensen, A., Speyer, D., Sturmfels, B., Thomas, R.: Computing tropical varieties. J. Symbolic Comput. 42(1), 54–73 (2007) · Zbl 1121.14051 · doi:10.1016/j.jsc.2006.02.004 |
| [5] | Grayson, D., Stillman, M.: Macaulay2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/ |
| [6] | Herrero, M., Jeronimo, G., Sabia, J.: Affine solution sets of sparse polynomial systems. J. Symbolic Comput. 51(1), 34–54 (2012) · Zbl 1264.13027 |
| [7] | Herrero, M., Jeronimo, G., Sabia, J.: Elimination for generic sparse polynomial systems. Discrete Comput. Geom. 51(3), 578–599 (2014) · Zbl 1310.68261 · doi:10.1007/s00454-014-9571-z |
| [8] | Herrero, M., Jeronimo, G., Sabia, J.: Puiseux expansions and non-isolated points in algebraic varieties. Commun. Algebra 44(5), 2100–2109 (2016) · Zbl 1346.14136 · doi:10.1080/00927872.2015.1033717 |
| [9] | Hida, Y., Li, X., Bailey, D.: Algorithms for quad-double precision floating point arithmetic. In: 15th IEEE Symposium on Computer Arithmetic (Arith-15 2001), 11–17, Vail, CO, USA, pp. 155–162. IEEE Computer Society (2001). Shortened version of Technical Report LBNL-46996, software at http://crd.lbl.gov/ dhbailey/mpdist/qd-2.3.9.tar.gz |
| [10] | Huber, B., Sturmfels, B.: A polyhedral method for solving sparse polynomial systems. Math. Comput. 64(212), 1541–1555 (1995). http://www.jstor.org/stable/2153370 · Zbl 0849.65030 · doi:10.1090/S0025-5718-1995-1297471-4 |
| [11] | Huber, B., Verschelde, J.: Polyhedral end games for polynomial continuation. Numer. Algorithms 18(1), 91–108 (1998) · Zbl 0933.65057 · doi:10.1023/A:1019163811284 |
| [12] | Jensen, A., Leykin, A., Yu, J.: Computing tropical curves via homotopy continuation. Exp. Math. 25(1), 83–93 (2016) · Zbl 1350.14045 · doi:10.1080/10586458.2015.1037407 |
| [13] | Jensen, A., Yu, J.: Computing tropical resultants. J. Algebra 387, 287–319 (2013) · Zbl 1316.14117 · doi:10.1016/j.jalgebra.2013.03.031 |
| [14] | Jensen, A.: Computing Gröbner fans and tropical varieties in Gfan. In: Stillman, M., Takayama, N., Verschelde, J. (eds.) Software for Algebraic Geometry. The IMA Volumes in Mathematics and its Applications, vol. 148, pp. 33–46. Springer, Heidelberg (2008) · Zbl 1148.68579 · doi:10.1007/978-0-387-78133-4_3 |
| [15] | Jeronimo, G., Matera, G., Solernó, P., Waissbein, A.: Deformation techniques for sparse systems. Found. Comput. Math. 9(1), 1–50 (2008). http://dx.doi.org/10.1007/s10208-008-9024-2 · Zbl 1167.14039 · doi:10.1007/s10208-008-9024-2 |
| [16] | Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry, Graduate Studies in Mathematics, vol. 161. American Mathematical Society, Providence (2015) · Zbl 1321.14048 · doi:10.1090/gsm/161 |
| [17] | OEIS Foundation Inc.: The on-line encyclopedia of integer sequences (2016). http://oeis.org . Accessed 03 Nov 2015 |
| [18] | Römer, T., Schmitz, K.: Generic tropical varieties. J. Pure Appl. Algebra 216(1), 140–148 (2012). http://www.sciencedirect.com/science/article/pii/S0022404911001290 · Zbl 1246.14082 · doi:10.1016/j.jpaa.2011.05.012 |
| [19] | Sabeti, R.: Numerical-symbolic exact irreducible decomposition of cyclic-12. LMS J. Comput. Math. 14, 155–172 (2011) · Zbl 1228.65079 · doi:10.1112/S146115701000001X |
| [20] | Schneider, R.: Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications, vol. 44. Cambridge University Press, Cambridge (1993) · Zbl 0798.52001 · doi:10.1017/CBO9780511526282 |
| [21] | Sommars, J., Verschelde, J.: Pruning algorithms for pretropisms of Newton polytopes. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2016. LNCS, vol. 9890, pp. 489–503 (2016) · Zbl 1453.52015 · doi:10.1007/978-3-319-45641-6_31 |
| [22] | Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25(2), 251–276 (1999) · Zbl 0961.65047 · doi:10.1145/317275.317286 |
| [23] | Verschelde, J.: Polyhedral methods in numerical algebraic geometry. In: Bates, D., Besana, G., Di Rocco, S., Wampler, C. (eds.) Interactions of Classical and Numerical Algebraic Geometry, Contemporary Mathematics, vol. 496, pp. 243–263. AMS (2009) · Zbl 1181.65073 · doi:10.1090/conm/496/09727 |
| [24] | Verschelde, J.: Modernizing PHCpack through phcpy. In: de Buyl, P., Varoquaux, N. (eds.) Proceedings of the 6th European Conference on Python in Science (EuroSciPy 2013), pp. 71–76 (2014) |
| [25] | Verschelde, J., Verlinden, P., Cools, R.: Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SIAM J. Numer. Anal. 31(3), 915–930 (1994) · Zbl 0809.65048 · doi:10.1137/0731049 |
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.
