### DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:**
**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

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.

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