We present a new algorithm for the computation of the integer-linear decomposition of a multivariate polynomial. Such a decomposition is used in Ore-Sato theory and discrete creative telescoping, for example to detect applicability of Zeilberger's algorithm to a hypergeometric term. Our algorithm is quite straightforward, requiring only basic polynomial arithmetic along with efficient rational root finding. We present complete complexity analyses for both our and previous algorithms in the case of bivariate integer polynomials, and show that our method has a better theoretical performance. We also provide a Maple implementation which shows that our method is faster in practice than previous algorithms.

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

New algorithms are presented for computing the dispersion set of two polynomials over Q and for shiftless factorization. Together with a summability criterion by Abramov, these are applied to get a polynomial-time algorithm for indefinite rational summation, using a sparse representation of the output.

Backward and mixed chains of recurrences are introduced. A complete set of chains of recurrences manipulation tools is described. Applications of these tools, related to the safety and numeric stability of chained computations are given.

In this paper we consider the problem of fast computation of sums of n-ary products of rational numbers, for large n. We present improvements to the standard binary splitting algorithm which are due to numerous factors, including changing the standard arbitrary precision integer representation to one that is more suitable for such computations, unrolling, and chains of recurrences techniques. For the computation of ζ(3) to 640000 decimal digits, we achieve a speedup factor of 2.65 over the standard binary splitting algorithm, which compares favorably to the ideal case in which the numerator and the denominator can be reduced by their greatest common divisor at no cost. If asymptotically fast multiplication is not available (as in the Java Development Kit), a speedup of an order of magnitude is easily obtained.

In this paper we consider the problem of fast computation ofn-ary products, for largen, over arbitrary precision integer or rational number domains. The combination of loop unrolling, chains of recurrences techniques and analogs of binary powering allows us to obtain order-of-magnitude speed improvements for such computations. Three di erent implementations of the technique (in Maple, C++ and Java) are described. Many examples together with timings are given.

A technique to expedite iterative computations which is based on multidimensional chains of recurrences (MCR) is presented.Algorithms for MCR construction, interpretation and MCR-based code generation are discussed.The notion of delayed MCR simpli cation introduced here for the rst time often leads to reduced times for both the MCR construction and MCR interpretation phases of this technique.Three dierent implementations of the MCR technique (in Maple, C and Java) are described.

We propose an algorithm to construct the minimal annihilating operator of a function or a sequence, when the operator is completely factorable (i.e. can be decomposed in first order factors).The algorithm is designed in the frame of the Ore rings theory and can be used in the differentiaf, difference and q-difference cases.We describe also a Maple implement ation of the algorithm.1 Introduction Constructing a linear ordinary differential operator annihilating a function (an annihilator of the function) is necessary when solving many computer algebra problems.We list some of these problems.P1. Expanding a function as a power series and subsequently investigating the expansion.An annihilator lets one construct the recurrence for the series coefficients and manipulate them ([14, 17]). P2.Solving linear inhomogeneous equations.Some methods use annihilators of the right-hand side ([4, 8]).P3. Integrating.If the minimal annihilator L, ord L = n, of j is given, then one can check whether there exists a primitive of ~with an n-th order minimal annihilator.If yes, then it is possible to express the primitive explicitly via f ([91) P4.Recognizing the equivalence of two given functions.If the common annihilator of both the functions is given, then it suffices to check the agreement between the corresponding "initial conditions" (a classical approach).The minimal annihilator, i.e. the annihilator of the lowest order, is the most informative.Note that to solve P3 only the minimal annihilator of j is suitable.Applying algorithm [8] to an equation with a d'Alembertian righthand side guarantees that all d'Alembertian solutions will be found only in the situation when the minimaf annihilator of the right hand side, decomposed in first order factors, is given.(A function is d'Alembertian if it has a completely -Work reported herein was supported in part by RFBR under Grant 95-01-01138.

Let an Ore polynomial ring k[X; a, 6] and a nonzero pseudolinear map 19: K + K, where K is a O, &compatible extension of the field k, be given.Then we have the ring k[O] of op-

The problem of expediting the evaluation of closed-form functions at regular intervals is considered. The Chain of Recurrences technique to expedite computations is extended by rational simplifications and examined as a form of internal representation, oriented towards fast evaluation. Optimizing transformations of Chains of Recurrences are proposed. 1 Introduction A common component in the analysis and solution of many problems, is the iterative evaluation of a function G(x) over a number of points in an interval. More specifically, given a starting point x0 and an increment h, evaluation of the function G(x0 + ih) for i = 0; 1; : : : ; n occurs frequently in applications such as plotting graphs of functions, simulations, and signal processing applications. Straightforward evaluation of functions (especially obtained as the result of symbolic transformations in Computer Algebra Systems) may not be efficient. One way to speed up this process is to compute the function incrementally...

Chains of Recurrences (CR's) are introduced as an effective method to evaluate functions at regular intervals. Algebraic properties of CR's are examined and an algorithm that constructs a CR for a given function is explained. Finally, an implementation of the method in MAXIMA/Common Lisp is discussed.

An important problem of symbolic-numeric interface is the optimization of computations generated by formulae that are obtained in computer algebra system [1]. This problem concerns not only the case of numeric code gen-