×

Complexity of a standard basis of a \(D\)-module. (English. Russian original) Zbl 1206.16050

St. Petersbg. Math. J. 20, No. 5, 709-736 (2009); translation from Algebra Anal. 20, No. 5, 41-82 (2008).
Summary: 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.

MSC:

16Z05 Computational aspects of associative rings (general theory)
16S32 Rings of differential operators (associative algebraic aspects)
32C38 Sheaves of differential operators and their modules, \(D\)-modules
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. A. Bayer, The division algorithm and the Hilbert scheme, Ph.D. Thesis, Harvard, 1982.
[2] A. L. Chistov and D. Yu. Grigor\(^{\prime}\)ev, Complexity of quantifier elimination in the theory of algebraically closed fields, Mathematical foundations of computer science, 1984 (Prague, 1984) Lecture Notes in Comput. Sci., vol. 176, Springer, Berlin, 1984, pp. 17 – 31. · doi:10.1007/BFb0030287
[3] David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. · Zbl 0920.13026
[4] Thomas W. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J. Comput. 19 (1990), no. 4, 750 – 775. · Zbl 0697.68051 · doi:10.1137/0219053
[5] André 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. · doi:10.1007/3-540-15984-3_301
[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. · Zbl 0585.13010 · doi:10.1007/BFb0032839
[7] Dima Grigoriev, Weak Bézout inequality for D-modules, J. Complexity 21 (2005), no. 4, 532 – 542. · Zbl 1080.32010 · doi:10.1016/j.jco.2004.09.006
[8] Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736 – 788 (German). · JFM 52.0127.01 · doi:10.1007/BF01206635
[9] Maurice 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 (French). · JFM 50.0321.03
[10] Huishi Li, Noncommutative Gröbner bases and filtered-graded transfer, Lecture Notes in Mathematics, vol. 1795, Springer-Verlag, Berlin, 2002. · Zbl 1050.16022
[11] F. S. Macaulay, Some properties of enumeration in the theory of modular systems, Proc. London Math. Soc. 26 (1927), 531-555. · JFM 53.0104.01
[12] H. Michael Möller and Ferdinando 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. · Zbl 0564.68030 · doi:10.1007/BFb0032840
[13] Gunter Ritter and Volker Weispfenning, On the number of term orders, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 1, 55 – 79. · Zbl 0739.06008 · doi:10.1007/BF01810855
[14] Fritz 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. · Zbl 1024.34027
[15] Chee-K. Yap, A new lower bound construction for commutative Thue systems with applications, J. Symbolic Comput. 12 (1991), no. 1, 1 – 27. · Zbl 0731.68060 · doi:10.1016/S0747-7171(08)80138-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.