Wilf-Zeilberger 理论的算法设计, 复杂度分析及其应用
批准号:
11501552
项目类别:
青年科学基金项目
资助金额:
17.0 万元
负责人:
陈绍示
依托单位:
学科分类:
A0410.算法复杂性与近似算法
结题年份:
2018
批准年份:
2015
项目状态:
已结题
项目参与者:
黄辉、张熠、王杰、杜昊
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
上世纪90年代,组合学家 Wilf和 Zeilberger建立了组合恒等式的机器证明理论,即Wilf-Zeilberger 理论。 该理论现已成为符号计算应用于组合数学,特殊函数论,数学物理等领域的桥梁。邻差算子是 Wilf-Zeilberger 理论的核心概念。与此相关的两个基本问题是:1. 对于给定特殊函数,如何判定邻差算子是否存在,即存在性问题;2. 在邻差算子存在的前提下,如何设计高效算法计算邻差算子,即构造性问题。在双变元情形,上述问题已经得到比较完整的解答。本项目主要针对三元或更多元情形,研究邻差算子的存在性及其构造。其难点是多元函数的符号积分与求和问题。我们计划利用经典的代数曲面理论,以及近年来发展的超指数-超几何项的结构定理与离散留数方法对上述问题展开研究, 并且将研究结果应用于解决计数组合学,统计物理,含参微分方程伽罗瓦理论等领域中一些困难的计算问题。
英文摘要
In the 1990s, combinatorists Wilf and Zeilberger developed an algorithmic proof theory for combinatorial identities, which is called the Wilf-Zeilberger theory. This theory has been the bridge between symbolic computation and other research fields, such as combinatoric, special-function theory, and mathematical physics etc. Telescoper is the core concept of this theory. The two fundamental problems on telescopers are:.1. for a given special function, how to decide the existence of telescopers, i.e., the existence problem;.2. if telescopers exist, how to design efficient algorithms to compute them, i.e., the construction problem..In the bivariate case, these problems have been solved rather satisfactorily. The project mainly concerns the existence of telescopers and their construction in the case of three or more variables. The main challenge in this project is to develop algorithms for symbolic integration and summation for multivariate functions. We plan to apply classical results on algebraic surfaces, and use recent results on the structure.of the hyperexpoential-hypergeometric terms and discrete residues. As applications, we will apply our results to the computational problems in enumerative combinatorics, statistical physics, and the Galois theory of parameterized differential equations.
上世纪90年代初,组合学家Wilf和Zeilberger建立了组合恒等式机器证明的算法理论,即Wilf-Zeilberger 理论。 该理论现已成为符号计算应用于组合数学,特殊函数论,数学物理等领域的桥梁。邻差算子是 Wilf-Zeilberger 理论的核心概念。与此相关的两个基本问题是:1. 对于给定特殊函数,如何判定邻差算子是否存在,即存在性问题;2. 在邻差算子存在的前提下,如何设计高效算法计算邻差算子,即构造性问题。.本项目围绕这两个基本问题开展了系统性的研究。在存在性问题方面,解决了著名的Wilf-Zeilberger猜想,从而给出了判定混合超几何项的完整性的高效算法;首次建立了三变元有理函数的邻差算子存在的判定准则, 解决了Zeilberger算法对此类函数的终止性问题。在构造性问题方面,发展了基于约化的构造代数函数与Fuchsian微分有限函数的邻差算子的高效算法, 并应用于组合恒等式的自动证明与格路计数等问题。微分有限函数是Wilf-Zeilberger理论涉及的一类重要特殊函数。本项目也给出了消去这类函数的伪奇点的随机高效算法,并将Szego型有理性定理从单变元推广到多变元。以上成果得到了国际同行包括美国Rutger大学的Zeilberger教授的肯定。本项目共发表文章11篇,其中符号计算领域最重要期刊Journal of Symbolic Computation发表4篇,符号与代数计算方向权威国际会议ISSAC发表4篇,组合理论最权威期刊Journal of Combinatorial Theory, Series A 发表1篇。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:https://doi.org/10.1016/j.jsc.2018.06.003
发表时间:2019
期刊:Journal of Symbolic Computation
影响因子:--
作者:Shaoshi Chen;ChristophKoutschan
通讯作者:ChristophKoutschan
Power Series with Coefficients from a Finite Set
具有有限集合系数的幂级数
DOI:--
发表时间:2017
期刊:Journal of Combinatorial Theory, Series A
影响因子:--
作者:Jason P. Bell;Shaoshi Chen
通讯作者:Shaoshi Chen
Proof of the Wilf–Zeilberger Conjecture for Mixed Hypergeometric Terms
混合超几何项的威尔夫·蔡尔伯格猜想的证明
DOI:10.1016/j.jsc.2018.06.003
发表时间:2019
期刊:Journal of Symbolic Computation
影响因子:0.7
作者:Shaoshi Chen;ChristophKoutschan
通讯作者:ChristophKoutschan
DOI:10.1016/j.jsc.2017.07.005
发表时间:2016-11
期刊:J. Symb. Comput.
影响因子:--
作者:Shaoshi Chen;M. V. Hoeij;Manuel Kauers;C. Koutschan
通讯作者:Shaoshi Chen;M. V. Hoeij;Manuel Kauers;C. Koutschan
Some Open Problems Related to Creative Telescoping
与创意伸缩相关的一些未决问题
DOI:10.1007/s11424-017-6202-9
发表时间:2017
期刊:Journal of Systems Science and Complexity
影响因子:2.1
作者:Shaoshi Chen;Manuel Kauers
通讯作者:Manuel Kauers
P-递归多项式序列的算术理论、符号算法及其在组合分析中的应用
- 批准号:12271511
- 项目类别:面上项目
- 资助金额:46万元
- 批准年份:2022
- 负责人:陈绍示
- 依托单位:
多变元D-有限幂级数的理论、算法及其在组合分析中的应用
- 批准号:11871067
- 项目类别:面上项目
- 资助金额:53.0万元
- 批准年份:2018
- 负责人:陈绍示
- 依托单位:
国内基金
海外基金















{{item.name}}会员


