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
DOI: https://doi.org/10.1090/S1061-0022-09-01069-3
Published electronically: July 21, 2009
Full-text PDF

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?)

  • 1. D. A. Bayer, The division algorithm and the Hilbert scheme, Ph.D. Thesis, Harvard, 1982.
  • 2. A. Chistov and D. Grigor'ev, Complexity of quantifier elimination in the theory of algebraically closed fields, Mathematical Foundations of Computer Science (Prague, 1984), Lecture Notes in Comput. Sci., vol. 176, Springer, Berlin, 1984, pp. 17-31. MR 0783435 (86i:03040)
  • 3. D. Cox, J. Little, and D. O'Shea, Using algebraic geometry, Grad. Texts in Math., vol. 185, Springer-Verlag, New York, 1998. MR 1639811 (99h:13033)
  • 4. T. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J. Comput. 19 (1990), 750-775. MR 1053942 (91h:13021)
  • 5. A. Galligo, Some algorithmic questions on ideals of differential operators, EUROCAL' 85, Vol. 2 (Linz, 1985), Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, 1985, pp. 413-421. MR 0826576 (87g:32012)
  • 6. M. Giusti, Some effectivity problems in polynomial ideal theory, EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 159-171. MR 0779123 (86d:12001)
  • 7. D. Grigoriev, Weak Bézout inequality for D-modules, J. Complexity 21 (2005), 532-542. MR 2152720 (2006b:16036)
  • 8. G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), 736-788. MR 1512302
  • 9. M. Janet, 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 1509256
  • 10. H. Li, Noncommutative Gröbner bases and filtered-graded transfer, Lecture Notes in Math., vol. 1795, Springer-Verlag, Berlin, 2002. MR 1947291 (2003i:16065)
  • 11. F. S. Macaulay, Some properties of enumeration in the theory of modular systems, Proc. London Math. Soc. 26 (1927), 531-555.
  • 12. H. Möller and F. Mora, Upper and lower bounds for the degree of Groebner bases, EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 172-183. MR 0779124 (86k:13008)
  • 13. G. Ritter and V. Weispfenning, On the number of term orders, Appl. Algebra Engrg. Comm. Comput. 2 (1991), 55-79. MR 1209244 (94e:06011)
  • 14. F. Schwarz, Janet bases for symmetry groups, Gröbner Bases and Applications (Linz, 1998), London Math. Soc. Lecture Note Ser., vol. 251, Cambridge Univ. Press, Cambridge, 1998, pp. 221-234. MR 1708880 (2002j:35015)
  • 15. C. K. Yap, A new lower bound construction for commutative Thue systems with applications, J. Symbolic Comput. 12 (1991), 1-27. MR 1124303 (92i:03046)

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: https://doi.org/10.1090/S1061-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

American Mathematical Society