Fast polynomial dispersion computation and its application to indefinite summation
Yiu Kwong Man, Francis J Wright · 1994
An algorithm for computing the dispersion of one or two polynomials is described, based on irreducible factorization. It is demonstrated that in practice it is faster than the “conventional” resultant-based algorithm, at least for small problems. It can be applied to algorithms for indefinite summation and closed-form solution of linear difference equations. A brief survey of existing mostly resultant-based dispersion algorithms is given and the complexity of the resultant involved is analysed. The effectiveness of the proposed algorithm applied to indefinite summation is demonstrated by some examples that are not easily summed by the standard facilities in several computer algebra systems.