Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
From MaRDI portal
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.
Recommendations
- Analytic combinatorics in several variables.
- Analytic combinatorics in d variables: an overview
- Combinatorial methods in analysis
- Analytic Combinatorics
- Analytic combinatorics
- scientific article; zbMATH DE number 54350
- An invitation to analytic combinatorics. From one to several variables
- scientific article; zbMATH DE number 4058865
- Factor varieties and symbolic computation
Cited in
(13)- Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
- On the bit complexity of polynomial system solving
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- Diagonal asymptotics for symmetric rational functions via ACSV
- Absolute root separation
- New software for computing asymptotics of multivariate generating functions
- Automatic asymptotics for coefficients of smooth, bivariate rational functions
- Multiple binomial sums
- Linear differential equations as a data structure
- Exact algorithms for linear matrix inequalities
- Stationary points at infinity for analytic combinatorics
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- Symbolic computation, number theory, special functions, physics and combinatorics. Proceedings of the conference, Gainesville, FL, USA, November 11--13, 1999
This page was built for publication: Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985845)
