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

A. L. Chistov
Affiliation: Steklov Institute of Mathematics, Fontanka 27, St. Petersburg 191023, Russia

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