Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Efficient computation of Castelnuovo-Mumford regularity


Author: Amir Hashemi
Journal: Math. Comp. 81 (2012), 1163-1177
MSC (2010): Primary 14Q20, 13P10
DOI: https://doi.org/10.1090/S0025-5718-2011-02515-9
Published electronically: July 21, 2011
MathSciNet review: 2869055
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we introduce the notion of a homogeneous ideal in quasi stable position (QSP); a new definition for the notion of generic coordinates to compute efficiently the Castelnuovo-Mumford regularity of a homogeneous ideal. This definition is simple to check, because it is tested on the initial ideal for the degree reverse lexicographic ordering. It is explicit, because we provide an algorithm to decide whether a monomial ideal is in QSP or not. The main result of this paper is that the Castelnuovo-Mumford regularity of an ideal in QSP is the maximal degree of the elements of its reduced Gröbner basis with respect to the reverse lexicographic ordering. We have implemented an algorithm in (the distributed library noether.lib of) SINGULAR based on the above results for computing the Castelnuovo-Mumford regularity of a general ideal, and we evaluate its performance via some examples.


References [Enhancements On Off] (What's this?)

  • 1. Amir Hashemi.
    noether.lib.
    A SINGULAR 3.0.3 distributed library for computing Castelnuovo-Mumford regularity, 2007.
  • 2. Dave Bayer.
    The Division Algorithm and the Hilbert Scheme.
    PhD thesis, Harvard University, 1982.
  • 3. David Bayer and Michael Stillman.
    A criterion for detecting $ m$-regularity.
    Invent. Math., 87(1):1-11, 1987. MR 862710 (87k:13019)
  • 4. Isabel Bermejo and Philippe Gimenez.
    Computing the Castelnuovo-Mumford regularity of some subschemes of $ {\mathbb{P}}\sb K\sp n$ using quotients of monomial ideals.
    J. Pure Appl. Algebra, 164(1-2):23-33, 2001.
    Effective methods in algebraic geometry (Bath, 2000). MR 1854328 (2002i:13013)
  • 5. Isabel Bermejo and Philippe Gimenez.
    Saturation and Catelnuovo-Mumford regularity.
    J. Algebra, 303:592-617, 2006. MR 2255124 (2007f:13026)
  • 6. Wolfram Decker, Gert-Martin Greuel, and Gerhard Pfister.
    Primary decomposition: algorithms and comparisons.
    In Algorithmic algebra and number theory (Heidelberg, 1997), pages 187-220. Springer, Berlin, 1999. MR 1672046 (99m:13049)
  • 7. David Eisenbud.
    Commutative algebra with a view toward algebraic geometry, volume 150 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 1995. MR 1322960 (97a:13001)
  • 8. David Eisenbud and Shiro Goto.
    Linear free resolutions and minimal multiplicity.
    J. Algebra, 88(1):89-133, 1984. MR 741934 (85f:13023)
  • 9. Shalom Eliahou and Michel Kervaire.
    Minimal resolutions of some monomial ideals.
    J. Algebra, 129(1):1-25, 1990. MR 1037391 (91b:13019)
  • 10. André Galligo.
    À propos du théorème de-préparation de Weierstrass.
    In Fonctions de plusieurs variables complexes (Sém. François Norguet, octobre 1970-décembre 1973; à la mémoire d'André Martineau), pages 543-579. Lecture Notes in Math., Vol. 409. Springer, Berlin, 1974. MR 0402102 (53:5924)
  • 11. M. Giusti.
    Some effectivity problems in polynomial ideal theory.
    In EUROSAM 84 (Cambridge, 1984), volume 174 of Lecture Notes in Comput. Sci., pages 159-171. Springer, Berlin, 1984. MR 779123 (86d:12001)
  • 12. Mark L. Green.
    Generic initial ideals.
    In Six lectures on commutative algebra (Bellaterra, 1996), volume 166 of Progr. Math., pages 119-186. Birkhäuser, Basel, 1998. MR 1648665 (99m:13040)
  • 13. G.-M. Greuel, G. Pfister, and H. Schönemann.
    SINGULAR 3.0.
    A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005.
  • 14. D. Lazard.
    Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations.
    In Computer algebra (London, 1983), volume 162 of Lecture Notes in Comput. Sci., pages 146-156. Springer, Berlin, 1983. MR 774807 (86m:13002)
  • 15. Daniel Lazard.
    Résolution des systèmes d'équations algébriques.
    Theoret. Comput. Sci., 15(1):77-110, 1981. MR 619687 (82i:12001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14Q20, 13P10

Retrieve articles in all journals with MSC (2010): 14Q20, 13P10


Additional Information

Amir Hashemi
Affiliation: Department of Mathematical Sciences, Isfahan University of Technology, Isfahan 84156-83111, Iran
Email: Amir.Hashemi@cc.iut.ac.ir

DOI: https://doi.org/10.1090/S0025-5718-2011-02515-9
Keywords: Castelnuovo-Mumford regularity, satiety, degree reverse lexicographic ordering, Gröbner bases, complexity
Received by editor(s): April 7, 2008
Received by editor(s) in revised form: January 4, 2011
Published electronically: July 21, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society