Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Bruno Salvy Connect in order to contact the contributor
Submitted on : Tuesday, May 3, 2016 - 8:39:03 AM
Last modification on : Monday, May 16, 2022 - 4:58:02 PM

Links full text




Stephen Melczer, Bruno Salvy. Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables. ISSAC 2016, 2016, Waterloo, Canada. pp.8, ⟨10.1145/2930889.2930913⟩. ⟨hal-01310691⟩



Record views