Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Accelerating indefinite summation
Speaker: Eugene Zima, Wilfrid Laurier University Waterloo, CANADA
Date: Thursday, November 3, 2011 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Although the algorithmic treatment of symbolic summation has long history, standard algorithms and computer algebra implementations suffer from the fact that they might unnecessarily require running time which is exponential in the input size. Popular example of this kind is an attempt to apply Gosper algorithm to the rational or quasi-rational summand: in such cases running time can be exponential in the input size, even if the result has the size polynomial in the input size. We will present a set of new algorithms that overcomes this long-standing deficiency in the theory and practice of the indefinite summation, in particular new effective rational summation algorithm, based on shiftless factorization of polynomials and synthetic division in the ring of linear difference operators. Similar approach is applied to improve quasi-rational summation algorithms, replacing Gosper algorithm.