Advanced applications of the holonomic systems approach
Advanced applications of the holonomic systems approach
复制标题
DOI：
10.1145/1823931.1823954
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
C. Koutschan
中科院分区：
文献类型：
--
作者：
C. Koutschan
完整系统方法由Doron Zeilberger在20世纪90年代初提出。为完整函数恒等式的算法处理奠定了基础。后来，frimac Chyzak扩展了这个框架，引入了与之密切相关的∂-finite函数的概念，并将它们的操作置于坚实的算法基础上。为了实际目的，利用这两个概念是很方便的，这不是太多的限制：完整函数和∂-finite函数类包含许多初等函数（如有理函数，代数函数，对数，指数，正弦函数等）以及许多特殊函数（如经典正交多项式，椭圆积分，Airy，贝塞尔和开尔文函数等）。简而言之，它是由可以用足够多的偏微分方程和差分方程来表征的函数组成的，这些方程既有线性的，也有多项式系数的。一个重要的组成部分是能够以算法方式执行闭包属性，例如加法、乘法和某些替换。但核心技术被称为创造性伸缩，它允许以完全自动化的方式处理求和和集成问题。本论文的一部分是我们的Mathematica软件包HolonomicFunctions，其中实现了上述算法，包括更基本的功能，如非交换算子代数，Gröbner基的计算，线性微分或差分方程参数化系统的有理解。除了像证明特殊函数恒等式这样的标准应用之外，本文的重点是三个高级应用，它们本身以及它们的计算挑战都很有趣。首先，我们将Takayama的算法翻译到一个新的环境中，以便将其应用于一个开放问题，即Ira Gessel的晶格路径猜想的证明。完成证明的计算是非常大的，并且已经用我们的软件完成了。其次，研究有限元方法中的基函数，我们能够扩展现有的算法，从而使我们能够推导出各种关系，这些关系在随后的数值模拟中产生了相当大的加速，在这种情况下，是电磁波的传播。第三个应用涉及完全对称平面分区的枚举公式的计算机证明，也称为Stembridge定理。为了使基础计算可行，我们采用了一种新的方法来寻找创造性的伸缩算子。
The holonomic systems approach was proposed in the early 1990s by Doron Zeilberger. It laid a foundation for the algorithmic treatment of holonomic function identities. Frédéric Chyzak later extended this framework by introducing the closely related notion of ∂-finite functions and by placing their manipulation on solid algorithmic grounds. For practical purposes it is convenient to take advantage of both concepts which is not too much of a restriction: The class of functions that are holonomic and ∂-finite contains many elementary functions (such as rational functions, algebraic functions, logarithms, exponentials, sine function, etc.) as well as a multitude of special functions (like classical orthogonal polynomials, elliptic integrals, Airy, Bessel, and Kelvin functions, etc.). In short, it is composed of functions that can be characterized by sufficiently many partial differential and difference equations, both linear and with polynomial coefficients. An important ingredient is the ability to execute closure properties algorithmically, for example addition, multiplication, and certain substitutions. But the central technique is called creative telescoping which allows to deal with summation and integration problems in a completely automatized fashion. Part of this thesis is our Mathematica package HolonomicFunctions in which the above mentioned algorithms are implemented, including more basic functionality such as noncommutative operator algebras, the computation of Gröbner bases in them, and finding rational solutions of parameterized systems of linear differential or difference equations. Besides standard applications like proving special function identities, the focus of this thesis is on three advanced applications that are interesting in their own right as well as for their computational challenge. First, we contributed to translating Takayama's algorithm into a new context, in order to apply it to an until then open problem, the proof of Ira Gessel's lattice path conjecture. The computations that completed the proof were of a nontrivial size and have been performed with our software. Second, investigating basis functions in finite element methods, we were able to extend the existing algorithms in a way that allowed us to derive various relations which generated a considerable speed-up in the subsequent numerical simulations, in this case of the propagation of electromagnetic waves. The third application concerns a computer proof of the enumeration formula for totally symmetric plane partitions, also known as Stembridge's theorem. To make the underlying computations feasible we employed a new approach for finding creative telescoping operators.