设计构造邻差算子的高效算法是Wilf-Zeilberger方法应用于组合恒等式证明，格点路径计数，数学物理中含参积分的计算等问题的关键。Zeilberger算法研究方面最知名的学者M. Kauers教授认为：从1990年至今，邻差算子的构造算法经历了四代的演化。第一代算法是Zeilberger在上世纪90年代初提出的，基本思想是基于微分、差分算子环上的非交换消元。这种方法后来分别由Takayama和Chyzak，Salvy等人利用非交换Groebner基方法得到了改进。在1990年, Zeilberger发现对一类所谓的超几何项可以基于参数化的Gosper算法来“快速”地构造超几何项的邻差算子，这就是第二代算法，后称之Zeilberger（快速）算法。这类快速算法在许多计算机代数系统如MAPLE和MATHEMATICA中得到了实现。在2005年，为了更好的分析已有关于超指数-(q-)超几何项的邻差算子的构造算法的复杂度， Zeilberger与其学生Apagodu提出了基于线性系统求解的算法，即第三代算法。这算法对于分析邻差算子的阶数以及其多项式系数的次数的上界非常有效，但是计算效率欠佳。前三代算法的共同特点是在计算邻差算子的同时不可避免需要计算相伴的验证函数，而该函数一般在存储大小上比邻差算子高出一个量级并且在应用中往往是多余的。一直以来，如何将邻差算子的计算与其相伴验证函数的计算分离开来，是一个很具挑战性且重要的问题。解决这个分离问题的关键是约化算法。第四代算法就是基于约化(reduction-based telescoping) 的构造算法。具体内容如下
1.基于约化的构造有理函数的邻差算子的高效算法
Hermite约化是符号计算中求单变元有理函数的不定积分的基本技巧。在2010年, 先进制造部陈绍士、李子明等科研人员在文章【4】中基于Hermite约化设计了计算双变元有理函数的邻差算子的新算法，并证明了该算法的算术复杂度比已有的算法低。新算法的特点是可以将邻差算子和验证函数的计算分离开，从而在应用问题中效率远优于经典算法。最近他们的工作又由法国巴黎综合理工的Lairez在其博士论文中利用Griffiths-Dwork约化进一步推广到一般多变元情形。这些算法显著提高了经典Zeilberger算法的效率。M. Kauers教授在2015年关于计算机数学的暑期学校的系列报告中指出，第四代算法的奠基性工作开始于文章【4】。论文的评审意见指出“This is a very well-written paper, pioneering a serious optimal implementation of the problem of definite integration… it is a very good beginning…”。
2.基于约化的构造超指数函数与超几何项的邻差算子的高效算法
为了将基于约化的构造算法推广到比有理函数更一般的情形，他们的文章【3】中首先改进了Hermite, Davenport, Geddes-Le-Li等关于单变元超指数函数的约化算法，然后基于改进后的约化设计了计算双变元超指数函数的邻差算子的新算法。该算法同样解决了分离问题。与经典的Almkvist-Zeilberger算法相比不但在理论上给出邻差算子的阶数的更紧上界，而且效率更优。最近他们在文章【2】中将【3】中结果推广到了离散超几何情形，即改进了超几何项的Abramov-Petkovsek的约化算法并用于计算邻差算子。在2016年, 法国巴黎综合理工的Dumont在其博士论文工作中延续他们的工作将这类算法推广到了混合超指数-超几何情形, 并利用了他们的关于邻差算子存在性判定的工作. 文章【2】的前期结果获得了国际符号与代数专业委员会颁发的2014年度“ISSAC杰出海报奖”。对于这两项工作的评审意见指出 “it improves the state of the art in telescoping; the fact that a certificate is no longer needed is an important contribution, …”。 “These two enhancements – a faster reduction procedure as well as elimination of certificate computation – result in a novel creative telescoping algorithm…”。
3.基于约化的构造代数函数邻差算子的高效算法
如前所述，经典的Hermite约化只处理有理函数。为了处理代数函数，Trager在其博士论文中将Hermite约化算法推广到了代数函数情形。在【1】中首先将超指数, 超几何情形的多项式约化推广到代数函数情形, 然后结合Trager的约化算法给出了计算代数函数邻差算子的新算法，同时他们还给出了邻差算子的阶的新的上界。与经典的方法相比较，算法效率更佳，并且所给出的上界更优。文章的评审意见认为“This is an excellent paper, solving an interesting point…”。
参考文献
1.Shaoshi Chen, Manuel Kauers, and ChristophKoutschan. Reduction-Based Creative Telescoping for Algebraic Functions. Proceedings of ISSAC'16, 175–182, ACM Press, 2016.
2.Shaoshi Chen, Hui Huang, Manuel Kauers, and ZimingLi . A Modified Abramov-Petkovsek Reductionand Creative Telescoping for Hypergeometric Terms. Proceedings of ISSAC'15, 117–124, ACM Press, 2015.
3.AlinBostan,Shaoshi Chen, FrédéricChyzak, Ziming Li, and GuoceXin. Hermite Reduction and Creative Telescoping for Hyperexponential Functions. Proceedings of ISSAC'13, 77–84, ACM Press, 2013.
4.AlinBostan, Shaoshi Chen, FrédéricChyzak, and Ziming Li. Complexity of Creative Telescoping for Bivariate Rational Functions. Proceedings of ISSAC'10, 203–210, ACM Press, 2010.
