Algorithms for Analytic Combinatorics in Several Variables

Abstract

Given a multivariate rational generating function we are interested in computing asymptotic formulas for the sequences encoded by the coefficients. In this thesis we apply the theory of analytic combinatorics in several variables (ACSV) to this problem and build algorithms which seek to compute asymptotic formulas automatically, and to aid in understanding of the theory. Under certain assumptions on a given rational multivariate generating series, we demonstrate two algorithms which compute an asymptotic formula for the coefficients. The first algorithm applies numerical methods for polynomial system solving to compute minimal points which are essential to asymptotics, while the second algorithm leverages the geometry of a so-called height map in two variables to compute asymptotics even in the absence of minimal points. We also provide software for computing gradient flows on the height maps of rational generating functions. These flows are useful for understanding the deformations of integral contours which are present in the analysis of rational generating functions.