网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
科研进展
科研成果
研究专题
获奖
现在位置:首页 > 科研进展 > 科研成果
Wilf-Zeilberger方法研究新进展
【打印】【关闭】

2014-06-30 | 编辑:文\先进制造部

    

 

组合数学随着计算机科学的发展而得到了复兴。算法是计算机科学研究的核心内容。不同算法的效率是由其复杂度来衡量的。在分析算法的复杂度过程中会涉及许多组合数,如二项式系数,Catalan数,Stirling数等,并需要化简或计算这些数的和式与证明各式各样的恒等式。与初等几何定理证明一样,许多传统的证明方法往往具有高度技巧性,不具统一性。计算机科学大师Knuth在其专著《计算机程序设计艺术》中提出了如何设计计算机程序来自动地化简关于二次项系数的和式的问题。这个问题由美国组合学家Wilf和Zeilberger在上世纪90年代的一系列工作中给出了完美的回答,从而建立了组合恒等式机器证明的Wilf-Zeilberger方法。他们也因此项工作获得了1998年美国数学会颁发的Leroy P. Steel奖(授予奠基性研究工作)。Wilf-Zeilberger方法现已成为符号计算应用于组合数学,特殊函数论,数学物理等领域的桥梁,也是吴文俊先生所倡导的数学机械化思想在机器证明方向的成功典范之一。
       Wilf-Zeilberger方法的核心步骤是 Creative Telescoping (见图1), 即对给定的多变元函数 H(n, k), 构造出非平凡的多项式系数的线性微分或差分算子 L(n, Sn) 与满足一定条件的多变元函数 G(n, k) 使得关系式 L(H) = Δk(G)。算子L与函数G分别称为H的Telescoper与Certificate. 该算法已经在主流的计算机代数系统如 Maple与Mathematica中实现并得到广泛应用。从1990年至今,国内外关于该方法的研究主要围绕如下两个问题:1. 给定函数,判定Telescoper是否存在,即存在性问题;2. 如果Telescoper存在,如何设计算法将其构造出来,即构造性问题。在这两个问题上,我们的研究主要争对超指数-超几何函数展开,这类函数是线性微分,差分方程的最基本的闭形式解。
       在存在性问题方面,Zeilberger在1990年证明了一类所谓的完整函数(holonomic functions)总存在Telescoper。但是完整性质只是Telescoper存在的充分条件。事实上,Kauers,陈永川,孙慧等给出了几类非完整但Telescoper仍然存在的函数。在理论上找到判定Telescoper存在的充分必要条件一直是此领域科研前沿的挑战性问题。Abramov在2003年给出了双变元超几何项的Telescoper存在的充分必要条件,并且设计了算法来验证此充要条件。Abramov的判定准则由其学生 Le 推广到了有理q-情形,并且由陈永川,侯庆虎和穆彦平在2005年进一步推广到了一般双变元q-超几何项情形。在2012年,陈绍示和 Singer在基于留数及其离散化概念统一地处理了双变元有理情形的 9 种Telescoper存在性问题。陈绍示及其合作者近期又解决了超指数-超几何混合情形下剩余 6 种Telescoper存在性问题。这些存在性准则使Zeilberger算法关于满足一阶微分或差分方程的函数(即超指数函数,超几何项与超指数-超几何混合项)的终止性问题得到了完全地解决,由此完备了该算法。文章已经被 J. Symbolic Computation 杂志接收,审稿人认为:“The present paper can beconsidered as a keystone that settles all the remaining cases of bivariatehypergeometric telescoping…”。
       在构造性问题方面,他们的研究主要针对计算超指数函数的Telescoper。在1990年,Almkvist与Zeilberger基于微分Gosper算法给出了双变元超指数函数的Telescoper的构造算法。这也是通行商业软件中所用的算法。在2010年,他们基于有理函数积分的Hermite约化方法,提出了计算双变元有理函数的Telescoper的新算法,并且证明了该算法的复杂度比已有的算法低。2013年,他们首先将有理函数的Hermite约化方法推广到了超指数情形。该推广大大提高了超指数函数是否为超指数可积的判定效率。基于推广的Hermite约化算法,他们提出了计算双变元超指数函数Telescoper的高效算法。新算法的最大优点是可以把Telescoper的计算与Certificate的计算分离开来。这在实际应用中非常重要,因为Certificate往往存储空间很大可实际又不需要该信息。通过与商业软件Maple中的程序对比,他们的算法的效率优于经典的Almkvist-Zeilberger算法。论文发表于2013年国际符号计算最权威的会议录 Proc. ISSAC2013。审稿人认为:
“It improves the state of the art in telescoping; the fact that a certificate is no longer needed is an important contribution…”。
       在Wilf-Zeilberger方法的研究中, 已有的高效算法主要是对双变元函数设计的。对于多重积分与求和,高维网格上的行走计数等问题,需要将这些算法推广到多变元情形。另一方面, Zeilberger算法的复杂度估计一直是困难而重要的公开问题。所以建立计算多变元函数的Telescoper的高效算法, 并估计相应算法的复杂度是下一步研究的主要目标。

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn