Fast polynomial dispersion computation and its application to indefinite summation

Yiu Kwong MAN, Francis J. WRIGHT

Research output: Chapter in Book/Report/Conference proceedingChapter

17 Citations (Scopus)

Abstract

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. Copyright © 1994 ACM.
Original languageEnglish
Title of host publicationISSAC '94: Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation
Place of PublicationOxford
PublisherACM
Pages175-180
ISBN (Print)0897916387
DOIs
Publication statusPublished - 1994

Fingerprint

Polynomials
Difference equations
Factorization
Algebra

Citation

Man, Y.-K., & Wright, F .J. (1994). Fast polynomial dispersion computation and its application to indefinite summation. In ISSAC '94: Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation (pp. 175-180). Oxford: ACM.