Computational D-module theory with singular, comparison with other systems and two new algorithms

ABSTRACT

We present the new implementation of core functions for the computational D-module theory. It is realized as a library dmod.lib in the computer algebra system Singular. We show both theoretical advances, such as the LOT and checkRoot algorithms as well as the comparison of our implementation with other packages for D-modules in computer algebra systems kan/sm1, Asir and Macaulay. The comparison indicates, that our implementation is among the fastest ones. With our package we are able to solve several challenges in D-module theory and we demonstrate the answers to these problems.

REFERENCES

• 1: The SymbolicData project, 2000--2008. Available at http://www.SymbolicData.org.
• 2: OpenXM (Open message eXchange for Mathematics). A project to integrate mathematical software systems, 2007. Available at http://www.openxm.org.
• 3: I. N. Bernsteuın. Analytic continuation of generalized functions with respect to a parameter. Funkcional. Anal. i Prilozen., 6(4):26--40, 1972.
• 4: J. Briançon and P. Maisonobe. Remarques sur l'idéal de Bernstein associé à des polynômes. Preprint no. 650, Univ. Nice Sophia-Antipolis, 2002.
• 5: M. Brickenstein. Slimgb: Gröbner Bases with Slim Polynomials. In Rhine Workshop on Computer Algebra, pages 55--66, 2006. Proceedings of RWCA'06, Basel, March 2006.
• 6: F. Castro-Jiménez and J. Ucha-Enr'ıquez. On the computation of Bernstein-Sato ideals. J. Symbolic Computation, 37:629--639, 2004.
• 7: J. Gago-Vargas, M. Hartillo-Hermoso, and J. Ucha-Enr'ıquez. Comparison of theoretical complexities of two methods for computing annihilating ideals of polynomials. J. Symbolic Computation, 40(3):1076--1086, 2005.
• 8: D. Grayson and M. Stillman. Macaulay 2, a software system for research in algebraic geometry, 2005. Available at http://www.math.uiuc.edu/Macaulay2.
• 9: G.-M. Greuel, V. Levandovskyy, and H. Schönemann. Plural. A Singular 3.0 Subsystem for Computations with Non-commutative Polynomial Algebras. Centre for Computer Algebra, University of Kaiserslautern, 2006. Available at http://www.singular.uni-kl.de.
• 10: G.-M. Greuel and G. Pfister. A SINGULAR Introduction to Commutative Algebra. Springer, 2nd edition, 2008.
• 11: G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern, 2005. Available at http://www.singular.uni-kl.de.
• 12: M. Kashiwara. B-functions and holonomic systems. Rationality of roots of B-functions. Invent. Math., 38(1):33--53, 1976/77.
• 13: Viktor Levandovskyy, Intersection of ideals with non-commutative subalgebras, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145805]
• 14: V. Levandovskyy and J. Morales. A Singular 3.0 library for computations with algebraic D-modules dmod.lib, 2008. Available at http://www.singular.uni-kl.de.
• 15: Viktor Levandovskyy , Hans Schönemann, Plural: a computer algebra system for noncommutative polynomial algebras, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.176-183, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860895]
• 16: Anton Leykin, Constructibility of the set of polynomials with a fixed Bernstein-Sato polynonmial: an algorithmic approach, Journal of Symbolic Computation, v.32 n.6, p.663-675, December 2001 [doi>10.1006/jsco.2001.0488]
• 17: J. McConnell and J. Robson. Noncommutative Noetherian rings. With the cooperation of L. W. Small. Graduate Studies in Mathematics. 30. Providence, RI: American Mathematical Society (AMS), 2001.
• 18: H. Nakayama. An Algorithm Computing the Local b Function by an Approximate Division Algorithm in D. Available at http://arxiv.org/abs/math/0606437v1.
• 19: M. Noro. An efficient modular algorithm for computing the global b-function. In A. M. Cohen, editor, Mathematical software. World Scientific, 2002. Proceedings of the 1st international congress on mathematical software, Beijing, China, August 2002.
• 20: M. Noro, T. Shimoyama, and T. Takeshima. Risa/Asir, an open source general computer algebra system, 2006. Available at http://www.math.kobe-u.ac.jp/Asir.
• 21: T. Oaku. Algorithms for the b-function and D-modules associated with a polynomial. J. Pure Appl. Algebra, 117/118:495--518, 1997.
• 22: M. Saito. On microlocal b-function. Bull. Soc. Math. France, 122(2):163--184, 1994.
• 23: M. Saito, B. Sturmfels, and N. Takayama. Gröbner deformations of hypergeometric differential equations, volume 6 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2000.
• 24: N. Takayama. kan/sm1, a Gröbner engine for the ring of differential and difference operators, 2003. Available at http://www.math.kobe-u.ac.jp/KAN.
• 25: Quoc-Nam Tran, A new class of term orders for elimination, Journal of Symbolic Computation, v.42 n.5, p.533-548, May, 2007 [doi>10.1016/j.jsc.2006.08.006]
• 26: H. Tsai and A. Leykin. D-modules package for Macaulay 2 -- algorithms for D-modules, 2006. Available at http://www.ima.umn.edu/ leykin/Dmodules.
• 27: A. N. Varcenko. Asymptotic Hodge structure on vanishing cohomology. Izv. Akad. Nauk SSSR Ser. Mat., 45(3):540--591, 688, 1981.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
D-modules, annihilator, bernstein-sato polynomial, groebner bases, intersection with subalgebra, non-commutative groebner bases, preimage of ideal