Solutions to Systems of Binomial Equations

• Autorzy: Tianran Chen , Tien-Yien Li
• Języki publikacji: EN

Abstrakty

EN

The problem of solving systems of polynomial equations has been, and will continue to be, one of the most important subjects in both pure and applied mathematics. The need to solve systems of polynomial equations occurs frequently in various fields of science and engineering, such as formulae construction, geometric intersection, inverse kinematics, robotics, computer vision, and the computation of equilibrium states of chemical reaction equations. In this article, we will focus on solving binomial polynomial systems: Systems of polynomial equations in which each equation contains exactly two terms. Binomial polynomial systems (or simply binomial systems) represents an important class of polynomial systems. While the solution structure of binomial systems is interesting in its own right, it actually plays a crucially important role in solving general polynomial systems numerically. (We will elaborate this in details in Section 5.1.) Moreover, binomial systems have direct connections to lattice ideals [34] and toric varieties [9, 15], which admit vast applications. We will take a computational point of view in this article to outline the different ingredients needed to solve binomial polynomial systems exactly and numerically. To facilitate the discussion, Section 2 introduces notations and conventions to be used. Section 3 discusses the structure of solution sets of binomial systems and their important properties. Section 4 investigates different aspects in solving binomial systems from a computational point of view. In particular, we will discuss the problems in computation when the coefficients of the binomial systems are not provided exactly. Among various kinds of applications for binomial systems, we present, in Section 5, two important and interesting applications. First one illustrates the heavy reliance on solving binomial systems when solving general polynomial systems by the efficient polyhedral homotopies. Second example highlights the needs and difficulties in solving binomial systems that arose in supersymmetric gauge theory in theoretical physics. Finally, for solving larger binomial systems from applied sciences, parallel computation becomes inevitable. Section 6 showcases some recent developments in the parallel implementation of solvers for binomial systems. (fragment of text)

Słowa kluczowe

EN

Mathematics; Algebra

PL

Matematyka; Algebra

• Czasopismo: Annales Mathematicae Silesianae
• Rocznik: 2014
• Tom: 28
• Strony: 7--34

Twórcy

autor

Tianran Chen

• Michigan State University, USA

autor

Tien-Yien Li

• Michigan State University, USA

Bibliografia

• Allgower E., Georg K., Introduction to numerical continuation methods, Society for Industrial and Applied Mathematics, Philadelphia, 2003.
• Barber C.B., Dobkin D.P., Huhdanpaa H., The quickhull algorithm for convex hulls, ACM Trans. Math. Software 22 (1996), 469-483.
• 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.
• Bernshtein D.N., The number of roots of a system of equations, Funct. Anal. Appl. 9 (1975), 183-185.
• Büeler B., Enge A., Fukuda K., Exact volume computation for polytopes: A practical study, 1998.
• Chen T.R., Lee T.L., Li T.Y., Hom4PS-3: an numerical solver for polynomial systems using homotopy continuation methods. Available at http://www.hom4ps3.org.
• Chen T.R., Lee T.L., Li T.Y., Mixed volume computation in parallel, Taiwanese J. Math. 18 (2014), 93-114.
• Cohen H., A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.
• Cox D.A., Little J.B., Schenck H.K., Toric varieties, American Mathematical Society, Providence, 2011.
• 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.
• Drexler F.J., Eine methode zur berechnung sämtlicher lösungen von polynomgleichungssystemen, Numer. Math. 29 (1977), 45-58.
• Eisenbud D., Sturmfels B., Binomial ideals, Duke Math. J. 84 (1996), 1-46.
• Emiris I.Z., Canny J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput. 20 (1995), 117-149.
• Enge A., Büeler B., Fukuda K., VINCI: an easy to install C package that implements the state of the art algorithms for volume computation. Available at http://www.math.u-bordeaux1.fr/~aenge/?category=software&page=vinci.
• Fulton W., Introduction to toric varieties, Princeton University Press, Princeton, 1993.
• Gao T., Li T.Y., Wu M., Algorithm 846: MixedVol: a software package for mixedvolume computation, ACM Trans. Math. Software 31 (2005), 555-560.
• Garcia C.B., Zangwill W.I., Finding all solutions to polynomial systems and other systems of equations, Math. Program. 16 (1979), 159-176.
• Gockenbach M.S., Finite-dimensional linear algebra, CRC Press, Boca Raton, 2011.
• Grayson D.R., Stillman M.E., Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.
• 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.
• Hartshorne R., Algebraic geometry, Springer-Verlag, Berlin, 1977.
• 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.
• Huber B., Sturmfels B., A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), 1541-1555.
• Jensen A.N., Gfan, a software system for Gröbner fans and tropical varieties. Available at http://home.imf.au.dk/jensen/software/gfan/gfan.html.
• Kahle T., Decompositions of binomial ideals, Ann. Inst. Statist. Math. 62 (2010), 727-745.
• 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), 266-267.
• Lee T.L., Li T.Y., Mixed volume computation in solving polynomial systems, Contemp. Math 556 (2011), 97-112.
• 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.
• 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.
• 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.
• 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.
• Li T.Y., Wang X., The BKK root count in Cn, Math. Comput. 65 (1996), 1477-1484.
• 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.
• Miller E., Sturmfels B., Combinatorial commutative algebra, Springer-Verlag, New York, 2005.
• 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.
• Morgan A.P., Sommese A.J., Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), 123-160.
• Sommese A.J., Wampler C.W., The numerical solution of systems of polynomials arising in engineering and science, World Scientific Press, Singapore, 2005.
• Verschelde J., Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software 25 (1999), 251-276.
• Zhuang Y., Parallel Implementation of Polyhedral Homotopy Methods, Ph.D. thesis, University of Illinois at Chicago 2007.