Efficient algorithms for the symbolic computation of certain contour integrals with one parameter
Algorithmes rapides pour le calcul symbolique de certaines intégrales de contour à paramètre
Résumé
In this thesis, we provide solutions to some symbolic integration problems in computer algebra. The main objective is to effectively and efficiently compute functions that appear as contour integrals depending on one parameter.First, we consider the computation of the integral of a bivariate rational function with regard to one of the variables. The result is then an algebraic function that can be expressed as a sum of residues of the integrand. We design two algorithms that efficiently compute an annihilating polynomial for each residue, and then for their sum, which yields an annihilating polynomial for the integral itself.These algorithms apply almost directly to the computation of an annihilating polynomial for the diagonal of a rational function, that is, the univariate power series obtained from the expansion of a bivariate rational function by only keeping the diagonal coefficients. Indeed, these diagonals can be written as integrals of rational functions. In another application, we give a new algorithm for the Taylor expansion of the generating functions for several families of unidimensional lattice walks. It relies on a fine analysis of the sizes of the algebraic and differential equations satisfied by these generating functions.Secondly, we consider integrals of mixed hypergeometric and hyperexponential terms. In this case, the result is a polynomially recursive sequence. We devise a method to rewrite the various shifts of a given term under a normal form. This allows us to apply the method of reduction-based creative telescoping in order to efficiently compute a recurrence with polynomial coefficients for the integral.
Cette thèse traite de problèmes d'intégration symbolique en calcul formel. L'objectif principal est de mettre au point des algorithmes permettant de calculer rapidement des fonctions qui sont présentées sous la forme d'intégrales de contour dépendant d'un paramètre.On commence par aborder le problème du calcul de l'intégrale d'une fraction rationnelle bivariée par rapport à l'une de ses variables. Le résultat est alors une fonction algébrique qui s'exprime comme une somme de résidus de l'intégrande. On met au point deux algorithmes qui calculent efficacement un polynôme annulateur pour chacun des résidus, et ensuite pour la somme, ce qui donne accès à un polynôme annulateur pour l'intégrale elle-même.Ces algorithmes s'appliquent presque directement au calcul d'un polynôme annulateur pour la diagonale d'une fraction rationnelle bivariée, c'est-à-dire la série univariée obtenue à partir du développement en série d'une fraction rationnelle bivariée en ne gardant que les coefficients diagonaux. En effet, ces diagonales peuvent s'écrire comme des intégrales de fractions rationnelles. Dans une autre application, on donne un nouvel algorithme pour le développement des séries génératrices de plusieurs familles de marches unidimensionnelles sur les entiers. Il repose sur une analyse fine des tailles des équations algébriques et différentielles satisfaites par ces séries.Dans un second temps, on s'intéresse au calcul de l'intégrale d'un terme mixte hypergéométrique et hyperexponentiel. Cette fois-ci le résultat est une suite polynomialement récursive. On élabore une méthode pour mettre sous forme normale les divers décalages d'un terme donné. Ceci permet d'appliquer la méthode du télescopage créatif par réductions pour calculer efficacement une récurrence à coefficients polynomiaux satisfaite par l'intégrale.
Origine : Version validée par le jury (STAR)
Loading...