zbMATH — the first resource for mathematics

Exploiting chordal structure in polynomial ideals: a Gröbner bases approach. (English) Zbl 1353.13033
The paper contains a new elimination method for polynomial systems. The method is well suitable for systems with many equations and many variables, but there are only few variables in each equation. The idea is to use classical elimination (by Gröbner bases) for carefully chosen subsets of equations and variables in an iterative way. Algorithm 2 computes upper and lower bounds for elimination ideals. Theorem 3 gives sufficient conditions for these bounds being exact; hence in these cases, Algorithm 2 computes the precision ideals. Algorithm 3 computes a description of the ideal which has properties sumilar to a lexicographical Gröbner basis. In case of zero dimension, it is easy to compute all solutions when such a description is known.

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
Full Text: DOI arXiv
[1] S. Arnborg, D. G. Corneil, and A. Proskurowski, Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8 (1987), pp. 277–284, http://dx.doi.org/10.1137/0608024 doi:10.1137/0608024. · Zbl 0611.05022
[2] G. V. Bard, N. T. Courtois, and C. Jefferson, Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers, Report 2007/024, Cryptology ePrint Archive, http://eprint.iacr.org, 2007.
[3] D. A. Bayer, The Division Algorithm and the Hilbert Scheme, Ph.D. thesis, Harvard University, Cambridge, MA, 1982.
[4] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM, 30 (1983), pp. 479–513. · Zbl 0624.68087
[5] J. Blair and B. Peyton, An introduction to chordal graphs and clique trees, in Graph Theory and Sparse Matrix Computation, Springer, Berlin, 1993, pp. 1–29. · Zbl 0803.68081
[6] H. L. Bodlaender and A. Koster, Combinatorial optimization on graphs of bounded treewidth, Comput. J., 51 (2008), pp. 255–269.
[7] M. Brickenstein and A. Dreyer, PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials, J. Symbol. Comput., 44 (2009), pp. 1326–1345, http://dx.doi.org/DOI:10.1016/j.jsc.2008.02.017 doi:10.1016/ j.jsc.2008.02.017. · Zbl 1186.68571
[8] C. Cid, S. Murphy, and M. Robshaw, Small scale variants of the AES, in Fast Software Encryption, Springer, Berlin, 2005, pp. 145–162. · Zbl 1140.94330
[9] B. Courcelle and J. Engelfriet, Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, Encyclopedia Math. Appl. 138, Cambridge University Press, Cambridge, UK, 2012. · Zbl 1257.68006
[10] D. A. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, Berlin, 2007. · Zbl 1118.13001
[11] V. Dalmau, P. G. Kolaitis, and M. Y. Vardi, Constraint satisfaction, bounded treewidth, and finite-variable logics, in Principles and Practice of Constraint Programming (CP 2002), Springer, Berlin, 2002, pp. 310–326.
[12] T. A. Davis, J. R. Gilbert, S. I. Larimore, and E. G. Ng, A column approximate minimum degree ordering algorithm, ACM Trans. Math. Software, 30 (2004), pp. 353–376. · Zbl 1073.65039
[13] J. A. De Loera, J. Lee, S. Margulies, and S. Onn, Expressing combinatorial problems by systems of polynomial equations and Hilbert’s nullstellensatz, Combin. Probab. Comput., 18 (2009), pp. 551–582, http://dx.doi.org/10.1017/S0963548309009894 doi:10.1017/S0963548309009894. · Zbl 1197.05155
[14] J. A. De Loera, S. Margulies, M. Pernpeintner, E. Riedl, D. Rolnick, G. Spencer, D. Stasi, and J. Swenson, Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases, in Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation (ISSAC’15), ACM, New York, 2015, pp. 133–140, http://dx.doi.org/10.1145/2755996.2756639 doi:10.1145/2755996.2756639. · Zbl 1345.68154
[15] R. Dechter, Bucket elimination: A unifying framework for probabilistic inference, in Learning in Graphical Models, Springer, Berlin, 1998, pp. 75–104. · Zbl 0910.68209
[16] R. Dechter, Constraint Processing, Morgan Kaufmann, San Francisco, 2003.
[17] W. Decker, G. M. Greuel, G. Pfister, and H. Schönemann, Singular 4-0-2—A Computer Algebra System for Polynomial Computations, http://www.singular.uni-kl.de, 2015.
[18] I. Z. Emiris and J. F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbol. Comput., 20 (1995), pp. 117–149, http://dx.doi.org/10.1006/jsco.1995.1041 doi:10.1006/jsco.1995.1041. · Zbl 0843.68036
[19] J. C. Faugère, P. Gaudry, L. Huot, and G. Renault, Polynomial Systems Solving by Fast Linear Algebra, preprint, http://arxiv.org/abs/1304.6039 arXiv:1304.6039 [cs.SC], 2013.
[20] J. C. Faugère and S. Rahmany, Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, in Proceedings of the 34th International Symposium on Symbolic and Algebraic Computation (ISSAC’09), ACM, New York, 2009, pp. 151–158.
[21] J. C. Faugère, M. Safey El Din, and P. J. Spaenlehauer, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1, 1)\): Algorithms and complexity, J. Symbol. Comput., 46 (2011), pp. 406–437. · Zbl 1226.13017
[22] J. C. Faugère, P. J. Spaenlehauer, and J. Svartz, Sparse Gröbner bases: The unmixed case, in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC’14), ACM, New York, 2014, pp. 178–185, http://dx.doi.org/10.1145/2608628.2608663 doi:10.1145/2608628.2608663.
[23] S. Gao, Counting Zeros over Finite Fields Using Gröbner Bases, M.S. thesis in Logic and Computation, Carnegie Mellon University, Pittsburgh, PA, 2009.
[24] S. Gao, V. M. Rodrigues, and J. Stroomer, Gröbner Basis Structure of Finite Sets of Points, preprint, Department of Mathematical Sciences, Clemson University, Clemson, SC, http://www.math.clemson.edu/ sgao/papers/GBstr.pdf, 2003.
[25] K. Gatemann, Symbolic solution polynomial equation systems with symmetry, in Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’90), ACM, New York, 1990, pp. 112–119, http://dx.doi.org/10.1145/96877.96907 doi:10.1145/96877.96907.
[26] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math. 57, Elsevier B. V., Amsterdam, 2004. · Zbl 1050.05002
[27] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, and J. Rauh, Binomial edge ideals and conditional independence statements, Adv. Appl. Math., 45 (2010), pp. 317–333, http://dx.doi.org/10.1016/j.aam.2010.01.003 doi:10.1145/96877.96907. · Zbl 1196.13018
[28] C. J. Hillar and T. Windfeldt, Algebraic characterization of uniquely vertex colorable graphs, J. Combin. Theory Ser. B, 98 (2008), pp. 400–414. · Zbl 1134.05026
[29] B. Huber and B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp., 64 (1995), pp. 1541–1555. · Zbl 0849.65030
[30] Y. N. Lakshman, On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal, in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, ACM, New York, 1990, pp. 555–563.
[31] S. L. Lauritzen and D. J. Spiegelhalter, 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
[32] T. Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numer., 6 (1997), pp. 399–436. · Zbl 0886.65054
[33] J. A. Makowsky and K. Meer, Polynomials of bounded treewidth, in Foundations of Computational Mathematics, Proceedings of the Smalefest 2000, F. Cucker and M. Rojas, eds., World Scientific, Singapore, 2002, pp. 211–250. · Zbl 1018.65063
[34] J. Nie and J. Demmel, Sparse SOS relaxations for minimizing functions that are summations of small polynomials, SIAM J. Optim., 19 (2008), pp. 1534–1558, http://dx.doi.org/10.1137/060668791 doi:10.1137/060668791. · Zbl 1178.65048
[35] S. Parter, The use of linear graphs in Gauss elimination, SIAM Rev., 3 (1961), pp. 119–130, http://dx.doi.org/10.1137/1003021 doi:10.1137/1003021. · Zbl 0102.11302
[36] V. I. Paulsen, S. C. Power, and R. R. Smith, Schur products and matrix completions, J. Funct. Anal., 85 (1989), pp. 151–178. · Zbl 0672.15008
[37] A. Pothen and S. Toledo, Elimination structures in scientific computing, in Handbook on Data Structures and Applications, D. Mehta and S. Sahni, eds., CRC Press, Boca Raton, FL, 2004, pp. 59-1–59-29. · Zbl 1387.68099
[38] H. Raddum and I. Semaev, New Technique for Solving Sparse Equation Systems, Report 2006/475, Cryptology ePrint Archive, http://eprint.iacr.org, 2006. · Zbl 1179.94067
[39] D. J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32 (1970), pp. 597–609. · Zbl 0216.02602
[40] A. J. Sommese and C. W. Wampler, The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, World Scientific, Singapore, 2005. · Zbl 1091.65049
[41] W. A. Stein et al., SageMath, Free Open-Source Mathematics Software System, http://www.sagemath.org (accessed 06-20-16).
[42] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series 8, American Mathematical Society, Providence, RI, 1996.
[43] L. Vandenberghe and M. S. Andersen, Chordal graphs and semidefinite optimization, Found. Trends Optim., 1 (2015), pp. 241–433, http://dx.doi.org/10.1561/2400000006 doi:10.1561/2400000006.
[44] R. Villarreal, Cohen-Macaulay graphs, Manuscripta Math., 66 (1990), pp. 277–293, http://dx.doi.org/10.1007/BF02568497 doi:10.1007/BF02568497. · Zbl 0737.13003
[45] R. Villarreal, Monomial Algebras, 2nd ed., Monogr. Res. Notes Math. 8, CRC Press, Boca Raton, FL, 2015.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.