Accelerating hypergeometric indefinite summation
Eugene Zima, Wilfrid Laurier University
Date & time: Thursday, 28 October 2021 at 5:00PM - 6:00PM
Abstract: One well-known longstanding problem with Gosperâ€™s algorithm is that its running time depends at least linearly on the dispersion of the rational certificate of the summand, and this last can be exponentially large in the bit size of the summand. This makes summation problems for hypergeometric terms with large dispersion values effectively intractable. We show that for summable terms this dependency is not essential (can be removed). The structure of polynomial solutions to the Gospe key equation is analyzed. A method for rapid extractionsof simple high-degree factors of the solution is given. Resulting modified Gosper's algorithm is presented. This result is based on very simple and well-known facts, properties, and lazy evaluation rules of factorial polynomials. Experimental Maple implementation confirms practical acceleration in computing of indefinite sums and rational normal forms of hypergeometric terms.