Decompositions of binomial ideals. (English) Zbl 1440.62394

Kahle, Thomas

Ann. Inst. Stat. Math. 62, No. 4, 727-745 (2010).

Summary: We present Binomials, a package for the computer algebra system Macaulay 2, which specializes well-known algorithms to binomial ideals. These come up frequently in algebraic statistics and commutative algebra, and it is shown that significant speedup of computations like primary decomposition is possible. While central parts of the implemented algorithms go back to a paper of Eisenbud and Sturmfels, we also discuss a new algorithm for computing the minimal primes of a binomial ideal. All decompositions make significant use of combinatorial structure found in binomial ideals, and to demonstrate the power of this approach we show how Binomialswas used to compute primary decompositions of commuting birth and death ideals of Evans et al., yielding a counterexample for their conjectures.

MSC:

62R01	Algebraic statistics
13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13F20	Polynomial rings and ideals; rings of integer-valued polynomials
62-08	Computational methods for problems pertaining to statistics

Keywords:

algebraic statistics; binomial ideals; commuting birth and death ideals; computational commutative algebra; primary decomposition

Software:

GRIN; 4ti2; Macaulay2; Binomials.m2

References:

[1]	4ti2 team (2007). 4ti2–a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at http://www.4ti2.de
[2]	Altmann K. (2000) The chain property for the associated primes of \({\mathcal{A}}\) -graded ideals. Mathematical Research Letters 7: 565–575 · Zbl 1055.13014
[3]	Bigatti A.M., Scala R.L., Robbiano L. (1999) Computing toric ideals. Journal of Symbolic Computation 27(4): 351–365 · Zbl 0958.13009
[4]	Cox D.A., Little J.B., O’Shea D. (1996) Ideals, varieties, and algorithms (2nd ed.). Undergraduate texts in mathematics. Springer, New York
[5]	Dickenstein, A., Matusevich, L., Miller, E. (2008). Combinatorics of binomial primary decomposition. Mathematische Zeitschrift (to appear). · Zbl 1190.13017
[6]	Drton M., Sturmfels B., Sullivant S. (2009) Lectures on algebraic statistics. Oberwolfach Seminars (Vol. 39). Springer, Birkhäuser, Berlin · Zbl 1166.13001
[7]	Eisenbud D. (1995) Commutative algebra: With a view toward algebraic geometry. Graduate texts in mathematics (Vol. 150). Springer, New York · Zbl 0819.13001
[8]	Eisenbud D., Sturmfels B. (1996) Binomial ideals. Duke Mathematical Journal 84(1): 1–45 · Zbl 0873.13021
[9]	Eisenbud D., Grayson D.R., Stillman M.E., Sturmfels B. (2001) Computations in algebraic geometry with Macaulay 2. Algorithms and computations in Mathematics (Vol. 8). Springer, New York · Zbl 0973.00017
[10]	Evans S., Sturmfels B., Uhler C. (2010) Commuting birth-death processes. Annals of Applied Probability 20(1): 238–266 · Zbl 1200.60072
[11]	Fink, A. (2009). The binomial ideal of the intersection axiom for conditional probabilities. preprint arXiv:09021495 · Zbl 1227.13019
[12]	Fulton W. (1993) Introduction to toric varieties. Annals of Mathematical Studies. Princeton University Press, Princeton · Zbl 0813.14039
[13]	Geiger D., Meek C., Sturmfels B. (2006) On the toric algebra of graphical models. The Annals of Statistics 34(5): 1463–1492 · Zbl 1104.60007
[14]	Gilmer R. (1984) Commutative semigroup rings. University of Chicago Press, Chicago · Zbl 0566.20050
[15]	Hemmecke R., Malkin P. (2009) Computing generating sets of lattice ideals. Journal of Symbolic Computation 44(10): 1493–1476 · Zbl 1200.13048
[16]	Hemmecke R., Morton J., Shiu A., Sturmfels B., Wienand O. (2008) Three counter-examples on semi-graphoids. Combinatorics, Probability and Computation 17: 239–257 · Zbl 1211.62197
[17]	Herzog, J., Hibi, T., Hreinsdóttir, F., Kahle, T., Rauh, J. (2009). Binomial edge ideals and conditional independence statements. Advances in Applied Mathematics (in press). · Zbl 1196.13018
[18]	Hoşten S., Sturmfels B. (1995) Grin: An implementation of groebner bases for integer programming. In: Balas E., Clausen J. (eds) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. Springer, Berlin, pp 267–276
[19]	Hungerford T.W. (1974) Algebra, graduate texts in mathematics (Vol. 73). Springer, New York
[20]	Latouche G., Ramaswami V. (1999) Introduction to matrix analytic methods in stochastic modeling. Statistics and Applied Probability. SIAM, Philadelphia · Zbl 0922.60001
[21]	Miller E., Sturmfels B. (2005) Combinatorial commutative algebra. Graduate texts in mathematics (Vol. 227). Springer, Berlin
[22]	Ojeda I., Piedra R. (2000) Cellular binomial ideals. primary decomposition of binomial ideals. Journal of Symbolic Computation 30: 383–400 · Zbl 0991.13008