Constructing minimal telescopers for rational functions in three discrete variables

DOI10.1016/J.AAM.2022.102389MaRDI QIDQ2168558zbMATH OpenOpenAlexWikidataFDO

Authors Shaoshi Chen, Qing-Hu Hou, Hui Huang, G. Labahn, Rong-Hua Wang

Publication date 31 August 2022

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11614

Abramov reduction creative telescoping symbolic summation

Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30)

Abstract: We present a new algorithm for constructing minimal telescopers for rational functions in three discrete variables. This is the first discrete reduction-based algorithm that goes beyond the bivariate case. The termination of the algorithm is guaranteed by a known existence criterion of telescopers. Our approach has the important feature that it avoids the potentially costly computation of certificates. Computational experiments are also provided so as to illustrate the efficiency of our approach.

Review text

The authors develop a reduction-based creative telescoping algorithm for rational functions in three discrete variables. Such method is able to derive a linear recurrence equation with polynomial coefficients that is satisfied by a given double sum over a trivariate rational function. Its core is a reduction procedure that decomposes a given function into a summable part and a remainder (which is non-summable if it is nonzero). The reason why reduction-based creative telescoping algorithms have been intensively studied in the past few years is the fact that this approach allows one to compute telescopers without having to compute the corresponding certificates, which makes them very interesting from an application point of view. Most of the work so far has been on bivariate problems (i.e., single sums and single integrals), and the present paper is the first attempt on trivariate problems, at least in the discrete (summation) case. The starting point for the algorithm is a reduction method due to Abramov for bivariate rational functions, which the authors extend so that it is applicable in their setting. However, this extended Abramov reduction cannot be used as is, because it lacks an important property: linearity. For constructing telescopers, one has to rely on the fact that the sum of two remainders is again a remainder. This problem is overcome by a process called remainder linearization, which is achieved by choosing a particular representative of the residue class modulo summable rational functions. Now it can be shown that these new remainders behave well with respect to taking linear combinations, which in turn yields the promised reduction-based algorithm to construct telescopers for rational functions in three discrete variables. The termination of the algorithm follows from a previously known existence criterion of telescopers. Several optimizations are described how the efficiency of the basic algorithm can be improved. The paper is concluded by computational experiments carried out in Maple, with an implementation of the algorithm that was produced by the authors themselves. They show an impressive speed-up compared to other computer programs that do not use the reduction-based approach.

Recommendations

Cites work

Cited in

(10)

Describes a project that uses

Uses Software

This page was built for publication: Constructing minimal telescopers for rational functions in three discrete variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168558)