(2019.07.19 14:30pm N224)Eugene Zima:On the complexity of indefinite summation

Time:2019-07-17  Source:

Title                 On the complexity of indefinite summation

Speaker           Eugene Zima (Wilfrid Laurier University, Waterloo, Canada)

Time&Venue   2019.07.19  14:30pm  N224

Abstract:           The notion of dispersion plays a crucial role in the development of modern algorithms for indefinite summation. First introduced by Abramov in his classical work as the maximal integer distance between roots of the denominator of a reduced rational function, it has since been a key  notion in several algorithmic developments. For example many summation algorithms have the running time proportional to the dispersion (or square of the dispersion), which can be exponential in the bit size of their input.

We analyze the relation between the value of the dispersion and running time complexity of indefinite summation algorithms for different classes of summands, and show that the dependency of the running time on dispersion is non-essential (i.e. it is a feature of algorithms, not of the summation problems) in many cases. As an example of such behaviour we can mention  the following recent finding: if a non-rational hypergeometric term is summable, then the size of the result is polynomial in the size of the summand and we have an algorithm to find the sum in polynomial (in the input size) time.

This leads to practical improvements of the algorithms for indefinite summation, based on ideas of direct indefinite summation and succinct representation of the factorial polynomials.