×

Chordal networks of polynomial ideals. (English) Zbl 1444.13037

In the paper under review, the authors introduce a new representation of structured polynomial ideals that is called a chordal network. A chordal network is well-suited for operation involving elimination, and so gives an efficient alternative to Gröbner bases elimination techniques, preserving the possible sparsity of the polynomial system in some way. This gives a contribution in computational algebraic geometry and in other related topics.
A chordal network can be computed for every polynomial system and has particular good performance for many interesting families of polynomial ideals that the authors consider. It provides a description of “a decomposition of a polynomial ideal into simpler (triangular) polynomial sets”. In some cases this description can be compact even if the decomposition may be extremely large.
The definition (Definition 2.7) and computation of a chordal network are based, respectively, on the concept of chordal graph (Definition 2.1) and on a refinement of the chordal elimination algorithm, which the authors introduced in a previous paper (Algorithm 1 for a particular case and its extension to arbitrary ideals in subsection 6.3).
The authors provide many motivating examples and applications of a chordal network in order to obtain information about the algebraic variety defined by the polynomial system, such as the dimension. Moreover, a probabilistic test for the radical ideal membership problem is given (Algorithm 3 for a particular case and its extension to the general case in subsection 6.4).
The paper ends providing many examples and applications in several related topics. In the Appendix some additional proofs are collected. A preliminary implementation of a Macaulay2 package with all the methods that arose in this paper is available.

MSC:

13P15 Solving polynomial systems; resultants
14Q99 Computational aspects in algebraic geometry
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. B. Akers, {\it Binary decision diagrams}, IEEE Trans. Computers, 100 (1978), pp. 509-516. · Zbl 0377.94038
[2] S. Arnborg, D. G. Corneil, and A. Proskurowski, {\it Complexity of finding embeddings in a \(k\)-tree}, SIAM J. Algebraic Discrete Methods, 8 (1987), pp. 277-284, . · Zbl 0611.05022
[3] P. Aubry, D. Lazard, and M. M. Maza, {\it On the theories of triangular sets}, J. Symbolic Comput., 28 (1999), pp. 105-124. · Zbl 0943.12003
[4] J. R. Blair and B. Peyton, {\it An introduction to chordal graphs and clique trees}, in Graph Theory and Sparse Matrix Computation, Springer, New York, 1993, pp. 1-29. · Zbl 0803.68081
[5] H. L. Bodlaender and A. M. Koster, {\it Combinatorial optimization on graphs of bounded treewidth}, Comput. J., 51 (2008), pp. 255-269.
[6] H. L. Bodlaender and A. M. Koster, {\it Treewidth computations I. Upper bounds}, Inform. and Comput., 208 (2010), pp. 259-275. · Zbl 1186.68328
[7] R. E. Bryant, {\it Symbolic boolean manipulation with ordered binary-decision diagrams}, ACM Computing Surveys (CSUR), 24 (1992), pp. 293-318.
[8] D. Cifuentes and P. A. Parrilo, {\it An efficient tree decomposition method for permanents and mixed discriminants}, Linear Algebra Appl., 493 (2016), pp. 45-81. · Zbl 1329.15020
[9] D. Cifuentes and P. A. Parrilo, {\it Exploiting chordal structure in polynomial ideals: A Gröbner bases approach}, SIAM J. Discrete Math., 30 (2016), pp. 1534-1570, . · Zbl 1353.13033
[10] J. A. De Loera, J. Lee, P. N. Malkin, and S. Margulies, {\it Hilbert’s Nullstellensatz and an algorithm for proving combinatorial infeasibility}, in Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation, ISSAC’08, ACM, New York, 2008, pp. 197-206. · Zbl 1297.05229
[11] R. Dechter, {\it Constraint Processing}, Morgan Kaufmann, San Francisco, CA, 2003. · Zbl 1057.68114
[12] W. Decker, G. Greuel, G. Pfister, and H. Schönemann, {\it Singular \3-1-6–a computer algebra system for polynomial computations}, , 2012.
[13] P. Diaconis, D. Eisenbud, and B. Sturmfels, {\it Lattice walks and primary decomposition}, in Mathematical Essays in Honor of Gian-Carlo Rota, B. E. Sagan and R. P. Stanley, eds., Progr. Math. 161, Birkhäuser Boston, Boston, MA, 1998, pp. 173-193. · Zbl 0962.05010
[14] S. N. Evans, B. Sturmfels, and C. Uhler, {\it Commuting birth-and-death processes}, Ann. Appl. Probab., 20 (2010), pp. 238-266. · Zbl 1200.60072
[15] S. Gao, {\it Counting Zeros over Finite Fields Using Gröbner Bases}, Master’s thesis, Carnegie Mellon University, Pittsburgh, PA, 2009.
[16] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, and J. Rauh, {\it Binomial edge ideals and conditional independence statements}, Adv. Appl. Math., 45 (2010), pp. 317-333. · Zbl 1196.13018
[17] E. Hubert, {\it Notes on Triangular Sets and Triangulation-Decomposition Algorithms I: Polynomial Systems}, Springer, New York, 2003. · Zbl 1022.12004
[18] T. Kahle, {\it Decompositions of binomial ideals}, Ann. Inst. Statist. Math., 62 (2010), pp. 727-745. · Zbl 1440.62394
[19] M. Kalkbrener, {\it A generalized Euclidean algorithm for computing triangular representations of algebraic varieties}, J. Symbolic Comput., 15 (1993), pp. 143-167. · Zbl 0783.14039
[20] E. Kaltofen, {\it Polynomial factorization 1987-1991}, in Proceedings of the 1st Latin American Symposium on Theoretical Informatics, I. Simon, ed., Springer, Berlin, Heidelberg, 1992, pp. 294-313.
[21] D. E. Knuth, {\it Combinatorial Algorithms, Part 1}, Art Comput. Program. 4A, Addison-Wesley, Boston, MA, 2011. · Zbl 1354.68001
[22] S. R. Kosaraju, {\it Decidability of reachability in vector addition systems}, in Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC ’82, ACM, New York, 1982, pp. 267-281.
[23] S. L. Lauritzen and D. J. Spiegelhalter, {\it Local computations with probabilities on graphical structures and their application to expert systems}, J. Roy. Statist. Soc. Ser. B, 50 (1988), pp. 157-224. · Zbl 0684.68106
[24] D. Lazard, {\it Solving zero-dimensional algebraic systems}, J. Symbolic Comput., 13 (1992), pp. 117-131. · Zbl 0753.13012
[25] F. Lemaire, M. M. Maza, and Y. Xie, {\it The RegularChains library}, in Maple Conference (Waterloo, Canada), Vol. 5, 2005, pp. 355-368. · Zbl 1114.68628
[26] M. M. Maza, {\it On triangular decompositions of algebraic varieties}, presented at the MEGA-2000 Conference, NAG, UK, 2000.
[27] M. Monagan and R. Pearce, {\it Sparse polynomial division using a heap}, J. Symbolic Comput., 46 (2011), pp. 807-822. · Zbl 1291.68435
[28] D. J. Rose, R. E. Tarjan, and G. S. Lueker, {\it Algorithmic aspects of vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp. 266-283, . · Zbl 0353.65019
[29] F. Rouillier, {\it Solving zero-dimensional systems through the rational univariate representation}, Appl. Algebra Engrg. Comm. Comput., 9 (1999), pp. 433-461. · Zbl 0932.12008
[30] W. Stein et al., {\it Sage: Open Source Mathematical Software}, , 2008.
[31] B. Sturmfels, {\it Solving Systems of Polynomial Equations}, CBMS Regional Conf. Ser. Math. 97, AMS, Providence, RI, 2002. · Zbl 1101.13040
[32] L. Vandenberghe and M. S. Andersen, {\it Chordal graphs and semidefinite optimization}, Found. Trends Optim., 1 (2014), pp. 241-433.
[33] R. Villarreal, {\it Monomial Algebras}, 2nd ed., CRC Press, Boca Raton, FL, 2015. · Zbl 1325.13004
[34] J. von zur Gathen and J. Gerhard, {\it Modern Computer Algebra}, Cambridge University Press, Cambridge, UK, 2013. · Zbl 1277.68002
[35] D. Wang, {\it Computing triangular systems and regular systems}, J. Symbolic Comput., 30 (2000), pp. 221-236. · Zbl 1007.65039
[36] D. Wang, {\it Elimination Methods}, Springer, New York, 2001. · Zbl 0964.13014
[37] D. Wang, {\it Elimination Practice: Software Tools and Applications}, Imperial College Press, London, 2003.
[38] I. Wegener, {\it Branching Programs and Binary Decision Diagrams: Theory and Applications}, Discrete Math. Appl. 4, SIAM, Philadelphia, 2000. · Zbl 0956.68068
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.