Modular algorithms for polynomial basis conversion and greatest factorial factorization

Jürgen Gerhard

Abstract. We give new algorithms for converting between representations of polynomials with respect to certain kinds of bases, comprising the usual monomial basis and the falling factorial basis, for fast multiplication and Taylor shift in the falling factorial basis, and for computing the greatest factorial factorization. We analyze both the classical and the new algorithms in terms of arithmetic coefficient operations. For the special case of polynomials with integer coefficients, we present modular variants of these methods and give cost estimates in terms of word operations. Postscript

Fast modular algorithms for squarefree factorization and Hermite integration

Jürgen Gerhard

Abstract. We present new modular algorithms for the squarefree factorization of a primitive polynomial in Z[x] and for computing the rational part of the integral of a rational function in Q[x]. We analyze both algorithms with respect to classical and fast arithmetic and argue that the latter variants are---up to logarithmic factors---asymptotically optimal. Even for classical arithmetic, the integration algorithm is faster than previously known methods. Postscript

High degree solutions of low degree equations

Jürgen Gerhard

Abstract. We exhibit a class of proper hypergeometric expressions which lead to a key equation with coefficients of degree at most two and a unique solution of arbitrarily high degree in Gosper's algorithm from 1978 for indefinite hypergeometric summation. We investigate similar classes for the related problems of indefinite integration and q-hypergeometric summation. Postscript

Author: Jürgen Gerhard, last change: 8 March 2001