Hermite Reduction for D-finite Functions via Integral Bases
Pages 155 - 163
Abstract
Trager’s Hermite reduction solves the integration problem for algebraic functions via integral bases. A generalization of this algorithm to D-finite functions has so far been limited to the Fuchsian case. In the present paper, we remove this restriction and propose a reduction algorithm based on integral bases that is applicable to arbitrary D-finite functions.
References
[1]
[1] https://github.com/LixinDu/HermiteReduction.
[2]
[2] Sergei A Abramov and Mark Van Hoeij. Integration of solutions of linear functional equations. Integral Transforms and Special Functions, 8(1-2):3–12, 1999.
[3]
[3] Shayea Aldossari. Algorithms for Simplifying Differential Equations. 2020. PhD thesis.
[4]
[4] Gert Almkvist and Doron Zeilberger. The method of differentiating under the integral sign. Journal of Symbolic Computation, 10:571–591, 1990.
[5]
[5] Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li. Complexity of creative telescoping for bivariate rational functions. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, page 203–210, New York, NY, USA, 2010. ACM.
[6]
[6] Alin Bostan, Shaoshi Chen, Frédéric Chyzak, Ziming Li, and Guoce Xin. Hermite reduction and creative telescoping for hyperexponential functions. In Proceedings of the 2013 International Symposium on Symbolic and Algebraic Computation, pages 77–84, New York, NY, USA, 2013. ACM.
[7]
[7] Alin Bostan, Frédéric Chyzak, Pierre Lairez, and Bruno Salvy. Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions. In Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation, pages 95–102, New York, NY, USA, 2018. ACM.
[8]
[8] Shaoshi Chen, Lixin Du, and Manuel Kauers. Lazy Hermite reduction and creative telescoping for algebraic functions. In Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, page 75–82, New York, NY, USA, 2021. ACM.
[9]
[9] Shaoshi Chen, Hui Huang, Manuel Kauers, and Ziming Li. A modified Abramov-Petkovsek reduction and creative telescoping for hypergeometric terms. In Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation, pages 117–124, New York, NY, USA, 2015. ACM.
[10]
[10] Shaoshi Chen, Manuel Kauers, and C. Koutschan. Reduction-based creative telescoping for algebraic functions. In Proceedings of the 2016 International Symposium on Symbolic and Algebraic Computation, pages 175–182, New York, NY, USA, 2016. ACM.
[11]
[11] Shaoshi Chen, Mark van Hoeij, Manuel Kauers, and Christoph Koutschan. Reduction-based creative telescoping for fuchsian D-finite functions. Journal of Symbolic Computation, 85:108–127, 2018.
[12]
[12] Frédéric Chyzak. An extension of Zeilberger’s fast algorithm to general holonomic functions. Discrete Mathematics, 217:115–134, 2000.
[13]
[13] Lixin Du. Generalized Integral Bases and Applications in Creative Telescoping. 2022. PhD thesis.
[14]
[14] Erdal Imamoglu. Algorithms for Solving Linear Differential Equations with Rational Function Coefficients. 2017. PhD thesis.
[15]
[15] Erdal Imamoglu and Mark van Hoeij. Computing hypergeometric solutions of second order linear differential equations using quotients of formal solutions and integral bases. Journal of Symbolic Computation, 83:254–271, 2017.
[16]
[16] Edward L. Ince. Ordinary Differential Equations. Dover, 1926.
[17]
[17] Manuel Kauers and Christoph Koutschan. Integral D-finite functions. In Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation, pages 251–258, New York, NY, USA, 2015. ACM.
[18]
[18] Manuel Kauers and Peter Paule. The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Publishing Company, Incorporated, 1st edition, 2011.
[19]
[19] Mikhail Vasil’evich Ostrogradsky. De l’intégration des fractions rationnelles. Bull. de la classe physico-mathématique de l’Acad. Impériale des Sciences de Saint-Pétersbourg, 4:145–167, 286–300, 1845.
[20]
[20] Barry M. Trager. Integration of Algebraic Functions. 1984. PhD thesis.
[21]
[21] Joris van der Hoeven. Constructing reductions for creative telescoping: the general differentially finite case. Applicable Algebra in Engineering, Communication and Computing, 32(5):575–602, nov 2021.
[22]
[22] Doron Zeilberger. A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, 32:321–368, 1990.
Index Terms
- Hermite Reduction for D-finite Functions via Integral Bases
Recommendations
Generalized Hermite Reduction, Creative Telescoping and Definite Integration of D-Finite Functions
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic ComputationHermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to ...
Lazy Hermite Reduction and Creative Telescoping for Algebraic Functions
ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic ComputationBronstein's lazy Hermite reduction is a symbolic integration technique that reduces algebraic functions to integrands with only simple poles without the prior computation of an integral basis. We sharpen the lazy Hermite reduction by combining it with ...
Reduction-based creative telescoping for definite summation of D-finite functions
AbstractCreative telescoping is an algorithmic method initiated by Zeilberger to compute definite sums by synthesizing summands that telescope, called certificates. We describe a creative telescoping algorithm that computes telescopers for definite sums ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
567 pages
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Austrian FWF grants
- CAS Project for Young Scientists in Basic Research
- NSFC grants
- National Key Research and Development Project
- Fund of the Youth Innovation Promotion Association
Conference
ISSAC 2023
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023
July 24 - 27, 2023
Tromsø, Norway
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 150Total Downloads
- Downloads (Last 12 months)115
- Downloads (Last 6 weeks)9
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in