Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Where is the cheapest equation?
Speaker: Manuel Kauers, Research Institute for Symbolic Computation, J. Kepler University, Linz, Austria
Date: Monday, September 26, 2011, 5:00pm (Note special day!)
ROOM CHANGE: CoRE 431 (DIMACS Seminar Room)
Location: CoRE 431 (DIMACS Seminar Room), Busch Campus, Piscataway, NJ
Abstract:
Zeilberger's celebrated method of creative telescoping computes equations for given definite sums or integrals. These equations are linear recurrence or differential equtions of a certain finite order r with polynomial coefficients of some degree d. For designing efficient summation software, it is useful to know in advance for which pairs (r,d) there will exist a solution of order r and degree d. These pairs (r,d) form a certain region in N^2, whose precise shape was not well understood until now. Together with Shaoshi Chen, we have recently determined a curve which provides a surprisingly accurate description of the boundary of this region. We will not make an attempt at explaining our technical derivation of this curve in the talk, but we will show how its knowledge can be used to determine, for example, the pair (r,d) for which the computational cost is minimal. Perhaps surprisingly, it turns out that this is not the pair where r is minimal.