Fast algorithms for Taylor shifts and certain difference equations
Joachim von zur Gathen, Jürgen Gerhard · 1997
We analyze six algorithms for computing integral Taylor shifts for polynomials with integral coefficients.We present and analyze a new algorithm for solving the "key equation" which occurs in many rational and hypergeometric summation algorithms.In a special case, our algorithm is asymp totically faster than previously known methods.We give experimental results for our algorithms.