Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
From MaRDI portal
Publication:2211202
DOI10.1016/J.JSC.2020.01.001zbMATH Open1458.05263arXiv1905.04187OpenAlexW2944417255WikidataQ126296009 ScholiaQ126296009MaRDI QIDQ2211202FDOQ2211202
Publication date: 13 November 2020
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Abstract: The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables.
Full work available at URL: https://arxiv.org/abs/1905.04187
Recommendations
- Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
- Asymptotics of coefficients of multivariate generating functions: improvements for multiple points
- Automatic asymptotics for coefficients of smooth, bivariate rational functions
- Diagonal asymptotics for symmetric rational functions via ACSV
- Asymptotics of coefficients of algebraic series via embedding into rational series (extended abstract)
asymptotic enumerationanalytic combinatorics in several variablessymbolic-numeric algorithmsKronecker representation
Asymptotic enumeration (05A16) Combinatorial aspects of algebraic geometry (05E14) Geometric aspects of numerical algebraic geometry (14Q65) Computational real algebraic geometry (14Q30)
Cites Work
- NumGfun
- Title not available (Why is that?)
- Title not available (Why is that?)
- Using Algebraic Geometry
- Asymptotics of multivariate sequences. I: Smooth points of the singular variety
- Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
- Title not available (Why is that?)
- Sharp estimates for the arithmetic Nullstellensatz
- Algebraic functions over finite fields
- Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
- Title not available (Why is that?)
- Algorithms in real algebraic geometry
- Solving zero-dimensional systems through the rational univariate representation
- Straight-line programs in geometric elimination theory
- On the complexity of computing with planar algebraic curves
- Central and local limit theorems applied to asymptotic enumeration
- Fast Polynomial Factorization and Modular Composition
- Title not available (Why is that?)
- A Gröbner free alternative for polynomial system solving
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nilpotent connections and the monodromy theorem: Applications of a result of Turrittin
- Analytic combinatorics in several variables.
- Creative telescoping for rational functions using the griffiths
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Separating linear forms and rational univariate representations of bivariate systems
- Computing real roots of real polynomials
- Computing periods of rational integrals
- Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
- Title not available (Why is that?)
- Multiple binomial sums
- Title not available (Why is that?)
- Title not available (Why is that?)
- Gevrey series of arithmetic type. I: Purity and duality theorems
- Title not available (Why is that?)
- Le formalisme du résultant. (The formalism of resultant)
- An asymptotic formula for binomial sums
- On Elementary Methods in Positivity Theory
- Asymptotics of multivariate sequences. III: Quadratic points
- Positivity of Szegö's rational function
- Title not available (Why is that?)
- Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
- Kronecker's and Newton's approaches to solving: a first comparison
- Central and local limit theorems applied to asymptotic enumeration. IV: Multivariate generating functions
- History of Science and Psychology of Invention
- Computing Real Roots of Real Polynomials ... and now For Real!
- Decision Problems for Linear Recurrence Sequences
- Effective asymptotics of linear recurrences with rational coefficients
- Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- Multivariate asymptotics for products of large powers with applications to Lagrange inversion
- Diagonal asymptotics for symmetric rational functions via ACSV
- Automatic asymptotics for coefficients of smooth, bivariate rational functions
- Title not available (Why is that?)
Cited In (3)
Uses Software
This page was built for publication: Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211202)
