Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
St. Petersburg Mathematical Journal
St. Petersburg Mathematical Journal
ISSN 1547-7371(online) ISSN 1061-0022(print)

 

Complexity of a standard basis of a $ D$-module


Authors: D. Yu. Grigoriev and A. L. Chistov
Translated by: The authors
Original publication: Algebra i Analiz, tom 20 (2008), nomer 5.
Journal: St. Petersburg Math. J. 20 (2009), 709-736
MSC (2000): Primary 16Z05
Published electronically: July 21, 2009
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A double-exponential upper bound is obtained for the degree and for the complexity of constructing a standard basis of a $ D$-module. This generalizes a well-known bound for the complexity of a Gröbner basis of a module over the algebra of polynomials. It should be emphasized that the bound obtained cannot be deduced immediately from the commutative case. To get the bound in question, a new technique is developed for constructing all the solutions of a linear system over a homogeneous version of a Weyl algebra.


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


Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 16Z05

Retrieve articles in all journals with MSC (2000): 16Z05


Additional Information

D. Yu. Grigoriev
Affiliation: CNRS, IRMAR, Université de Rennes Beaulieu, 35042, Rennes, France
Email: dmitry.grigoryev@univ-rennes1.fr

A. L. Chistov
Affiliation: Steklov Institute of Mathematics, Fontanka 27, St. Petersburg 191023, Russia
Email: alch@pdmi.ras.ru

DOI: http://dx.doi.org/10.1090/S1061-0022-09-01069-3
PII: S 1061-0022(09)01069-3
Keywords: Weyl algebra, Janet basis, Gr\"obner basis
Received by editor(s): March 30, 2007
Published electronically: July 21, 2009
Article copyright: © Copyright 2009 American Mathematical Society