Automatically Computing Asymptotics of Sequences with Multivariate Rational Generating Functions
The field of Analytic Combinatorics in Several Variables (ACSV) uses techniques from complex analysis and algebraic geometry to determine the asymptotic behaviour of sequences through their multivariate generating functions. When the generating function is rational, its set of singularities is an algebraic variety, and the geometry of this singular variety heavily influences asymptotics. Under a set of verifiable conditions, asymptotic behaviour for a wide class of sequences with rational generating functions can be determined.
The SageMath package sage-acsv, first released in 2023, rigorously computes dominant asymptotics under a smoothness condition on the singular variety. We present an extension of the package that computes asymptotics of rational generating functions with possibly non-smooth singular varieties. This work uses ACSV techniques and a recent effective algorithm for computing Whitney Stratifications of algebraic varieties. We also present other improvements to the package, including the ability to compute higher order asymptotic terms.
Applications discussed include lattice path enumeration, counting the number of horizontally convex polyominoes, and the DNA sequence alignment problem.