Extension of Algorithms for D-finite functions [DK15]

Project Lead

Project Duration

01/10/2014 - 30/06/2022

Project URL

Go to Website

Publications

2023

[Jimenez Pastor]

An extension of holonomic sequences: $C^2$-finite sequences

A. Jimenez-Pastor, P. Nuspl, V. Pillwein

Journal of Symbolic Computation 116, pp. 400-424. 2023. ISSN: 0747-7171.
[bib]
@article{RISC6636,
author = {A. Jimenez-Pastor and P. Nuspl and V. Pillwein},
title = {{An extension of holonomic sequences: $C^2$-finite sequences}},
language = {english},
journal = {Journal of Symbolic Computation},
volume = {116},
pages = {400--424},
isbn_issn = {ISSN: 0747-7171},
year = {2023},
refereed = {yes},
length = {25}
}
[Kauers]

Order bounds for $C^2$-finite sequences

M. Kauers, P. Nuspl, V. Pillwein

In: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, A.Dickenstein, E. Tsigaridas and G. Jeronimo (ed.), ISSAC '23, Tromso{}, Norway , pp. 389-397. July 2023. Association for Computing Machinery, New York, NY, USA, 9798400700392}. [doi]
[bib]
@inproceedings{RISC6751,
author = {M. Kauers and P. Nuspl and V. Pillwein},
title = {{Order bounds for $C^2$-finite sequences}},
booktitle = {{Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation}},
language = {english},
abstract = {A sequence is called $C$-finite if it satisfies a linear recurrence with constant coefficients. We study sequences which satisfy a linear recurrence with $C$-finite coefficients. Recently, it was shown that such $C^2$-finite sequences satisfy similar closure properties as $C$-finite sequences. In particular, they form a difference ring. In this paper we present new techniques for performing these closure properties of $C^2$-finite sequences. These methods also allow us to derive order bounds which were not known before. Additionally, they provide more insight in the effectiveness of these computations. The results are based on the exponent lattice of algebraic numbers. We present an iterative algorithm which can be used to compute bases of such lattices.},
series = {ISSAC '23, Tromso{}, Norway},
pages = {389--397},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn_issn = {9798400700392}},
year = {2023},
month = {July},
editor = {A.Dickenstein and E. Tsigaridas and G. Jeronimo},
refereed = {no},
keywords = {Difference equations, holonomic sequences, closure properties, algorithms},
length = {9},
url = {https://doi.org/10.35011/risc.23-03}
}
[Nuspl]

Algorithms for linear recurrence sequences

P. Nuspl

Johannes Kepler University Linz. PhD Thesis. 2023. [pdf]
[bib]
@phdthesis{RISC6711,
author = {P. Nuspl},
title = {{Algorithms for linear recurrence sequences}},
language = {english},
year = {2023},
translation = {0},
school = {Johannes Kepler University Linz},
length = {129}
}

2022

[Nuspl]

Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite Sequences

P. Nuspl, V. Pillwein

Technical report no. 22-02 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). February 2022. Licensed under CC BY 4.0 International. [doi] [pdf]
[bib]
@techreport{RISC6479,
author = {P. Nuspl and V. Pillwein},
title = {{Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite Sequences}},
language = {english},
abstract = {The class of $C^2$-finite sequences is a natural generalization of holonomic sequences and consists of sequences satisfying a linear recurrence with C-finite coefficients, i.e., coefficients satisfying a linear recurrence with constant coefficients themselves. Recently, we investigated computational properties of $C^2$-finite sequences: we showed that these sequences form a difference ring and provided methods to compute in this ring.From an algorithmic point of view, some of these results were not as far reaching as we hoped for. In this paper, we define the class of simple $C^2$-finite sequences and show that it satisfies the same computational properties, but does not share the same technical issues. In particular, we are able to derive bounds for the asymptotic behavior, can compute closure properties more efficiently, and have a characterization via the generating function.},
number = {22-02},
year = {2022},
month = {February},
keywords = {difference equations, holonomic sequences, closure properties, generating functions, algorithms},
length = {16},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
[Nuspl]

$C$-finite and $C^2$-finite Sequences in SageMath

P. Nuspl

Technical report no. 22-06 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). June 2022. Licensed under CC BY 4.0 International. [doi] [pdf]
[bib]
@techreport{RISC6516,
author = {P. Nuspl},
title = {{$C$-finite and $C^2$-finite Sequences in SageMath}},
language = {english},
abstract = {We present the SageMath package rec_sequences which provides methods to compute with sequences satisfying linear recurrences. The package can be used to show inequalities of $C$-finite sequences, i.e., sequences satisfying a linear recurrence relation with constant coefficients. Furthermore, it provides functionality to compute in the $C^2$-finite sequence ring, i.e., to compute closure properties of sequences satisfying a linear recurrence with $C$-finite coefficients.},
number = {22-06},
year = {2022},
month = {June},
keywords = {Difference equations, Closure properties, Inequalities},
length = {4},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
[Nuspl]

A comparison of algorithms for proving positivity of linearly recurrent sequences

P. Nuspl, V. Pillwein

Technical report no. 22-05 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). May 2022. Licensed under CC BY 4.0 International. [doi] [pdf]
[bib]
@techreport{RISC6514,
author = {P. Nuspl and V. Pillwein},
title = {{A comparison of algorithms for proving positivity of linearly recurrent sequences}},
language = {english},
abstract = {Deciding positivity for recursively defined sequences based on only the recursive description as input is usually a non-trivial task. Even in the case of $C$-finite sequences, i.e., sequences satisfying a linear recurrence with constant coefficients, this is only known to be decidable for orders up to five. In this paper, we discuss several methods for proving positivity of $C$-finite sequences and compare their effectiveness on input from the Online Encyclopedia of Integer Sequences (OEIS).},
number = {22-05},
year = {2022},
month = {May},
keywords = {Difference equations Inequalities Holonomic sequences},
length = {17},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
[Nuspl]

Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite Sequences

P. Nuspl, V. Pillwein

In: ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, Marc Moreno Maza, Lihong Zhi (ed.), pp. 45-53. 2022. Association for Computing Machinery, ISBN: 978-1-4503-8688-3. [doi]
[bib]
@inproceedings{RISC6520,
author = {P. Nuspl and V. Pillwein},
title = {{Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite Sequences}},
booktitle = {{ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation}},
language = {english},
pages = {45--53},
publisher = {Association for Computing Machinery},
isbn_issn = {ISBN: 978-1-4503-8688-3},
year = {2022},
editor = {Marc Moreno Maza and Lihong Zhi},
refereed = {yes},
length = {9},
url = {https://doi.org/10.1145/3476446.3536174}
}
[Nuspl]

A Comparison of Algorithms for Proving Positivity of Linearly Recurrent Sequences

P. Nuspl, V. Pillwein

In: Computer Algebra in Scientific Computing, Boulier, Francois and England, Matthew and Sadykov, Timur M. and Vorozhtsov, Evgenii V. (ed.), Proceedings of CASC 2022, LNCS 13366, pp. 268-287. 2022. Springer International Publishing, ISBN: 978-3-031-14788-3.
[bib]
@inproceedings{RISC6616,
author = {P. Nuspl and V. Pillwein},
title = {{A Comparison of Algorithms for Proving Positivity of Linearly Recurrent Sequences}},
booktitle = {{Computer Algebra in Scientific Computing}},
language = {english},
series = {LNCS},
volume = {13366},
pages = {268--287},
publisher = {Springer International Publishing},
isbn_issn = {ISBN: 978-3-031-14788-3},
year = {2022},
editor = {Boulier and Francois and England and Matthew and Sadykov and Timur M. and Vorozhtsov and Evgenii V.},
refereed = {yes},
length = {20},
conferencename = {CASC 2022}
}

2021

[Jimenez Pastor]

On C2-Finite Sequences

Antonio Jiménez-Pastor, Philipp Nuspl, Veronika Pillwein

In: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation, Frédéric Chyzak, George Labahn (ed.), ISSAC '21 , pp. 217-224. 2021. Association for Computing Machinery, New York, NY, USA, ISBN 9781450383820. [doi]
[bib]
@inproceedings{RISC6348,
author = {Antonio Jiménez-Pastor and Philipp Nuspl and Veronika Pillwein},
title = {{On C2-Finite Sequences}},
booktitle = {{Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation}},
language = {english},
abstract = {Holonomic sequences are widely studied as many objects interesting to mathematiciansand computer scientists are in this class. In the univariate case, these are the sequencessatisfying linear recurrences with polynomial coefficients and also referred to asD-finite sequences. A subclass are C-finite sequences satisfying a linear recurrencewith constant coefficients.We investigate the set of sequences which satisfy linearrecurrence equations with coefficients that are C-finite sequences. These sequencesare a natural generalization of holonomic sequences. In this paper, we show that C2-finitesequences form a difference ring and provide methods to compute in this ring.},
series = {ISSAC '21},
pages = {217--224},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn_issn = {ISBN 9781450383820},
year = {2021},
editor = {Frédéric Chyzak and George Labahn},
refereed = {yes},
keywords = {holonomic sequences, algorithms, closure properties, difference equations},
length = {8},
url = {https://doi.org/10.1145/3452143.3465529}
}
[Jimenez Pastor]

An extension of holonomic sequences: C^2-finite sequences

Antonio Jiménez-Pastor, Philipp Nuspl, Veronika Pillwein

Technical report no. 21-20 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). December 2021. Licensed under CC BY 4.0 International. [doi] [pdf]
[bib]
@techreport{RISC6390,
author = {Antonio Jiménez-Pastor and Philipp Nuspl and Veronika Pillwein},
title = {{An extension of holonomic sequences: C^2-finite sequences}},
language = {english},
abstract = {Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as $D$-finite sequences. A subclass are $C$-finite sequences satisfying a linear recurrence with constant coefficients.We investigate the set of sequences which satisfy linear recurrence equations with coefficients that are $C$-finite sequences. These sequences are a natural generalization of holonomic sequences. In this paper, we show that $C^2$-finite sequences form a difference ring and provide methods to compute in this ring. Furthermore, we provide an analogous construction for $D^2$-finite sequences, i.e., sequences satisfying a linear recurrence with holonomic coefficients. We show that these constructions can be iterated and obtain an increasing chain of difference rings.},
number = {21-20},
year = {2021},
month = {December},
keywords = {Difference equations, holonomic sequences, closure properties, algorithms},
length = {26},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
[Pillwein]

Recursion relations for hp-FEM Element Matrices on quadrilaterals

Haubold Tim, Pillwein Veronika, Beuchler Sven

In: Proceedings in Applied Mathematics and Mechanics (PAMM), Gesellschaft für Angewandte Mathematik und Mechanik (GAMM) (ed.), Proceedings of Special Issue: 91st Annual Meeting of the International Association of Applied Mathematics and Mechanics (GAMM)21/1, pp. e202100200-e2021002. 2021. [doi]
[bib]
@inproceedings{RISC6412,
author = {Haubold Tim and Pillwein Veronika and Beuchler Sven},
title = {{Recursion relations for hp-FEM Element Matrices on quadrilaterals}},
booktitle = {{Proceedings in Applied Mathematics and Mechanics (PAMM)}},
language = {english},
abstract = {Abstract In this paper we consider higher order shape functions for finite elements on quadrilaterals. Using tensor products of suitable Jacobi polynomials, it can be proved that the corresponding mass and stiffness matrices are sparse with respect to polynomial degree p . Due to the orthogonal relations between Jacobi polynomials the exact values of the entries of mass and stiffness matrix can be determined. Using symbolic computation, we can find simple recurrence relations which allow us to compute the remaining nonzero entries in optimal arithmetic complexity. Besides the H1 case also the conformal basis functions for H(Div) and H(Curl) are investigated.},
volume = {21},
number = {1},
pages = {e202100200--e2021002},
isbn_issn = {?},
year = {2021},
editor = {Gesellschaft für Angewandte Mathematik und Mechanik (GAMM)},
refereed = {yes},
length = {2},
conferencename = {Special Issue: 91st Annual Meeting of the International Association of Applied Mathematics and Mechanics (GAMM)},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/pamm.202100200}
}
[Pillwein]

Recursion formulas for integrated products of Jacobi polynomials

Sven Beuchler, Tim Haubold, Veronika Pillwein

arXiv. Technical report, 2021. [url]
[bib]
@techreport{RISC6413,
author = {Sven Beuchler and Tim Haubold and Veronika Pillwein},
title = {{Recursion formulas for integrated products of Jacobi polynomials}},
language = {english},
year = {2021},
institution = {arXiv},
length = {25},
url = {https://arxiv.org/abs/2105.08989}
}

2020

[AUTHOR]

The Sage Package Comb_walks for Walks in the Quarter Plane

Antonio Jiménez-Pastor, Alin Bostan, Frédéric Chyzak, Pierre Lairez

ACM Commun. Comput. Algebra 54(2), pp. 30-38. sep 2020. Association for Computing Machinery, New York, NY, USA, 1932-2240. [doi]
[bib]
@article{RISC6282,
author = {Antonio Jiménez-Pastor and Alin Bostan and Frédéric Chyzak and Pierre Lairez},
title = {{The Sage Package Comb_walks for Walks in the Quarter Plane}},
language = {english},
abstract = {We present in this extended abstract a new software designed to work with generating functions that count walks in the quarter plane. With this software we offer a cohesive package that brings together all the required procedures for manipulating these generating functions, as well as a unified interface to deal with them. We also display results that this package offers on a public webpage.},
journal = {ACM Commun. Comput. Algebra},
volume = {54},
number = {2},
pages = {30--38},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn_issn = {1932-2240},
year = {2020},
month = {sep},
refereed = {yes},
keywords = {Sage, D-algebraic functions, generating functions, elliptic functions, lattice walks},
length = {9},
url = {https://doi.org/10.1145/3427218.3427220}
}
[Jimenez Pastor]

Some structural results on D^n finite functions

A. Jimenez-Pastor, V. Pillwein, M.F. Singer

Advances in Applied Mathematics 117, pp. 0-0. June 2020. Elsevier, 0196-8858. [doi] [pdf]
[bib]
@article{RISC6077,
author = {A. Jimenez-Pastor and V. Pillwein and M.F. Singer},
title = {{Some structural results on D^n finite functions}},
language = {english},
abstract = {D-finite (or holonomic) functions satisfy linear differential equations with polynomial coefficients. They form a large class of functions that appear in many applications in Mathematics or Physics. It is well-known that these functions are closed under certain operations and these closure properties can be executed algorithmically. Recently, the notion of D-finite functions has been generalized to differentially definable or Dn-finite functions. Also these functions are closed under operations such as forming (anti)derivative, addition or multiplication and, again, these can be implemented. In this paper we investigate how Dn-finite functions behave under composition and how they are related to algebraic and differentially algebraic functions.},
journal = {Advances in Applied Mathematics},
volume = {117},
pages = {0--0},
publisher = {Elsevier},
isbn_issn = {0196-8858},
year = {2020},
month = {June},
refereed = {yes},
length = {0},
url = {https://doi.org/10.1016/j.aam.2020.102027}
}
[Jimenez Pastor]

On the exponential generating function of labelled trees

Alin Bostan, Antonio Jiménez-Pastor

Comptes Rendus. Mathématique 358(9-10), pp. 1005-1009. 2020. Académie des sciences, Paris, 1631-0721. [doi]
[bib]
@article{RISC6281,
author = {Alin Bostan and Antonio Jiménez-Pastor},
title = {{On the exponential generating function of labelled trees}},
language = {english},
journal = {Comptes Rendus. Mathématique},
volume = {358},
number = {9-10},
pages = {1005--1009},
publisher = {Académie des sciences, Paris},
isbn_issn = {1631-0721},
year = {2020},
refereed = {yes},
length = {5},
url = {https://doi.org/10.5802/crmath.108}
}
[Jimenez Pastor]

The Sage Package Comb_walks for Walks in the Quarter Plane

Antonio Jiménez-Pastor, Alin Bostan, Frédéric Chyzak, Pierre Lairez

ACM Commun. Comput. Algebra 54(2), pp. 30-38. sep 2020. Association for Computing Machinery, New York, NY, USA, 1932-2240. [doi]
[bib]
@article{RISC6283,
author = {Antonio Jiménez-Pastor and Alin Bostan and Frédéric Chyzak and Pierre Lairez},
title = {{The Sage Package Comb_walks for Walks in the Quarter Plane}},
language = {english},
abstract = {We present in this extended abstract a new software designed to work with generating functions that count walks in the quarter plane. With this software we offer a cohesive package that brings together all the required procedures for manipulating these generating functions, as well as a unified interface to deal with them. We also display results that this package offers on a public webpage.},
journal = {ACM Commun. Comput. Algebra},
volume = {54},
number = {2},
pages = {30--38},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn_issn = {1932-2240},
year = {2020},
month = {sep},
refereed = {yes},
keywords = {Sage, D-algebraic functions, generating functions, elliptic functions, lattice walks},
length = {9},
url = {https://doi.org/10.1145/3427218.3427220}
}
[Pillwein]

A sequence of polynomials generated by a Kapteyn series of the second kind

D. Dominici, V. Pillwein

In: Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra, in Honour of Peter Paule on his 60th Birthday, V. Pillwein and C. Schneider (ed.), Texts and Monographs in Symbolic Computuation, in press , pp. ?-?. 2020. Springer, arXiv:1607.05314 [math.CO]. [url] [pdf]
[bib]
@incollection{RISC6078,
author = {D. Dominici and V. Pillwein},
title = {{A sequence of polynomials generated by a Kapteyn series of the second kind}},
booktitle = {{Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra, in Honour of Peter Paule on his 60th Birthday}},
language = {english},
series = {Texts and Monographs in Symbolic Computuation, in press},
pages = {?--?},
publisher = {Springer},
isbn_issn = {?},
year = {2020},
note = {arXiv:1607.05314 [math.CO]},
editor = {V. Pillwein and C. Schneider},
refereed = {yes},
length = {0},
url = {https://www.dk-compmath.jku.at/publications/dk-reports/2019-05-28/view}
}

2019

[Jimenez Pastor]

A Computable Extension for Holonomic Functions: DD-Finite Functions

Jiménez-Pastor Antonio, Pillwein Veronika

Journal of Symbolic Computation 94, pp. 90-104. September-October 2019. ISSN 0747-7171. [doi]
[bib]
@article{RISC5831,
author = {Jiménez-Pastor Antonio and Pillwein Veronika},
title = {{A Computable Extension for Holonomic Functions: DD-Finite Functions}},
language = {english},
abstract = {Differentiably finite (D-finite) formal power series form a large class of useful functions for which a variety of symbolic algorithms exists. Among these methods are several closure properties that can be carried out automatically. We introduce a natural extension of these functions to a larger class of computable objects for which we prove closure properties. These are again algorithmic. This extension can be iterated constructively preserving the closure properties},
journal = {Journal of Symbolic Computation},
volume = {94},
pages = {90--104},
isbn_issn = {ISSN 0747-7171},
year = {2019},
month = {September-October},
refereed = {yes},
length = {15},
url = {https://doi.org/10.1016/j.jsc.2018.07.002}
}

2018

[Jimenez Pastor]

Algorithmic Arithmetics with DD-Finite Functions

Jiménez-Pastor Antonio, Pillwein Veronika

In: Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, Arreche Carlos (ed.), ISSAC '18 , pp. 231-237. 2018. ACM, New York, NY, USA, ISBN 978-1-4503-5550-6. [doi]
[bib]
@inproceedings{RISC5730,
author = {Jiménez-Pastor Antonio and Pillwein Veronika},
title = {{Algorithmic Arithmetics with DD-Finite Functions}},
booktitle = {{Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation}},
language = {english},
series = {ISSAC '18},
pages = {231--237},
publisher = {ACM},
address = {New York, NY, USA},
isbn_issn = {ISBN 978-1-4503-5550-6},
year = {2018},
editor = {Arreche Carlos},
refereed = {yes},
keywords = {algorithms, closure properties, holonomic functions},
length = {7},
url = {http://doi.acm.org/10.1145/3208976.3209009}
}
[Pillwein]

Positivity of the Gillis-Reznick-Zeilberger rational function

V. Pillwein

Technical report no. 18-05 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). 2018. [pdf]
[bib]
@techreport{RISC5612,
author = {V. Pillwein},
title = {{Positivity of the Gillis-Reznick-Zeilberger rational function}},
language = {english},
number = {18-05},
year = {2018},
length = {12},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}

Loading…