# Fast computer algebra for special functions [START]

### Project Lead

### Project Duration

01/04/2010 - 31/03/2016## Partners

### The Austrian Science Fund (FWF)

## Publications

### 2016

### Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra

#### Manuel Kauers, Peter Paule, Greg Reid

ACM Communications in Computer Algebra 50(Issue 1), pp. 27-34. March 2016. 1932-2240. [pdf]@

author = {Manuel Kauers and Peter Paule and Greg Reid},

title = {{Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra}},

language = {english},

journal = {ACM Communications in Computer Algebra},

volume = {50},

number = {Issue 1},

pages = {27--34},

isbn_issn = {1932-2240},

year = {2016},

month = {March},

refereed = {no},

length = {8}

}

**article**{RISC5284,author = {Manuel Kauers and Peter Paule and Greg Reid},

title = {{Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra}},

language = {english},

journal = {ACM Communications in Computer Algebra},

volume = {50},

number = {Issue 1},

pages = {27--34},

isbn_issn = {1932-2240},

year = {2016},

month = {March},

refereed = {no},

length = {8}

}

### 2015

### An Improved Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms

#### Shaoshi Chen, Hui Huang, Manuel Kauers, Ziming Li

arxiv. Technical report no. 1501.04668, 2015. [pdf]@

author = {Shaoshi Chen and Hui Huang and Manuel Kauers and Ziming Li},

title = {{An Improved Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms}},

language = {english},

abstract = { The Abramov-Petkovsek reduction computes an additive decomposition of ahypergeometric term, which extends the functionality of the Gosper algorithmfor indefinite hypergeometric summation. We improve the Abramov-Petkovsekreduction so as to decompose a hypergeometric term as the sum of a summableterm and a non-summable one. The improved reduction does not solve anyauxiliary linear difference equation explicitly. It is also moreefficient thanthe original reduction according to computational experiments.Based on thisreduction, we design a new algorithm to compute minimal telescopers forbivariate hypergeometric terms. The new algorithm can avoid the costlycomputation of certificates.},

number = {1501.04668},

year = {2015},

institution = {arxiv},

length = {8}

}

**techreport**{RISC5102,author = {Shaoshi Chen and Hui Huang and Manuel Kauers and Ziming Li},

title = {{An Improved Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms}},

language = {english},

abstract = { The Abramov-Petkovsek reduction computes an additive decomposition of ahypergeometric term, which extends the functionality of the Gosper algorithmfor indefinite hypergeometric summation. We improve the Abramov-Petkovsekreduction so as to decompose a hypergeometric term as the sum of a summableterm and a non-summable one. The improved reduction does not solve anyauxiliary linear difference equation explicitly. It is also moreefficient thanthe original reduction according to computational experiments.Based on thisreduction, we design a new algorithm to compute minimal telescopers forbivariate hypergeometric terms. The new algorithm can avoid the costlycomputation of certificates.},

number = {1501.04668},

year = {2015},

institution = {arxiv},

length = {8}

}

### Integral D-Finite Functions

#### Manuel Kauers, Christoph Koutschan

arxiv. Technical report no. 1501.03691, 2015. [pdf]@

author = {Manuel Kauers and Christoph Koutschan},

title = {{Integral D-Finite Functions}},

language = {english},

abstract = { We propose a differential analog of the notion of integral closure ofalgebraic function fields. We present an algorithm for computing theintegralclosure of the algebra defined by a linear differential operator. Ouralgorithmis a direct analog of van Hoeij's algorithm for computing integral bases ofalgebraic function fields.},

number = {1501.03691},

year = {2015},

institution = {arxiv},

length = {8}

}

**techreport**{RISC5101,author = {Manuel Kauers and Christoph Koutschan},

title = {{Integral D-Finite Functions}},

language = {english},

abstract = { We propose a differential analog of the notion of integral closure ofalgebraic function fields. We present an algorithm for computing theintegralclosure of the algebra defined by a linear differential operator. Ouralgorithmis a direct analog of van Hoeij's algorithm for computing integral bases ofalgebraic function fields.},

number = {1501.03691},

year = {2015},

institution = {arxiv},

length = {8}

}

### 2014

### Radicals of Ore Polynomials

#### Maximilian Jaroschek

In: Proceedings of EACA 2014, , pp. -. 2014. to appear. [pdf]@

author = {Maximilian Jaroschek},

title = {{Radicals of Ore Polynomials}},

booktitle = {{Proceedings of EACA 2014}},

language = {english},

pages = {--},

isbn_issn = {?},

year = {2014},

note = {to appear},

editor = {?},

refereed = {yes},

length = {4}

}

**inproceedings**{RISC4979,author = {Maximilian Jaroschek},

title = {{Radicals of Ore Polynomials}},

booktitle = {{Proceedings of EACA 2014}},

language = {english},

pages = {--},

isbn_issn = {?},

year = {2014},

note = {to appear},

editor = {?},

refereed = {yes},

length = {4}

}

### Ore Polynomials in Sage

#### Manuel Kauers, Maximilian Jaroschek, Fredrik Johansson

In: Computer Algebra and Polynomials, Jaime Gutierrez, Josef Schicho, Martin Weimann (ed.), Lecture Notes in Computer Science , pp. ?-?. 2014. tba. [pdf] [ps]@

author = {Manuel Kauers and Maximilian Jaroschek and Fredrik Johansson},

title = {{Ore Polynomials in Sage}},

booktitle = {{Computer Algebra and Polynomials}},

language = {english},

abstract = {We present a Sage implementation of Ore algebras. The main features for the mostcommon instances include basic arithmetic and actions; GCRD and LCLM; D-finiteclosure properties; natural transformations between related algebras; guessing;desingularization; solvers for polynomials, rational functions and (generalized)power series. This paper is a tutorial on how to use the package.},

series = {Lecture Notes in Computer Science},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {Jaime Gutierrez and Josef Schicho and Martin Weimann},

refereed = {yes},

length = {17}

}

**inproceedings**{RISC4944,author = {Manuel Kauers and Maximilian Jaroschek and Fredrik Johansson},

title = {{Ore Polynomials in Sage}},

booktitle = {{Computer Algebra and Polynomials}},

language = {english},

abstract = {We present a Sage implementation of Ore algebras. The main features for the mostcommon instances include basic arithmetic and actions; GCRD and LCLM; D-finiteclosure properties; natural transformations between related algebras; guessing;desingularization; solvers for polynomials, rational functions and (generalized)power series. This paper is a tutorial on how to use the package.},

series = {Lecture Notes in Computer Science},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {Jaime Gutierrez and Josef Schicho and Martin Weimann},

refereed = {yes},

length = {17}

}

### Fast and rigorous computation of special functions to high precision

#### F. Johansson

RISC. PhD Thesis. 2014. [pdf]@

author = {F. Johansson},

title = {{Fast and rigorous computation of special functions to high precision}},

language = {english},

year = {2014},

translation = {0},

school = {RISC},

length = {0}

}

**phdthesis**{RISC4972,author = {F. Johansson},

title = {{Fast and rigorous computation of special functions to high precision}},

language = {english},

year = {2014},

translation = {0},

school = {RISC},

length = {0}

}

### Using functional equations to enumerate 1324-avoiding permutations

#### Fredrik Johansson, Brian Nakamura

Advances in Applied Mathematics 56(0), pp. 20 - 34. 2014. ISSN 0196-8858. [url]@

author = {Fredrik Johansson and Brian Nakamura},

title = {{Using functional equations to enumerate 1324-avoiding permutations}},

language = {english},

journal = {Advances in Applied Mathematics},

volume = {56},

number = {0},

pages = {20 -- 34},

isbn_issn = {ISSN 0196-8858},

year = {2014},

refereed = {yes},

keywords = {Enumeration algorithm},

length = {15},

url = {http://www.sciencedirect.com/science/article/pii/S0196885814000256}

}

**article**{RISC4987,author = {Fredrik Johansson and Brian Nakamura},

title = {{Using functional equations to enumerate 1324-avoiding permutations}},

language = {english},

journal = {Advances in Applied Mathematics},

volume = {56},

number = {0},

pages = {20 -- 34},

isbn_issn = {ISSN 0196-8858},

year = {2014},

refereed = {yes},

keywords = {Enumeration algorithm},

length = {15},

url = {http://www.sciencedirect.com/science/article/pii/S0196885814000256}

}

### Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph

#### Manuel Kauers, Ryan ODonnell, Li-Yang Tan, Yuan Zhou

In: Proceedings of SODA'14, tba (ed.), pp. ?-?. 2014. tba. [pdf]@

author = {Manuel Kauers and Ryan ODonnell and Li-Yang Tan and Yuan Zhou},

title = {{Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph}},

booktitle = {{Proceedings of SODA'14}},

language = {english},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {tba},

refereed = {yes},

length = {15}

}

**inproceedings**{RISC4829,author = {Manuel Kauers and Ryan ODonnell and Li-Yang Tan and Yuan Zhou},

title = {{Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph}},

booktitle = {{Proceedings of SODA'14}},

language = {english},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {tba},

refereed = {yes},

length = {15}

}

### On the length of integers in telescopers for proper hypergeometric terms

#### Manuel Kauers, Lily Yen

Journal of Symbolic Computation, pp. ?-?. 2014. ISSN 0747-7171. to appear. [pdf] [ps]@

author = {Manuel Kauers and Lily Yen},

title = {{On the length of integers in telescopers for proper hypergeometric terms}},

language = {english},

journal = {Journal of Symbolic Computation},

pages = {?--?},

isbn_issn = {ISSN 0747-7171},

year = {2014},

note = {to appear},

refereed = {yes},

length = {15}

}

**article**{RISC4955,author = {Manuel Kauers and Lily Yen},

title = {{On the length of integers in telescopers for proper hypergeometric terms}},

language = {english},

journal = {Journal of Symbolic Computation},

pages = {?--?},

isbn_issn = {ISSN 0747-7171},

year = {2014},

note = {to appear},

refereed = {yes},

length = {15}

}

### Computer Algebra

#### Manuel Kauers

In: Handbook of Combinatorics, Miklos Bona (ed.), pp. ?-?. 2014. Taylor and Francis, tba.@

author = {Manuel Kauers},

title = {{Computer Algebra}},

booktitle = {{Handbook of Combinatorics}},

language = {english},

pages = {?--?},

publisher = {Taylor and Francis},

isbn_issn = {tba},

year = {2014},

editor = {Miklos Bona},

refereed = {yes},

length = {59}

}

**incollection**{RISC4956,author = {Manuel Kauers},

title = {{Computer Algebra}},

booktitle = {{Handbook of Combinatorics}},

language = {english},

pages = {?--?},

publisher = {Taylor and Francis},

isbn_issn = {tba},

year = {2014},

editor = {Miklos Bona},

refereed = {yes},

length = {59}

}

### Bounds for D-Finite Closure Properties

#### Manuel Kauers

In: Proceedings of ISSAC 2014, Katsusuke Nabeshima (ed.), pp. 288-295. 2014. isbn 978-1-4503-2501-1/14/07. [pdf]@

author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {288--295},

isbn_issn = {isbn 978-1-4503-2501-1/14/07},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

**inproceedings**{RISC4989,author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {288--295},

isbn_issn = {isbn 978-1-4503-2501-1/14/07},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

### Bounds for D-Finite Closure Properties

#### Manuel Kauers

arxiv. Technical report no. 1408.5514, 2014. [pdf]@

author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

language = {english},

number = {1408.5514},

year = {2014},

institution = {arxiv},

length = {8}

}

**techreport**{RISC5041,author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

language = {english},

number = {1408.5514},

year = {2014},

institution = {arxiv},

length = {8}

}

### Desingularization of Ore Operators

#### Shaoshi Chen, Manuel Kauers, Michael F. Singer

arxiv. Technical report no. 1408.5512, 2014. [pdf]@

author = {Shaoshi Chen and Manuel Kauers and Michael F. Singer},

title = {{Desingularization of Ore Operators}},

language = {english},

number = {1408.5512},

year = {2014},

institution = {arxiv},

length = {11}

}

**techreport**{RISC5042,author = {Shaoshi Chen and Manuel Kauers and Michael F. Singer},

title = {{Desingularization of Ore Operators}},

language = {english},

number = {1408.5512},

year = {2014},

institution = {arxiv},

length = {11}

}

### On 3-dimensional lattice walks confined to the positive octant

#### Alin Bostan, Mireille Bousquet-Mélou, Manuel Kauers, Stephen Melczer

Arxiv. Technical report no. 1409.3669, 2014. [pdf]@

author = {Alin Bostan and Mireille Bousquet-Mélou and Manuel Kauers and Stephen Melczer},

title = {{On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

abstract = {Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in {0,±1}2: the generating function is D-finite if and only if a certain group associated with the step set is finite.We explore in this paper the analogous problem for 3-dimensional walks confined to the positive octant. The first difficulty is their number: there are 11074225 non-trivial and non-equivalent step sets in {0,±1}3 (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps.We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 -- the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases.On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure, which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations.This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear. },

number = {1409.3669},

year = {2014},

institution = {Arxiv},

length = {36}

}

**techreport**{RISC5054,author = {Alin Bostan and Mireille Bousquet-Mélou and Manuel Kauers and Stephen Melczer},

title = {{On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

abstract = {Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in {0,±1}2: the generating function is D-finite if and only if a certain group associated with the step set is finite.We explore in this paper the analogous problem for 3-dimensional walks confined to the positive octant. The first difficulty is their number: there are 11074225 non-trivial and non-equivalent step sets in {0,±1}3 (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps.We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 -- the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases.On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure, which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations.This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear. },

number = {1409.3669},

year = {2014},

institution = {Arxiv},

length = {36}

}

### On 3-dimensional lattice walks confined to the positive octant

#### Alin Bostan, Mireille Bousquet-Melou, Manuel Kauers, Stephen Melczer

Annals of Combinatorics, pp. ??-??. 2014. ISSN 0218-0006. to appear. [pdf]@

author = {Alin Bostan and Mireille Bousquet-Melou and Manuel Kauers and Stephen Melczer},

title = {{ On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

journal = {Annals of Combinatorics},

pages = {??--??},

isbn_issn = {ISSN 0218-0006},

year = {2014},

note = {to appear},

refereed = {yes},

length = {36}

}

**article**{RISC5082,author = {Alin Bostan and Mireille Bousquet-Melou and Manuel Kauers and Stephen Melczer},

title = {{ On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

journal = {Annals of Combinatorics},

pages = {??--??},

isbn_issn = {ISSN 0218-0006},

year = {2014},

note = {to appear},

refereed = {yes},

length = {36}

}

### Relativistic Coulomb Integrals and Zeilberger's Holonomic Systems Approach II

#### Christoph Koutschan, Peter Paule, Sergei K. Suslov

In: Algebraic and Algorithmic Aspects of Differential and Integral Operators, Moulay Barkatou and Thomas Cluzeau and Georg Regensburger and Markus Rosenkranz (ed.), Lecture Notes in Computer Science 8372, pp. 135-145. 2014. Springer, Berlin Heidelberg, ISBN 978-3-642-54478-1. [pdf]@

author = {Christoph Koutschan and Peter Paule and Sergei K. Suslov},

title = {{Relativistic Coulomb Integrals and Zeilberger's Holonomic Systems Approach II}},

booktitle = {{Algebraic and Algorithmic Aspects of Differential and Integral Operators}},

language = {english},

abstract = {We derive the recurrence relations for relativistic Coulomb integrals directly from the integral representations with the help of computer algebra methods. In order to manage the computational complexity of this problem, we employ holonomic closure properties in a sophisticated way.},

series = {Lecture Notes in Computer Science},

volume = {8372},

pages = {135--145},

publisher = {Springer},

address = {Berlin Heidelberg},

isbn_issn = {ISBN 978-3-642-54478-1},

year = {2014},

editor = {Moulay Barkatou and Thomas Cluzeau and Georg Regensburger and Markus Rosenkranz},

refereed = {yes},

length = {11}

}

**incollection**{RISC4847,author = {Christoph Koutschan and Peter Paule and Sergei K. Suslov},

title = {{Relativistic Coulomb Integrals and Zeilberger's Holonomic Systems Approach II}},

booktitle = {{Algebraic and Algorithmic Aspects of Differential and Integral Operators}},

language = {english},

abstract = {We derive the recurrence relations for relativistic Coulomb integrals directly from the integral representations with the help of computer algebra methods. In order to manage the computational complexity of this problem, we employ holonomic closure properties in a sophisticated way.},

series = {Lecture Notes in Computer Science},

volume = {8372},

pages = {135--145},

publisher = {Springer},

address = {Berlin Heidelberg},

isbn_issn = {ISBN 978-3-642-54478-1},

year = {2014},

editor = {Moulay Barkatou and Thomas Cluzeau and Georg Regensburger and Markus Rosenkranz},

refereed = {yes},

length = {11}

}

### A Generalized Apagodu-Zeilberger Algorithm

#### Shaoshi Chen, Manuel Kauers, Christoph Koutschan

In: Proceedings of ISSAC 2014, Katsusuke Nabeshima (ed.), pp. 107-114. 2014. ISBN 978-1-4503-2501-1. [pdf]@

author = {Shaoshi Chen and Manuel Kauers and Christoph Koutschan},

title = {{A Generalized Apagodu-Zeilberger Algorithm}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {107--114},

isbn_issn = {ISBN 978-1-4503-2501-1},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

**inproceedings**{RISC5034,author = {Shaoshi Chen and Manuel Kauers and Christoph Koutschan},

title = {{A Generalized Apagodu-Zeilberger Algorithm}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {107--114},

isbn_issn = {ISBN 978-1-4503-2501-1},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

### Comparison between binary and decimal floating-point numbers

#### Nicolas Brisebarre, Christoph Lauter, Marc Mezzarobba, Jean-Michel Muller

HAL. Technical report no. hal-01021928, 2014. [url]@

author = {Nicolas Brisebarre and Christoph Lauter and Marc Mezzarobba and Jean-Michel Muller},

title = {{Comparison between binary and decimal floating-point numbers}},

language = {english},

number = {hal-01021928},

year = {2014},

institution = {HAL},

length = {13},

url = {http://hal.archives-ouvertes.fr/hal-01021928/}

}

**techreport**{RISC5020,author = {Nicolas Brisebarre and Christoph Lauter and Marc Mezzarobba and Jean-Michel Muller},

title = {{Comparison between binary and decimal floating-point numbers}},

language = {english},

number = {hal-01021928},

year = {2014},

institution = {HAL},

length = {13},

url = {http://hal.archives-ouvertes.fr/hal-01021928/}

}

### Rigorous Uniform Approximation of D-finite Functions Using Chebyshev Expansions

#### Alexandre Benoit, Mioara Joldeș, Marc Mezzarobba

HAL. Technical report no. hal-01022420, 2014. [url]@

author = {Alexandre Benoit and Mioara Joldeș and Marc Mezzarobba},

title = {{Rigorous Uniform Approximation of D-finite Functions Using Chebyshev Expansions}},

language = {english},

number = {hal-01022420},

year = {2014},

institution = {HAL},

length = {39},

url = {http://hal.archives-ouvertes.fr/hal-01022420/}

}

**techreport**{RISC5021,author = {Alexandre Benoit and Mioara Joldeș and Marc Mezzarobba},

title = {{Rigorous Uniform Approximation of D-finite Functions Using Chebyshev Expansions}},

language = {english},

number = {hal-01022420},

year = {2014},

institution = {HAL},

length = {39},

url = {http://hal.archives-ouvertes.fr/hal-01022420/}

}

### 2013

### Formal Laurent Series in Several Variables

#### Ainhoa Aparicio Monforte, Manuel Kauers

Expositiones Mathematicae 31(4), pp. 350-367. 2013. ISSN 0723-0869. [pdf]@

author = {Ainhoa Aparicio Monforte and Manuel Kauers},

title = {{Formal Laurent Series in Several Variables}},

language = {english},

abstract = { We explain the construction of fields of formal infinite series in several variables, generalizing the classical notion of formal Laurent series in one variable. Our discussion addresses the field operations for these series (addition, multiplication, and division), the composition, and includes an implicit function theorem.},

journal = {Expositiones Mathematicae},

volume = {31},

number = {4},

pages = {350--367},

isbn_issn = {ISSN 0723-0869},

year = {2013},

refereed = {yes},

length = {24}

}

**article**{RISC4600,author = {Ainhoa Aparicio Monforte and Manuel Kauers},

title = {{Formal Laurent Series in Several Variables}},

language = {english},

abstract = { We explain the construction of fields of formal infinite series in several variables, generalizing the classical notion of formal Laurent series in one variable. Our discussion addresses the field operations for these series (addition, multiplication, and division), the composition, and includes an implicit function theorem.},

journal = {Expositiones Mathematicae},

volume = {31},

number = {4},

pages = {350--367},

isbn_issn = {ISSN 0723-0869},

year = {2013},

refereed = {yes},

length = {24}

}