Solutions to systems of binomial equations
Abstract
Annual Lecture dedicated to the memory of Professor Andrzej Lasota.
Keywords
binomial system; BKK bound; master space; polyhedral homotopy
References
1. Allgower E., Georg K., Introduction to numerical continuation methods, Society for Industrial and Applied Mathematics, Philadelphia, 2003.
2. Barber C.B., Dobkin D.P., Huhdanpaa H., The quickhull algorithm for convex hulls, ACM Trans. Math. Software 22 (1996), 469–483.
3. Bates D.J., Hauenstein J.D., Sommese A.J., Wampler C.W., Numerically Solving Polynomial Systems with Bertini, Society for Industrial and Applied Mathematics, Philadelphia, 2013.
4. Bernshtein D.N., The number of roots of a system of equations, Funct. Anal. Appl. 9 (1975), 183–185.
5. Büeler B., Enge A., Fukuda K., Exact volume computation for polytopes: A practical study, 1998.
6. Chen T.R., Lee T.L., Li T.Y., Mixed volume computation in parallel, Taiwanese J. Math. 18 (2014), 93–114.
7. Cohen H., A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.
8. Cox D.A., Little J.B., Schenck H.K., Toric varieties, American Mathematical Society, Providence, 2011.
9. Donfack S., Dongarra J., Faverge M., Gates M., Kurzak J., Luszczek P., Yamazaki I., On algorithmic variants of parallel Gaussian elimination: Comparison of implementations in terms of performance and numerical properties, Tech. Rep. 280, LAPACK Working Note (2013). Available at http://www.netlib.org/lapack/lawnspdf/lawn280.pdf.
10. Drexler F.J., Eine methode zur berechnung sämtlicher lösungen von polynomgleichungssystemen, Numer. Math. 29 (1977), 45–58.
11. Eisenbud D., Sturmfels B., Binomial ideals, Duke Math. J. 84 (1996), 1–46.
12. Emiris I.Z., Canny J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput. 20 (1995), 117–149.
13. Fulton W., Introduction to toric varieties, Princeton University Press, Princeton, 1993.
14. Gao T., Li T.Y., Wu M., Algorithm 846: MixedVol: a software package for mixed-volume computation, ACM Trans. Math. Software 31 (2005), 555–560.
15. Garcia C.B., Zangwill W.I., Finding all solutions to polynomial systems and other systems of equations, Math. Program. 16 (1979), 159–176.
16. Gockenbach M.S., Finite-dimensional linear algebra, CRC Press, Boca Raton, 2011.
17. Gunji T., Kim S., Kojima M., Takeda A., Fujisawa K., Mizutani T., PHoM–a polyhedral homotopy continuation method for polynomial systems, Computing 73 (2004), 57–77.
18. Hartshorne R., Algebraic geometry, Springer-Verlag, Berlin, 1977.
19. He Y.H., Candelas P., Hanany A., Lukas A., Ovrut B., Computational algebraic geometry in string and gauge theory, Adv. High Energy Phys. 2012, Art. ID 431898, 4 pp.
20. Huber B., Sturmfels B., A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), 1541–1555.
21. Kahle T., Decompositions of binomial ideals, Ann. Inst. Statist. Math. 62 (2010), 727–745.
22. Kushnirenko A.G., A Newton polyhedron and the number of solutions of a system of k equations in k unknowns, Usp. Math. Nauk 30 (1975), 66–267.
23. Lee T.L., Li T.Y., Mixed volume computation in solving polynomial systems, Contemp. Math 556 (2011), 97–112.
24. 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 (2008), 109–133.
25. Lee T.L., Li T.Y., Tsai C.H., HOM4PS-2.0 para: Parallelization of HOM4PS-2.0 for solving polynomial systems, Parallel Comput. 35 (2009), 226–238.
26. Li T.Y., Numerical solution of polynomial systems by homotopy continuation methods, in: Handbook of Numerical Analysis, ed. P.G. Ciarlet, vol. 11, North-Holland, Amsterdam, 2003, pp. 209–304.
27. Li T.Y., Sauer T., Yorke J., The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal. (1989), 1241–1251.
28. Li T.Y., Wang X., The BKK root count in Cn, Math. Comput. 65 (1996), 1477–1484.
29. Mehta D., He Y.H., Hauenstein J., Numerical algebraic geometry: a new perspective on gauge and string theories, J. High Energy Phys. 18 (2012), 1–32.
30. Miller E., Sturmfels B., Combinatorial commutative algebra, Springer-Verlag, New York, 2005.
31. Mizutani T., Takeda A., DEMiCs: A software package for computing the mixed volume via dynamic enumeration of all mixed cells, in: Software for Algebraic Geometry, Springer, New York, 2008, pp. 59–79.
32. Morgan A.P., Sommese A.J., Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), 123–160.
33. Sommese A.J., Wampler C.W., The numerical solution of systems of polynomials arising in engineering and science, World Scientific Press, Singapore, 2005.
34. Verschelde J., Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software 25 (1999), 251–276.
35. Zhuang Y., Parallel Implementation of Polyhedral Homotopy Methods, Ph.D. thesis, University of Illinois at Chicago, 2007.
2. Barber C.B., Dobkin D.P., Huhdanpaa H., The quickhull algorithm for convex hulls, ACM Trans. Math. Software 22 (1996), 469–483.
3. Bates D.J., Hauenstein J.D., Sommese A.J., Wampler C.W., Numerically Solving Polynomial Systems with Bertini, Society for Industrial and Applied Mathematics, Philadelphia, 2013.
4. Bernshtein D.N., The number of roots of a system of equations, Funct. Anal. Appl. 9 (1975), 183–185.
5. Büeler B., Enge A., Fukuda K., Exact volume computation for polytopes: A practical study, 1998.
6. Chen T.R., Lee T.L., Li T.Y., Mixed volume computation in parallel, Taiwanese J. Math. 18 (2014), 93–114.
7. Cohen H., A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.
8. Cox D.A., Little J.B., Schenck H.K., Toric varieties, American Mathematical Society, Providence, 2011.
9. Donfack S., Dongarra J., Faverge M., Gates M., Kurzak J., Luszczek P., Yamazaki I., On algorithmic variants of parallel Gaussian elimination: Comparison of implementations in terms of performance and numerical properties, Tech. Rep. 280, LAPACK Working Note (2013). Available at http://www.netlib.org/lapack/lawnspdf/lawn280.pdf.
10. Drexler F.J., Eine methode zur berechnung sämtlicher lösungen von polynomgleichungssystemen, Numer. Math. 29 (1977), 45–58.
11. Eisenbud D., Sturmfels B., Binomial ideals, Duke Math. J. 84 (1996), 1–46.
12. Emiris I.Z., Canny J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput. 20 (1995), 117–149.
13. Fulton W., Introduction to toric varieties, Princeton University Press, Princeton, 1993.
14. Gao T., Li T.Y., Wu M., Algorithm 846: MixedVol: a software package for mixed-volume computation, ACM Trans. Math. Software 31 (2005), 555–560.
15. Garcia C.B., Zangwill W.I., Finding all solutions to polynomial systems and other systems of equations, Math. Program. 16 (1979), 159–176.
16. Gockenbach M.S., Finite-dimensional linear algebra, CRC Press, Boca Raton, 2011.
17. Gunji T., Kim S., Kojima M., Takeda A., Fujisawa K., Mizutani T., PHoM–a polyhedral homotopy continuation method for polynomial systems, Computing 73 (2004), 57–77.
18. Hartshorne R., Algebraic geometry, Springer-Verlag, Berlin, 1977.
19. He Y.H., Candelas P., Hanany A., Lukas A., Ovrut B., Computational algebraic geometry in string and gauge theory, Adv. High Energy Phys. 2012, Art. ID 431898, 4 pp.
20. Huber B., Sturmfels B., A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), 1541–1555.
21. Kahle T., Decompositions of binomial ideals, Ann. Inst. Statist. Math. 62 (2010), 727–745.
22. Kushnirenko A.G., A Newton polyhedron and the number of solutions of a system of k equations in k unknowns, Usp. Math. Nauk 30 (1975), 66–267.
23. Lee T.L., Li T.Y., Mixed volume computation in solving polynomial systems, Contemp. Math 556 (2011), 97–112.
24. 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 (2008), 109–133.
25. Lee T.L., Li T.Y., Tsai C.H., HOM4PS-2.0 para: Parallelization of HOM4PS-2.0 for solving polynomial systems, Parallel Comput. 35 (2009), 226–238.
26. Li T.Y., Numerical solution of polynomial systems by homotopy continuation methods, in: Handbook of Numerical Analysis, ed. P.G. Ciarlet, vol. 11, North-Holland, Amsterdam, 2003, pp. 209–304.
27. Li T.Y., Sauer T., Yorke J., The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal. (1989), 1241–1251.
28. Li T.Y., Wang X., The BKK root count in Cn, Math. Comput. 65 (1996), 1477–1484.
29. Mehta D., He Y.H., Hauenstein J., Numerical algebraic geometry: a new perspective on gauge and string theories, J. High Energy Phys. 18 (2012), 1–32.
30. Miller E., Sturmfels B., Combinatorial commutative algebra, Springer-Verlag, New York, 2005.
31. Mizutani T., Takeda A., DEMiCs: A software package for computing the mixed volume via dynamic enumeration of all mixed cells, in: Software for Algebraic Geometry, Springer, New York, 2008, pp. 59–79.
32. Morgan A.P., Sommese A.J., Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), 123–160.
33. Sommese A.J., Wampler C.W., The numerical solution of systems of polynomials arising in engineering and science, World Scientific Press, Singapore, 2005.
34. Verschelde J., Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software 25 (1999), 251–276.
35. Zhuang Y., Parallel Implementation of Polyhedral Homotopy Methods, Ph.D. thesis, University of Illinois at Chicago, 2007.
ChenT., & LiT.-Y. (2014). Solutions to systems of binomial equations. Annales Mathematicae Silesianae, 28, 7-34. Retrieved from https://journals.us.edu.pl/index.php/AMSIL/article/view/13987
Tianran Chen
chentia1@msu.edu
Department of Mathematics, Michigan State University, USA United States
Department of Mathematics, Michigan State University, USA United States
Tien-Yien Li
Department of Mathematics, Michigan State University, USA United States
Department of Mathematics, Michigan State University, USA United States
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
