Efficient rational creative telescoping

We present a new algorithm to compute minimal telescopers for rational functions in two discrete variables. As with recent reduction-based approaches, our algorithm has the important feature that the computation of a telescoper is independent of its certificate. In addition, our algorithm uses a com...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2022-03, Vol.109, p.57-87
Main Authors: Giesbrecht, Mark, Huang, Hui, Labahn, George, Zima, Eugene
Format: Article
Language:English
Subjects:
GGSZ reduction
Left scalar division with remainder
Rational function
Telescoper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a new algorithm to compute minimal telescopers for rational functions in two discrete variables. As with recent reduction-based approaches, our algorithm has the important feature that the computation of a telescoper is independent of its certificate. In addition, our algorithm uses a compact representation of the certificate, which allows it to be easily manipulated and analyzed without knowing the precise expanded form. This representation hides potential expression swell until the final (and optional) expansion, which can be accomplished in time polynomial in the size of the expanded certificate. A complexity analysis, along with a Maple implementation, indicates that our algorithm has better theoretical and practical performance than the reduction-based approach in the rational case.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2021.07.005