research-article

Bounds for D-finite closure properties

Author:

Manuel KauersAuthors Info & Claims

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Pages 288 - 295

https://doi.org/10.1145/2608628.2608634

Published: 23 July 2014 Publication History

Abstract

We provide bounds on the size of operators obtained by algorithms for executing D-finite closure properties. For operators of small order, we give bounds on the degree and on the height (bit-size). For higher order operators, we give degree bounds that are parameterized with respect to the order and reflect the phenomenon that higher order operators may have lower degrees (order-degree curves).

References

[1]

Alin Bostan, Shaoshi Chen, Frédéric Chyzak, and Ziming Li. Complexity of creative telescoping for bivariate rational functions. In Proceedings of ISSAC'10, pages 203--210, 2010.

Digital Library

[2]

Alin Bostan, Frederic Chyzak, Ziming Li, and Bruno Salvy. Fast computation of common left multiples of linear ordinary differential operators. In Proceedings of ISSAC'12, pages 99--106, 2012.

Digital Library

[3]

Manuel Bronstein and Marko Petkovšek. An introduction to pseudo-linear algebra. Theoretical Computer Science, 157(1):3--33, 1996.

Digital Library

[4]

Shaoshi Chen and Manuel Kauers. Order-degree curves for hypergeometric creative telescoping. In Proceedings of ISSAC'12, pages 122--129, 2012.

Digital Library

[5]

Shaoshi Chen and Manuel Kauers. Trading order for degree in creative telescoping. Journal of Symbolic Computation, 47(8):968--995, 2012.

Digital Library

[6]

Maximilian Jaroschek, Manuel Kauers, Shaoshi Chen, and Michael F. Singer. Desingularization explains order-degree curves for Ore operators. In Manuel Kauers, editor, Proceedings of ISSAC'13, pages 157--164, 2013.

Digital Library

[7]

Manuel Kauers and Peter Paule. The Concrete Tetrahedron. Springer, 2011.

Digital Library

[8]

Manuel Kauers and Lily Yen. On the length of integers in telescopers for proper hypergeometric terms. Journal of Symbolic Computation, 2014. to appear.

[9]

Christoph Koutschan. HolonomicFunctions (User's Guide). Technical Report 10-01, RISC Report Series, University of Linz, Austria, January 2010.

[10]

Christian Mallinger. Algorithmic manipulations and transformations of univariate holonomic functions and sequences. Master's thesis, J. Kepler University, Linz, August 1996.

[11]

Mohamud Mohammed and Doron Zeilberger. Sharp upper bounds for the orders of the recurrences outputted by the Zeilberger and q-Zeilberger algorithms. Journal of Symbolic Computation, 39(2):201--207, 2005.

Digital Library

[12]

Bruno Salvy and Paul Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163--177, 1994.

Digital Library

[13]

Richard P. Stanley. Differentiably finite power series. European Journal of Combinatorics, 1:175--188, 1980.

[14]

Richard P. Stanley. Enumerative Combinatorics, Volume 2. Cambridge Studies in Advanced Mathematics 62. Cambridge University Press, 1999.

Digital Library

[15]

Lily Yen. A two-line algorithm for proving terminating hypergeometric identities. Journal of Mathematical Analysis and Applications, 198(3):856--878, 1996.

Cited By

Kauers MNuspl PPillwein V(2023)Order bounds for C2-finite sequencesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597070(389-397)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597070
Bostan ARivoal TSalvy B(2023)Minimization of differential equations and algebraic values of 𝐸-functionsMathematics of Computation10.1090/mcom/3912Online publication date: 23-Oct-2023
https://doi.org/10.1090/mcom/3912
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
Show More Cited By

Index Terms

Bounds for D-finite closure properties
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Denominator Bounds and Polynomial Solutions for Systems of q-Recurrences over K(t) for Constant K
ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

We consider systems A_l(t) y(q^l t) + ... + A₀(t) y(t) = b(t) of higher order q-recurrence equations with rational coefficients. We extend a method for finding a bound on the maximal power of t in the denominator of arbitrary rational solutions y(t) as ...
Desingularization explains order-degree curves for ore operators
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

Desingularization is the problem of finding a left multiple of a given Ore operator in which some factor of the leading coefficient of the original operator is removed. An order-degree curve for a given Ore operator is a curve in the (r,d)-plane such ...
Effective bounds for P-recursive sequences

We describe an algorithm that takes as input a complex sequence (u"n) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound (v"n) such that |u"n|@?v"n for all n. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

July 2014

444 pages

ISBN:9781450325011

DOI:10.1145/2608628

Editor:
Katsusuke Nabeshima
The University of Tokushima, Japan
,
General Chairs:
Kosaku Nagasaka
Kobe University, Japan
,
Franz Winkler
RISC, University Linz, Austria
,
Program Chair:
Agnes Szanto
North Carolina State University

Copyright © 2014 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]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Austrian Science Fund

Conference

ISSAC '14

ISSAC '14: International Symposium on Symbolic and Algebraic Computation

July 23 - 25, 2014

Kobe, Japan

Acceptance Rates

ISSAC '14 Paper Acceptance Rate 51 of 96 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
58
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kauers MNuspl PPillwein V(2023)Order bounds for C2-finite sequencesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597070(389-397)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597070
Bostan ARivoal TSalvy B(2023)Minimization of differential equations and algebraic values of 𝐸-functionsMathematics of Computation10.1090/mcom/3912Online publication date: 23-Oct-2023
https://doi.org/10.1090/mcom/3912
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
Kauers MKauers M(2023)Background and Fundamental ConceptsD-Finite Functions10.1007/978-3-031-34652-1_1(1-80)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-34652-1_1
Huang HKauers MMukherjee GMaza MZhi L(2022)Order-Degree-Height Surfaces for Linear OperatorsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536187(91-99)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536187
Chen SMaza MZhi L(2022)Stability Problems in Symbolic IntegrationProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535502(517-524)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535502
Nuspl PPillwein V(2022)A Comparison of Algorithms for Proving Positivity of Linearly Recurrent SequencesComputer Algebra in Scientific Computing10.1007/978-3-031-14788-3_15(268-287)Online publication date: 11-Aug-2022
https://doi.org/10.1007/978-3-031-14788-3_15
Show More Cited By

View Options

Get Access

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