Shiftless decomposition and polynomial-time rational summation
Jürgen Gerhard, Mark W. Giesbrecht, Arne Storjohann, Eugene V. Zima · 2003
New algorithms are presented for computing the dispersion set of two polynomials over Q and for shiftless factorization. Together with a summability criterion by Abramov, these are applied to get a polynomial-time algorithm for indefinite rational summation, using a sparse representation of the output.