RUS  ENG
Full version
JOURNALS // Algebra i Analiz // Archive

Algebra i Analiz, 2008 Volume 20, Issue 5, Pages 41–82 (Mi aa530)

This article is cited in 8 papers

Research Papers

Complexity of the Standard Basis of a $D$-Module

D. Yu. Grigorieva, A. L. Chistovb

a CNRS, IRMAR, Université de Rennes, Rennes, France
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences

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 elaborated for constructing all the solutions of a linear system over a homogeneous version of a Weyl algebra.

Keywords: Weyl algebra, Janet basis, Gröbner basis.

MSC: 16Z05

Received: 30.03.2007


 English version:
St. Petersburg Mathematical Journal, 2009, 20:5, 709–736

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024