Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems. (March 2021)

• Record Type: Journal Article
• Authors: Melczer, Stephen; Salvy, Bruno
• Is Part Of: Journal of symbolic computation. Volume 103(2021)
• Page Start: 234
• Page End: 279
• Publication Date: 2021-03
• Subjects: Analytic combinatorics in several variables -- Asymptotic enumeration -- Kronecker representation -- Symbolic-numeric algorithms; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.01.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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.