Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables

Stephen Melczer 1, 2 Bruno Salvy 2
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Analytic combinatorics studies the asymptotic behaviour 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.
Type de document :
Communication dans un congrès
ISSAC 2016, 2016, Waterloo, Canada. ACM, pp.8, 2016, 〈http://www.issac-symposium.org/2016/〉. 〈10.1145/2930889.2930913〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01310691
Contributeur : Bruno Salvy <>
Soumis le : mardi 3 mai 2016 - 08:39:03
Dernière modification le : vendredi 27 avril 2018 - 14:40:07

Lien texte intégral

Identifiants

Collections

Citation

Stephen Melczer, Bruno Salvy. Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables. ISSAC 2016, 2016, Waterloo, Canada. ACM, pp.8, 2016, 〈http://www.issac-symposium.org/2016/〉. 〈10.1145/2930889.2930913〉. 〈hal-01310691〉

Partager

Métriques

Consultations de la notice

124