Gröbner basis, integration and transcendental functions

ABSTRACT

It is well known that Gröbner basis is a fundamental and powerful tool to solve problems of polynomials ([Buch*],[JSC] etc). Recently, it is revealed that we can use Gröbner basis of Weyl algebra to solve the problems of integrations and formula verifications of transcendental functions ([Zei*], [Tak*], [AZ], [WZ*]). The purpose of the paper is to survey the theory of Gröbner basis of the ring of differential operators and its applications to the following problems: Computation of differential equations for a definite integral with parameters. Zero recognition of an expression that contains special functions or binomial coefficients etc., i.e. formula verification by a computer. Derivations of some of special functions identities. Solving a definite integral or obtaining an asymptotic expansion of a definite integral with parameters.

REFERENCES

• AZ: Almkvist,G., Zeilberger,D., The method of differentiating under the integral sign, preprint, Univ. of Lund, Drexel Univ.
• Bay: David Allen Bayer, The division algorithm and the hilbert scheme, 1982
• Berg: Bergman,G.M., The Diamond Lemma for Ring Theory. Adv. Math., 29 (1978), 178-218.
• Ber: Bernstein, i.N., The analytic continuation of generalized functions with respect to a parameter. Funk. Anal 6(1972), 26-40.
• Bjo: BjSrk, J.E., Rings of Differential Operators. North-Holland, New York, 1979
• Buch0: Buchberger,B., Ein algorithmisches kriterium f/ir die LSsbarkeit eines algebraischen Gleichungssystems. Aeq. Math., 4 (1970), 374-383.
• Buch1: Buchberger,B., Loos,R., Algebraic simplification. Computing. Suppl. 4 (1982), 11-43.
• Buch2: Buchberger,B., An algorithmic method in polynomial idea} theory, N.K. Bose ed., Recent Trends in Multidimensional Systems Theory, D.Reidel Publ. Corp., 1985.
• Cas: Castro,F., Calculs effectifs pour les id~aux d'opdrateurs diffdrentiells, G~omdtrie algdbrique et application III. J.M. Aroca, T. Sancfieg-Giralda, J.L. Vicente eds., Travaux en Coats 24 (1987), 1-19.
• Cav: B. F. Caviness, On Canonical Forms and Simplification, Journal of the ACM (JACM), v.17 n.2, p.385-396, April 1970 [doi>10.1145/321574.321591]
• Che: Chenadec, Canonical Forms in Finitely Presented Algebras, Pitman, 1986.
• FSK: A. Furukawa , T. Sasaki , H. Kobayashi, The Grobner basis of a module over KUX1,...,Xne and polynomial solutions of a system of linear equations, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.222-224, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32483]
• Gal: Galligo, A., Some algorithmic questions on ideals of differential operators. Lect. Note in Comp. Sci., 204(1985), 413-421.
• JSC: J. Symbolic Computation (1988) 6. (Special Issue on Computer and Commutative Algebra)
• Kas: Kashiwara, M., On the holonomic systems of linear differential equations II. Invent. Math. 49(1978), 121-135.
• KMH: Hidetsune Kobayashi , Shuichi Moritsugu , Robert W. Hogan, Solving Systems of Algebraic Equations, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.139-149, July 04-08, 1988
• Mac: Macsyma Reference Manual, Symbolics Inc.
• MM: MSller,H.M., Mora,F., New Constructive Methods in Classical Ideal Theory. J. of Algebra, 100 (1986), 138-178.
• Nou: Noumi, M., Wronskian determinants and the GrSbner representation of a linear differential equation, in Algebraic Analysis. Ed. by M. Kashiwar~, T. Kawai. Academic Press, 1989.
• ST: T. Sasaki , T. Takeshima, A modular method for Gro¨bner-basis construction over Q and solving system of algebraic equations, Journal of Information Processing, v.12 n.4, p.371-379, 1989
• Tak1: Takayama, N., GrSbner basis and the problem of contiguous relation. Japan J. Appl. Math. 6(1989), 147-160.
• Tak2: Takayama, N., An approach to the zero recognition problem by Buchberger algorithm, to appear.
• Tak3: Takayama,N., ODE section algorithm by GrSbner basis (in Japanese). RIMS Kokyuroku, Kyoto Univ. (1989,2), ~-26.
• Tak4: N. Takayama, An algorithm of constructing the integral of a module--an infinite dimensional analog of Gröbner basis, Proceedings of the international symposium on Symbolic and algebraic computation, p.206-211, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96929]
• UT: Tajima, S., Uchida,M., Computation of an integral of deRham system corresponding to a resolution of singularity (in Japanese). RIMS i~okyuroku OO3 (1OS0), 41-68.
• WZ1: Wilf, H.S. and Zeilberger, D., Rational functions certify combinatorial identities, J. of AMS (1990).
• WZ2: Wilf, H.S. and Zeilberger, D., Towards computational proofs of identities, Bull. of AMS (1990).
• Zei1: Zeilberger,D., A holonomic systems approach to special functions identities, to appear, Drexel Univ.
• Zei2: Zeilberger,D. (1989). The method of creative telescoping, to appear, Drexel Univ.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

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

General Terms:
Algorithms, Verification