International audience

We consider linear recurrences with polynomial coefficients of Poincaré type and with a unique simple dominant eigenvalue. We give an algorithm that proves or disproves positivity of solutions provided the initial conditions satisfy a precisely defined genericity condition. For positive sequences, the algorithm produces a certificate of positivity that is a data-structure for a proof by induction. This induction works by showing that an explicitly computed cone is contracted by the iteration of the recurrence.

A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n , the algorithm uses O ( n 1.43 ) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O ( n 1.63 ) field operations in general, and n 3/2+ o (1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n 5/3+ o (1) operations, while previous ones run in O ( n 2 ) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.

Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.

In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic Combinatorics, as described in the book by Flajolet and Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation. The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected.

Creative telescoping is a powerful computer algebra paradigm-initiated by Doron Zeilberger in the 90's- for dealing with definite integrals and sums with parameters. We address the mixed continuous-discrete case, and focus on the integration of bivariate hypergeometric-hyperexponential terms. We design a new creative telescoping algorithm operating on this class of inputs, based on a Hermite-like reduction procedure. The new algorithm has two nice features: it is efficient and it delivers, for a suitable representation of the input, a minimal-order telescoper. Its analysis reveals tight bounds on the sizes of the telescoper it produces.

Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal---a property governed by inequalities on the moduli of the coordinates---typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the 'combinatorial case') and under regularity conditions, we utilize this Kronecker representation to determine probabilistically the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.

The diagonal of a multivariate power series $F$ is the univariate power series DiagF generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case DiagF is an algebraic function. We propose an algorithm that computes an annihilating polynomial for DiagF. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.

We describe a simple method that produces automatically closed forms for the coefficients of continued fractions expansions of a large number of special functions. The function is specified by a non-linear differential equation and initial conditions. This is used to generate the first few coefficients and from there a conjectured formula. This formula is then proved automatically thanks to a linear recurrence satisfied by some remainder terms. Extensive experiments show that this simple approach and its straightforward generalization to difference and q-difference equations capture a large part of the formulas in the literature on continued fractions.

Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is single exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.

We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyse the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.

We provide algorithms computing power series solutions of a large class of differential or q-differential equations or systems. Their number of arithmetic operations grows linearly with the precision, up to logarithmic terms.

A Chebyshev expansion is a series in the basis of Chebyshev polynomials of the first kind. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a simple view of previous algorithms, analyze their complexity, and design a faster one for large orders.

We extend Zeilberger's approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before.

Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential, ...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.

We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer N (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in N. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree N. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in O(√N log2 N) bit operations; a deterministic one that computes a compact representation of the solution in O(N log3 N) bit operations. Similar speedups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

We investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzero polynomial solutions, the determination of the dimension of the vector space of polynomial solutions, the computation of a basis of this space. Previous algorithms have a bit complexity that is at least quadratic in the largest integer valuation N of formal Laurent series solutions at infinity, even for merely detecting the existence of nonzero polynomial solutions. We give a deterministic algorithm that computes a compact representation of a basis of polynomial solutions in O(Nlog3N) bit operations. We also give a probabilistic algorithm that computes the dimension of the space of polynomial solutions in O(√Nlog2N) bit operations. In general, the integer N is not polynomially bounded in the bit size of the input differential equation. We isolate a class of equations for which detecting nonzero polynomial solutions can be performed in polynomial complexity. We discuss implementation issues and possible extensions.

Differentially finite series are solutions of linear differential equations with polynomial coefficients. P-recursive sequences are solutions of linear recurrences with polynomial coefficients. Corresponding notions are obtained by replacing classical differentiation or difference operators by their q-analogues. All these objects share numerous properties that are described in the framework of D-finiteness. Our aim in this area is to enable computer algebra systems to deal in an algorithmic way with a large number of special functions and sequences. Indeed, it can be estimated that approximately 60% of the functions described in Abramowitz & Stegun's handbook [1] fall into this category, as well as 25% of the sequences in Sloane's encyclopedia [20,21]. In a way, D-finite sequences or series are non-commutative analogues of algebraic numbers: the role of the minimal polynomial is played by a linear operator.Ore [14] described a non-commutative version of Euclidean division and extended Euclid algorithm for these linear operators (known as Ore polynomials). In the same way as in the commutative case, these algorithms make several closure properties effective (see[22]). It follows that identities between these functions or sequences can be proved or computed automatically. Part of the success of the gfun package [17] comes from an implementation of these operations. Another part comes from the possibility of discovering such identities empirically, with Pade-Hermite approximants on power series [2] taking the place of the LLL algorithm on floating-point numbers. The discovery that a series is D-finite is also important from the complexity point of view: several operations can be performed on D-finite series at a lower cost than on arbitrary power series. This includes multiplication, but also evaluation at rational points by binary splitting [4]. A typical application is the numerical evaluation of π in computer algebra systems; we give another one in these proceedings [3]. Also, the local behaviour of solutions of linear differential equations in the neighbourhood of their singularities is well understood [9] and implementations of algorithms computing the corresponding expansions are available [24, 13]. This gives access to the asymptotics of numerous sequences or to analytic proofs that sequences or functions cannot satisfy such equations [10]Results of a more algebraic nature are obtained by differential Galois theory [18, 19], which naturally shares many subroutines with algorithms for D-finite series. The truly spectacular applications of D-finiteness come from the multivariate case: instead of series or sequences, one works with multivariate series or sequences, or with sequences of series or polynomials,.... They obey systems of linear operators that may be of differential, difference, q-difference or mixed types, with the extra constraint that a finite number of initial conditions are sufficient to specify the solution. This is a non-commutative analogue of polynomial systems with a finite number of solutions. It turns out that, as in the polynomial case, Grobner bases give algorithmic answers to many decision questions, by providing normal forms in a finite dimensional vector space. This has been observed first in the differential case [11, 23] and then extended to the more general multivariate Ore case [8]. A crucial insight of Zeilberger [27, 15] is that elimination in this non-commutative setting computes definite integrals or sums. This is known as creative telescoping. In thehypergeometric setting (when the quotient is a vector space of dimension1), a fast algorithm for this operation is known as Zeilberger's fast algorithm [26]. In the more general case, Grobner bases are of help in this elimination. This is true in the differential case [16, 25] and to a large extent in the more general multivariate case [8]. Also, Zeilberger's fast algorithm has been generalized to the multivariate Ore case by Chyzak [5, 6]. Still, various efficiency issues remain and phenomena of non-minimality of the eliminated operators are not completely understood. A further generalization of D-finite series is due to Gessel [12] who developed a theory of symmetric series. These series are such than when all but a finite number of their variables (in a certain basis) are specialized to0, the resulting series is D-finite in the previous sense. Closure properties under scalar product lead to proofs of D-finiteness (in the classical sense) for various combinatorial sequences. Again, algorithms based on Grobner bases make these operations effective [7]. The talk will survey the nicest of these algorithms and their applications. I will also indicate where current work is in progress, or where more work is needed.

Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

We present our on-going work on the automatic generation of an encyclopedia of special functions on the web, called The Encyclopedia of Special Functions (ESF)footnoteurlhttp://algo.inria.fr/esf. All mathematical formulæ in the ESF are computed, typeset and displayed without any human intervention. This is achieved by exploiting a collection of computer algebra algorithms in a systematic way, on top of a specially designed data structure for a class of special functions.

We give an algorithm to compute asymptotic expansions of exp-log functions.This algorithm automatically computes the necessary asymptotic scale and does not suffer from problems of indefinite cancellation.In particular, an asymptotic equivalent can always be computed for a given exp-log function.

We describe the GFUN package which contains functions for manipulating sequences, linear recurrences, or differential equations and generating functions of various types. This article is intended both as an elementary introduction to the subject and as a reference manual for the package.

We describe a rational algorithm that computes the full partial fraction expansion of a rational function over the algebraic closure of its field of definition. The algorithm uses only gcd operations over the initial field but the resulting decomposition is expressed with linear denominators. We give examples from its Axiom and Maple implementations. Introduction The partial fraction decomposition of a rational function is a form where both the local and global behaviour of the function are easy to find. This is used when computing a primitive by hand, or any linear operation which is most easily done on a pole. An example is the efficient computation of asymptotic expansion of the solutions of a linear recurrence with constant coefficients [4]. Let f = A=D be a rational function in some field K(z). By the fundamental theorem of algebra, it is clear that f admits a partial fraction decomposition of the form f = P + X D(ff)=0 n ff X i=1 b ff;i (z \\Gamma ff) i ; (1) where P is...

Hypergeometric sequences are such that the quotient of two successive terms is a fixed rational function of the index. We give a generalization of M. Petkovsek's algorithm to find all hypergeometric sequence solutions of linear recurrences, and we describe a program to find all hypergeometric functions that solve a linear differential equation. Solutions hyperg'eom'etriques des 'equations diff'erentielles lin'eaires R'esum'e Les suites hyperg'eom'etriques sont telles que le quotient de deux termes cons'ecutifs est une fonction rationnelle fixe de l'indice. Nous donnons une g'en'eralisation de l'algorithme de M. Petkovsek qui d'etermine toutes les solutions hyperg'eom'etriques de r'ecurrences lin'eaires, et nous d'ecrivons un programme qui donne toutes les fonctions hyperg'eom'etriques solutions d"equations diff'erentielles lin'eaires. To appear in Proceedings ISSAC'93. M. Bronstein ed. ACM Press. Finding All Hypergeometric Solutions of Linear Differential Equations Marko Petkovsek ...

We study the automatic computation of asymptotic expansions of functional inverses. Based on previous work on asymptotic expansions, we give an algorithm which computes Hardy-field solutions of equations f(y) = x, with f belonging to a large class of functions.