Efficient rational creative telescoping (Q820942)

This paper proposes a new (reduction-based) algorithm to compute minimal telescopers of \textit{rational functions in two discrete variables}. Prior to this work, the computation of minimal telescopers was recently dominated by a generation of reduction-based approaches, and were worked out in the differential setting for different classes of univariate functions including: algebraic, fuchsian D-finite, and general D-finite functions. For multivariate rational functions, a type of generalized Hermite reduction (i.e., the Griffith-Dwork method) was used in the differential setting. For the shift setting, a modified version of the Abramov-Petkovšek reduction was applied to hypergeometric terms in two variables. One drawback to these approaches is that the certificates are typically expressed as concatenated summands, which can cause the introduction of unnecessary terms that increase the size of intermediate results. A nice summary (with references) of this previous work on reduction algorithms can be found in [\textit{S. Chen}, in: Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC '19, Beijing, China, July 15--18, 2019. New York, NY: Association for Computing Machinery (ACM). 11--14 (2019; Zbl 1467.33023)]. One underlying aspect of reduction algorithms in the shift case comes from [\textit{J. Gerhard} et al., in: Proceedings of the 2003 international symposium on symbolic and algebraic computation, ISSAC 2003, Philadelphia, PA, USA, August 3--6, 2003. New York, NY: ACM Press. 119--126 (2003; Zbl 1072.68668)] for univariate rational functions, which is based on shiftless decompositions. This can be extended to bivariate rational functions and it is referred to as the GGSZ reduction (so named after its authors), with the advantage that the function decomposes into parts that can be represented compactly. Furthermore, a method of [\textit{H. Q. Le}, Adv. Appl. Math. 30, No. 1--2, 137--159 (2003; Zbl 1048.65026)] enables the construction of telescopers in a direct fashion, independent of the certificate computation. However, only the \(q\)-shift-case for bivariate rational functions was fully worked out. This paper extends the work to the general shift case for bivariate rational functions. Employing the GGSZ reduction and the main idea from Le, the authors were able to avoid the use of algebraic extensions in the base field and intermediate expression swells in the certificate during the process. More precisely, the main algorithm is based on a refined integer-linear decomposition (RILD) of the denominator of a rational function, which enables a (unique) RILD-based partial fraction decomposition of said function. It is noted that an algorithm for computing integer-linear decompositions has already been proposed by the same authors in [\textit{M. Giesbrecht} et al., in: Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC '19, Beijing, China, July 15--18, 2019. New York, NY: Association for Computing Machinery (ACM). 171--178 (2019; Zbl 1467.11123)]. After the decomposition step, GGSZ reduction is applied and the resulting arithmetic is performed directly in the ring of recurrence operators: the problem of constructing a telescoper gets reduced to the problem of computing left scalar remainders of integer-linear operators. In the end, the corresponding certificate can then be expressed using a compact (operator) representation. After stating the main algorithm, the authors introduce a few tweaks which improve overall efficiency. The paper also addresses complexity issues: there is discussion of arithmetic costs of the new algorithm and a review of arithmetic costs of previous reduction-based algorithms. Lastly, the authors provide a helpful preliminary exposition that introduces all of the background and notation for the paper.