Fast polynomial dispersion computation and its application to indefinite summation

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.

REFERENCES

• 1: Abramov, S. A. (1971) On the summation of rational functions. USSR Comp. Maths. Math. Phys. 11, 324- 330.
• 2: S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients, USSR Computational Mathematics and Mathematical Physics, v.29 n.6, p.7-12, 1989 [doi>10.1016/S0041-5553(89)80002-3]
• 3: B. Buchberger , George E. Collins , Rudiger Loos , Rudolf Albrecht, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 4: Cox, D., Little, J., O'Shea, D. (1992) Ideals, Varieties, and Algorithms: an introduction to computational algebraic geometry and commutative algebra. New York: Springer Verlag.
• 5: J. H. Davenport , Y. Siret , E. Tournier, Computer algebra: systems and algorithms for algebraic computation, Academic Press Ltd., London, UK, 1988
• 6: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 7: Gosper, R. W. (1978) Decision procedure for indefinite hypergeometric summation. Proc. Nat. A cad. Sci. USA. 75/1, 40-42.
• 8: Kaltofen, E. (1983) Factorization of polynomials. In {3}.
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: Lafon, J. C. (1983) Summation in finite terms. In {3}.
• 11: Loos, R. (1983) Computing rational zeros of integral polynomials by p-adic expansion. SIAM J. Computing. 12, 286-293.
• 12: Malcolm A. H. MacCallum , Francis J. Wright, Algebraic computing with REDUCE, Oxford University Press, Inc., New York, NY, 1992
• 13: Yiu-Kwong Man, On computing closed forms for indefinite summations, Journal of Symbolic Computation, v.16 n.4, p.355-376, Oct. 1993 [doi>10.1006/jsco.1993.1053]
• 14: Mignotte, M. (1983) Some useful bounds. In {3}.
• 15: David Rea Musser, Algorithms for polynomial factorization., 1971
• 16: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 17: Paule, P. (1993) Greatest factorial factorization and symbolic summation i. RISC-Linz report series 93-02.
• 18: Pirastu, R. (1992) Algorithmen zur Summation ra. tionaler Funktionen, Diploma Thesis, Universit~t Erlangen-Nfirnberg (in German).
• 19: Mary Shaw , J. F. Traub, On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives, Journal of the ACM (JACM), v.21 n.1, p.161-167, Jan. 1974 [doi>10.1145/321796.321810]
• 20: Doron Zeilberger, The method of creative telescoping, Journal of Symbolic Computation, v.11 n.3, p.195-204, March 1991 [doi>10.1016/S0747-7171(08)80044-2]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

          Nouns: REDUCE

General Terms:
Algorithms, Languages, Performance, Verification