Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Brian Nakamura, Rutgers University, bnaka {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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


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.

See: http://www.math.rutgers.edu/~bnaka/expmath/