m-fold Hypergeometric Solutions of Linear Recurrence Equations Revisited
Abstract
We present two algorithms to compute m-fold hypergeometric solutions of linear recurrence equations for the classical shift case and for the q-case, respectively. The first being an m-fold generalization and q-generalization of the algorithm by van Hoeij (1998a), Cluzeau and van Hoeij (2005) for recurrence equations. The latter is a combination of an improved version of the algorithms by Petkovsek (1992), Abramov et al. (1998) for recurrence and q-recurrence equations and the m-fold algorithm from Petkovsek and Salvy (1993) for recurrence equations. We will refer to the classical algorithms as van Hoeij or Petkovsek respectively.
To formulate our ideas, we first need to introduce an adapted version of an m-fold Newton polygon and its characteristic polynomials for the classical case and q-case, and to prove the important properties in this case. Using the data from the Newton polygon, we are able to present efficient m-fold versions of the van Hoeij and Petkovsek algorithms for the classical shift case and for the q-case, respectively. Furthermore, we show how one can use the Newton polygon and our characteristic polynomials to conclude for which m there could be m-fold hypergeometric solutions at all. Again by using the information obtained from the Newton polygon, the presentation of the q-Petkovsek algorithm can be simplified and streamlined.
Finally, we give timings for the 'classical' q-Petkovsek, our q-van Hoeij and our modified q-Petkovsek algorithm on some classes of problems and we present a Maple implementation of the m-fold algorithms for the q-case.
(jointly with Peter Horn and Wolfram Koepf / to appear in Mathematics in Computer Science)
