research-article

Creative telescoping for rational functions using the griffiths: dwork method

Authors:

Bruno SalvyAuthors Info & Claims

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

Pages 93 - 100

https://doi.org/10.1145/2465506.2465935

Published: 26 June 2013 Publication History

Abstract

Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is single exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.

References

[1]

T. G. Abbott, K. S. Kedlaya, and D. Roe. Bounding Picard numbers of surfaces using p-adic cohomology. In AGCT 2005, volume 21 of Sémin. Congr., pages 125--159. SMF, Paris, 2010.

[2]

M. Apagodu and D. Zeilberger. Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf- Zeilberger theory. Adv. in Appl. Math., 37(2):139--152, 2006.

Digital Library

[3]

A. Bostan, S. Chen, F. Chyzak, and Z. Li. Complexity of creative telescoping for bivariate rational functions. In ISSAC'10, pages 203--210. ACM, 2010.

Digital Library

[4]

S. Chen, M. Kauers, and M. F. Singer. Telescopers for rational and algebraic functions via residues. In ISSAC'12, pages 130--137. ACM, 2012.

Digital Library

[5]

G. Christol. Diagonales de fractions rationnelles et equations différentielles. In Groupe de travail d'analyse ultramétrique, 1982/83, volume 12, issue 2, exp. 18, pages 1--10. Paris, 1984.

[6]

G. Christol. Diagonales de fractions rationnelles et équations de Picard-Fuchs. In Groupe de travail d'analyse ultramétrique, 1984/85, volume 12, issue 1, exp. 13, pages 1--12. Paris, 1985.

[7]

F. Chyzak. An extension of Zeilberger's fast algorithm to general holonomic functions. Disc. Math., 217(1--3):115--134, 2000.

Digital Library

[8]

B. Dwork. On the zeta function of a hypersurface. IHES Publ. Math., (12):5--68, 1962.

[9]

B. Dwork. On the zeta function of a hypersurface. II. Ann. of Math. (2), 80:227--299, 1964.

[10]

J.gathenvon zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, second edition, 2003.

Digital Library

[11]

R. Gerkmann. Relative rigid cohomology and deformation of hypersurfaces. Int. Math. Res. Pap., (1):Art. 3, 1--67, 2007.

[12]

P. A. Griffiths. On the periods of certain rational integrals. I, II. Ann. of Math, 90(3):460--495, 496--541, 1969.

[13]

C.-P. Jeannerod and G. Villard. Essentially optimal computation of the inverse of generic polynomial matrices. J. Complexity, 21(1):72--86, 2005.

Digital Library

[14]

M. Kauers and D. Zeilberger. The computational challenge of enumerating high-dimensional rook walks. Adv. in Appl. Math., 47(4):813--819, 2011.

Digital Library

[15]

C. Koutschan. A fast approach to creative telescoping. Math. Comput. Sci., 4(2--3):259--266, 2010.

[16]

D. Lazard. Algèbre linéaire sur K{X_1,...,X_n}, et élimination. Bull. Soc. Math. France, 105(2):165--190, 1977.

[17]

L. Lipshitz. The diagonal of a D-finite power series is D-finite. J. Algebra, 113(2):373--378, 1988.

[18]

F. S. Macaulay. The algebraic theory of modular systems, volume XXXI of Cambridge Mathematical Library. Cambridge University Press, 1994. Revised reprint of the 1916 original.

[19]

P. Monsky. p-adic analysis and zeta functions, volume 4 of Lectures in Mathematics, Department of Mathematics, Kyoto University. Kinokuniya Book-Store Co. Ltd., Tokyo, 1970.

[20]

D. R. Morrison. Picard-Fuchs equations and mirror maps for hypersurfaces. In Essays on mirror manifolds, pages 241--264. Int. Press, Hong Kong, 1992.

[21]

H. Movasati. Multiple integrals and modular differential equations. IMPA Mathematical Publications. Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 2011.

[22]

S. Pancratz. Computing Gauss-Manin connections for families of projectives hypersurfaces. A thesis submitted for the Transfer of Status, Michaelmas, 2009.

[23]

É. Picard. Quelques remarques sur les intégrales doubles de seconde espèce dans la théorie des surfaces algébriques. C. R. Acad. Sci. Paris, 129:539--540, 1899.

[24]

É. Picard. Sur les périodes des intégrales doubles et sur une classe d'équations différentielles linéaires. C. R. Acad. Sci. Paris, 134:69--71, 1902.

[25]

É. Picard and G. Simart. Théorie des fonctions algébriques de deux variables indépendantes. Gauthier-Villars, 1906. Tome II.

[26]

N. Takayama. An algorithm of constructing the integral of a module -- an infinite dimensional analog of Gröbner basis. In ISSAC'90, pages 206--211. ACM, 1990.

Digital Library

[27]

H. S. Wilf and D. Zeilberger. An algorithmic proof theory for hypergeometric (ordinary and "q") multisum/integral identities. Invent. Math., 108(3):575--633, 1992.

[28]

D. Zeilberger. A holonomic systems approach to special functions identities. J. Comput. Appl. Math., 32(3):321--368, 1990.

Digital Library

[29]

D. Zeilberger. The method of creative telescoping. J. Symb. Comp., 11(3):195--204, 1991.

Digital Library

[30]

W. Zhou. Fast Order Basis and Kernel Basis Computation and Related Problems. PhD thesis, Univ. of Waterloo, 2013.

Cited By

Hassani SMaillard JZenine N(2024)Plea for Diagonals and Telescopers of Rational FunctionsUniverse10.3390/universe1002007110:2(71)Online publication date: 2-Feb-2024
https://doi.org/10.3390/universe10020071
Lairez PPichon-Pharabod EVanhove P(2024)Effective homology and periods of complex projective hypersurfacesMathematics of Computation10.1090/mcom/3947Online publication date: 20-Mar-2024
https://doi.org/10.1090/mcom/3947
Brochet HSalvy B(2024)Reduction-Based Creative Telescoping for Definite Summation of D-finite FunctionsJournal of Symbolic Computation10.1016/j.jsc.2024.102329(102329)Online publication date: Apr-2024
https://doi.org/10.1016/j.jsc.2024.102329
Show More Cited By

Index Terms

Creative telescoping for rational functions using the griffiths: dwork method
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Separability Problems in Creative Telescoping
ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

For given multivariate functions specified by algebraic, differential or difference equations,the separability problem is to decide whether they satisfy linear differential or difference equations in one variable. In this paper, we will explain how ...
Complexity of creative telescoping for bivariate rational functions
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

The long-term goal initiated in this work is to obtain fast algorithms and implementations for definite integration in Almkvist and Zeilberger's framework of (differential) creative telescoping. Our complexity-driven approach is to obtain tight degree ...
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 Computation

Hermite 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

June 2013

400 pages

ISBN:9781450320597

DOI:10.1145/2465506

General Chairs:
Michael Monagan
Simon Fraser University, Burnaby, Canada
,
Gene Cooperman
Northeastern University, Boston, USA
,
Program Chair:
Mark Giesbrecht
University of Waterloo, Waterloo, Canada

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC'13

Sponsor:

SIGSAM

ISSAC'13: International Symposium on Symbolic and Algebraic Computation

June 26 - 29, 2013

Maine, Boston, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
137
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hassani SMaillard JZenine N(2024)Plea for Diagonals and Telescopers of Rational FunctionsUniverse10.3390/universe1002007110:2(71)Online publication date: 2-Feb-2024
https://doi.org/10.3390/universe10020071
Lairez PPichon-Pharabod EVanhove P(2024)Effective homology and periods of complex projective hypersurfacesMathematics of Computation10.1090/mcom/3947Online publication date: 20-Mar-2024
https://doi.org/10.1090/mcom/3947
Brochet HSalvy B(2024)Reduction-Based Creative Telescoping for Definite Summation of D-finite FunctionsJournal of Symbolic Computation10.1016/j.jsc.2024.102329(102329)Online publication date: Apr-2024
https://doi.org/10.1016/j.jsc.2024.102329
Chen SFeng RLi ZSinger MWatt S(2024)Telescopers for differential forms with one parameterSelecta Mathematica10.1007/s00029-024-00926-630:3Online publication date: 9-Mar-2024
https://doi.org/10.1007/s00029-024-00926-6
Bostan ANeiger VYurkevich S(2023)Beating binary powering for polynomial matricesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597118(70-79)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597118
Lairez PVanhove P(2023)Algorithms for minimal Picard–Fuchs operators of Feynman integralsLetters in Mathematical Physics10.1007/s11005-023-01661-3113:2Online publication date: 29-Mar-2023
https://doi.org/10.1007/s11005-023-01661-3
Kauers MKauers M(2023)Summation and IntegrationD-Finite Functions10.1007/978-3-031-34652-1_5(393-509)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-34652-1_5
Kauers MKauers M(2023)OperatorsD-Finite Functions10.1007/978-3-031-34652-1_4(287-391)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-34652-1_4
Kauers MKauers M(2023)The Differential Case in One VariableD-Finite Functions10.1007/978-3-031-34652-1_3(185-286)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-34652-1_3
Kauers MKauers M(2023)The Recurrence Case in One VariableD-Finite Functions10.1007/978-3-031-34652-1_2(81-183)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-34652-1_2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents