|
This article is cited in 8 scientific papers (total 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.
Received: 30.03.2007
Citation:
D. Yu. Grigoriev, A. L. Chistov, “Complexity of the Standard Basis of a $D$-Module”, Algebra i Analiz, 20:5 (2008), 41–82; St. Petersburg Math. J., 20:5 (2009), 709–736
Linking options:
https://www.mathnet.ru/eng/aa530 https://www.mathnet.ru/eng/aa/v20/i5/p41
|
|