Geodesic
Complexity of the Standard Basis of a~$D$-Module
Algebra i analiz, Tome 20 (2008) no. 5, pp. 41-82.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{AA_2008_20_5_a2,
     author = {D. Yu. Grigoriev and A. L. Chistov},
     title = {Complexity of the {Standard} {Basis} of a~$D${-Module}},
     journal = {Algebra i analiz},
     pages = {41--82},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AA_2008_20_5_a2/}
}
TY  - JOUR
AU  - D. Yu. Grigoriev
AU  - A. L. Chistov
TI  - Complexity of the Standard Basis of a~$D$-Module
JO  - Algebra i analiz
PY  - 2008
SP  - 41
EP  - 82
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AA_2008_20_5_a2/
LA  - ru
ID  - AA_2008_20_5_a2
ER  - 
%0 Journal Article
%A D. Yu. Grigoriev
%A A. L. Chistov
%T Complexity of the Standard Basis of a~$D$-Module
%J Algebra i analiz
%D 2008
%P 41-82
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AA_2008_20_5_a2/
%G ru
%F AA_2008_20_5_a2
D. Yu. Grigoriev; A. L. Chistov. Complexity of the Standard Basis of a~$D$-Module. Algebra i analiz, Tome 20 (2008) no. 5, pp. 41-82. http://geodesic.mathdoc.fr/item/AA_2008_20_5_a2/

[1] Bayer D. A., The division algorithm and the Hilbert scheme, Ph. D. Thesis, Harvard, 1982

[2] Chistov A., Grigor'ev D., “Complexity of quantifier elimination in the theory of algebraically closed fields”, Mathematical Foundations of Computer Science (Prague, 1984), Lecture Notes in Comput. Sci., 176, Springer, Berlin, 1984, 17–31 | MR

[3] Cox D., Little J., O'Shea D., Using algebraic geometry, Grad. Texts in Math., 185, Springer-Verlag, New York, 1998 | MR | Zbl

[4] Dubé T., “The structure of polynomial ideals and Gröbner bases”, SIAM J. Comput., 19 (1990), 750–775 | DOI | MR

[5] Galligo A., “Some algorithmic questions on ideals of differential operators”, EUROCAL' 85, vol. 2 (Linz, 1985), Lecture Notes in Comput. Sci., 204, Springer, Berlin, 1985, 413–421 | MR

[6] Giusti M., “Some effectivity problems in polynomial ideal theory”, EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci., 174, Springer, Berlin, 1984, 159–171 | MR

[7] Grigoriev D., “Weak Bézout inequality for D-modules”, J. Complexity, 21 (2005), 532–542 | DOI | MR | Zbl

[8] Hermann G., “Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”, Math. Ann., 95 (1926), 736–788 | DOI | MR | Zbl

[9] Janet M., “Les modules de formes algébriques et la théorie générale des systèmes différentiels”, Ann. Sci. École Norm. Sup. (3), 41 (1924), 27–65 | MR | Zbl

[10] Li H., Noncommutative Gröbner bases and filtered-graded transfer, Lecture Notes in Math., 1795, Springer-Verlag, Berlin, 2002 | MR

[11] Macaulay F. S., “Some properties of enumeration in the theory of modular systems”, Proc. London Math. Soc., 26 (1927), 531–555 | DOI | Zbl

[12] Möller H., Mora F., “Upper and lower bounds for the degree of Groebner bases”, EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci., 174, Springer, Berlin, 1984, 172–183 | MR

[13] Ritter G., Weispfenning V., “On the number of term orders”, Appl. Algebra Engrg. Comm. Comput., 2 (1991), 55–79 | DOI | MR | Zbl

[14] Schwarz F., “Janet bases for symmetry groups”, Gröbner Bases and Applications (Linz, 1998), London Math. Soc. Lecture Note Ser., 251, Cambridge Univ. Press, Cambridge, 1998, 221–234 | MR | Zbl

[15] Yap C. K., “A new lower bound construction for commutative Thue systems with applications”, J. Symbolic Comput., 12 (1991), 1–27 | DOI | MR | Zbl