Computing Gröbner fans of toric ideals. (English) Zbl 0978.13019
In the theory of Gröbner bases it is well-known that the reduced Gröbner bases of a homogeneous ideal correspond to the vertices of a polytope, the so-called state polytope. Term orders are identified if the associated reduced Gröbner basis is the same. The cones of equivalent term orders form a fan which is the normal fan of the state polytope. The authors present an algorithm for the computation of all vertices of the state polytope in case the ideal is a toric ideal. In this case the local changes in the Gröbner walk become purely combinatorial. The major improvement of the Gröbner walk for a toric ideal is analogous to the reverse enumeration of vertices of a polytope by Avis and Fukuda. The authors show that all reduced Gröbner bases of a toric ideal may be ordered in an acyclic directed graph. Implementation details and examples as well as web address for the developed software are given. This nice paper will be interesting not only for people working in computational algebraic geometry, but for everybody working on efficient algorithms.
Reviewer: Karin Gatermann (Berlin)
MSC:
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 14Q05 | Computational aspects of algebraic curves |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
| 68W30 | Symbolic computation and algebraic computation |
Software:
TiGERSReferences:
| [1] | Adams W. W., An introduction to Gröobner bases (1994) |
| [2] | Amrhein B., Theoret. Comput. Sci. 187 (1) pp 179– (1997) · Zbl 0895.13012 · doi:10.1016/S0304-3975(97)00064-9 |
| [3] | Avis D., Disc. Comput. Geom. 8 pp 295– (1992) · Zbl 0752.68082 · doi:10.1007/BF02293050 |
| [4] | Bayer D., J. Symbolic Comput. 6 (2) pp 209– (1988) · Zbl 0675.13014 · doi:10.1016/S0747-7171(88)80043-9 |
| [5] | Billera L. J., Adv. Math. 83 (2) pp 155– (1990) · Zbl 0714.52004 · doi:10.1016/0001-8708(90)90077-Z |
| [6] | Collart S., J. Symbolic Comput. 24 (3) pp 465– (1997) · Zbl 0908.13020 · doi:10.1006/jsco.1996.0145 |
| [7] | Cox D., Ideals, varieties, and algorithms.,, 2. ed. (1997) |
| [8] | Gel’fand I. M., Discriminants, resultants, and multidimensional determinants (1994) · doi:10.1007/978-0-8176-4771-1 |
| [9] | Maclagan D., ”Antichains of monomial ideals are finite” · Zbl 0984.13013 |
| [10] | Maclagan D., ”Combinatorics of the toric Hilbert scheme” (1999) · Zbl 1073.14503 |
| [11] | Masada, T., Imai, H. and Imai, K. ”Enumeration of regular triangulations”. proc. 12th annual Symposium on Computational Geometry. Philadelphia, PA. pp.224–233. New York: ACM Press. [Masada et al. 1996] · Zbl 0925.68445 |
| [12] | Mora T., J. Symbolic Comput. 6 (2) pp 183– (1988) · Zbl 0668.13017 · doi:10.1016/S0747-7171(88)80042-7 |
| [13] | Peeva I., J. Amer. Math. Soc. 11 (2) pp 363– (1998) · Zbl 0905.13005 · doi:10.1090/S0894-0347-98-00255-0 |
| [14] | Saito M., Gröobner deformations of hypergeometric differential eguations (2000) |
| [15] | Sturmfels B., Gröobner bases and convex polytopes. (1996) · Zbl 0856.13020 |
| [16] | Sturmfels B., Math. Programming 77 (3) pp 357– (1997) |
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.
