St. Petersburg Mathematical Journal

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1547-7371(e) ISSN 1061-0022(p)

Complexity of a standard basis of a -module

Author(s): D. Yu. Grigoriev; 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
Posted: July 21, 2009
Retrieve article in: 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 -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:

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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|