On the complexity of indefinite summation

副标题：

时间：2019-07-17 来源：

题目： On the complexity of indefinite summation

报告人： Eugene Zima (Wilfrid Laurier University, Waterloo, Canada)

时间地点： 2019.07.19 14:30pm N224

摘要： 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.