检索结果-内蒙古大学图书馆

24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

作者： Lee, Kisun Melczer, Stephen Smolcic, Josip Univ Calif San Diego Dept Math La Jolla CA 92093 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

ISBN: (纸本)9781665465458

We combine tools from homotopy continuation solvers with the methods of analytic combinatorics in several variables to give the first practical algorithm and implementation for the asymptotics of multivariate rational generating functions not relying on a non-algorithmically checkable 'combinatorial' non-negativity assumption. Our homotopy implementation terminates on examples from the literature in three variables, and we additionally describe heuristic methods that terminate and correctly predict asymptotic behaviour in reasonable time on examples in even higher dimension. Our results are implemented in Julia, through the use of the *** package, and we provide a selection of examples and benchmarks.

关键词： asymptotics analytic combinatorics in several variables homotopy polynomial system

来源：评论

学校读者我要写书评

暂无评论

Symbolic-Numeric Tools for analytic combinatorics in several variables 16

Symbolic-Numeric Tools for Analytic Combinatorics in Several...

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Melczer, Stephen Salvy, Bruno Univ Waterloo Waterloo ON Canada U Lyon UCBL CNRS ENS LyonLIP Waterloo ON Canada U Lyon UCBL CNRS InriaENS LyonLIP Lyon France

ISBN: (纸本)9781450343800

analytic combinatorics studies the asymptotic behavior 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.

关键词： analytic combinatorics in several variables Kronecker Representation Symbolic-Numeric Algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometry of Gradient Flows for analytic combinatorics

Geometry of Gradient Flows for Analytic Combinatorics

引用

作者： Gillen, Stephen University of Pennsylvania

学位级别：Ph.D., Doctor of Philosophy

analytic combinatorics in several variables (ACSV) analyzes the asymptotic growth of generating function coefficients in a direction r. It uses Morse theory on the pole variety V := {H = 0} ⊆ (C∗)d to deform the torus T in the multivariate Cauchy Integral Formula via the downward gradient flow for the log-linear function h = hr = –∑dj=1 rj log |zj|, giving a homology decomposition of T into cycles around critical points of h on V . The deformation can flow to infinity at finite height when the height function is not a proper map. This happens only in the presence of a critical point at infinity (CPAI): a sequence of points on V approaching a point at infinity, and such that log-normals to em>V converge projectively to r. The CPAI is called heighted if the height function also converges to a finite value. The central questions that I have attempted to answer involve analyzing whether all CPAI are heighted, and in which directions CPAI can occur. I attempted to answer these questions by examining sequences converging to faces of the toric compactification defined by a multiple of the Newton polytope P of the polynomial H. The idea is to show that any projective limit of log-normals of a sequence converging to a face F must be parallel to F. This turns out to be true but only under further hypotheses. It implies that CPAI must always be heighted and can only occur in directions parallel to some face of P. The extra hypotheses hold in smooth cases under generically satisfied conditions. In addition, I show under a smoothness condition, that a point in a codimension-1 face F can only be a CPAI for directions parallel to F, and that the directions for a codimension-2 face can be a larger set, which can be computed explicitly and still has positive codimension. The question of whether non-heighted CPAI exist in general is left open; I conjecture that they do not exist.

关键词： ACSV analytic combinatorics in several variables

来源：评论

学校读者我要写书评

暂无评论

Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems

引用

JOURNAL OF SYMBOLIC COMPUTATION 2021年 103卷 234-279页

作者： Melczer, Stephen Salvy, Bruno Univ Penn Dept Math 209 South 33rd St Philadelphia PA 19104 USA Univ Lyon Univ Claude Bernard Lyon 1 ENS Lyon INRIACNRSLIPUMR 5668 Lyon France

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. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： analytic combinatorics in several variables Asymptotic enumeration Kronecker representation Symbolic-numeric algorithms

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Lattice Path Enumeration Using Diagonals

引用

ALGORITHMICA 2016年第4期75卷 782-811页

作者： Melczer, Stephen Mishna, Marni Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Lyon CNRS ENS Lyon INRIAUCBLLab LIP Lyon France Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada

We consider d-dimensional lattice path models restricted to the first orthant whose defining step sets exhibit reflective symmetry across every axis. Given such a model, we provide explicit asymptotic enumerative formulas for the number of walks of a fixed length: the exponential growth is given by the number of distinct steps a model can take, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. The generating function of each model is first expressed as the diagonal of a multivariate rational function, then asymptotic expressions are derived by analyzing the singular variety of this rational function. Additionally, we show how to compute subdominant growth, reflect on the difference between rational diagonals and differential equations as data structures for D-finite functions, and show how to determine first order asymptotics for the subset of walks that start and end at the origin.

关键词： Lattice path enumeration D-finite Diagonal analytic combinatorics in several variables Weyl chambers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：