Efficient algorithms and succinct data structures for acceleration of telescoping and related problems

本研究计划的重点是设计和实现快速符号算法和数值多层工具包，用于评估组合和和求解高阶差分方程。应用领域包括组合恒等式的自动证明、特殊函数的多精度求值、仿真、数学常数的高精度求值等。研究自然分为三个层次：算法、高效数据结构、低级编程和实现的硬件支持。所有这些都由一个共同的主题联系在一起：创造性的伸缩和应用，包括求解线性差分方程和快速计算组合和。创造性伸缩是计算机代数中求定和、定积分和证明组合恒等式的一种强有力的技术。在过去的几十年里，这项技术经历了各种算法的推广和改进。然而，一些严重的问题仍未得到解决。例如，构造望远镜的算法的运行时间可能不必要地表现出指数依赖于输入的大小。本研究在算法层的目的是开发一套新的算法，以克服长期存在的缺点。同时，在有效构造望远镜后，还需要求解线性差分望远镜的伸缩方程。对于不同类型的解决方案（多项式、有理、超几何），有许多算法可以做到这一点，这些解决方案都倾向于表现出运行时间对系数大小（在唯一分解域上的多项式）的非本质依赖。在本研究的数据结构层，我们将开发组合对象的替代表示，这有助于避免中间表达式膨胀。目标是开发简洁的表示和新算法，允许以惰性方式计算结果，避免不必要的指数依赖于输入的大小。此外，在这一部分中，我们计划进一步研究多层模算法的鲁棒性。它将多精度计算减少到几层模块化图像上的计算：下层是硬件精度（从而允许高效实现），上层是使用特殊选择的模，允许更快地从模块化图像集重建最终结果。在本研究的实现层，我们将继续研究基础工具的低级别硬件实现的适用性和可用性，以加速出现在更高级别的计算。这部分的核心将是一个带有web接口的独立C库，它允许生成和加载到FPGA板专用电路，以每个时钟周期一个值的速率对表达式进行数值计算，这比优化编译的代码快了几个数量级。

This research program focuses on the design and implementation of fast symbolic algorithms and numeric multi-layer toolkit for evaluation of combinatorial sums, and solving higher order difference equations. Application areas are in automatic proofs of combinatorial identities, multi-precision evaluation of special functions, simulation, and high precision evaluation of mathematical constants. The research naturally splits into three layers: algorithmic, efficient data structures, and low level programming and hardware support for implementation. All these are connected by the common theme: creative telescoping and applications, including solving linear difference equations and rapid evaluation of combinatorial sums. Creative telescoping is a powerful technique for evaluating definite sums and definite integrals and proving combinatorial identities in computer algebra. The technique has seen various algorithmic generalizations and improvements over the past decades. However, some serious problems remain unsolved. For example, the running time of the algorithms constructing a telescoper can unnecessary exhibit exponential dependency on the size of the input. The objective of this research in algorithmic layer is to develop a set of new algorithms that will overcome longstanding shortcomings. Also, after telescoper was efficiently constructed one wants to solve the linear difference telescoping equation. There are many algorithms to do this for different classes of solutions (polynomial, rational, hypergeometric) which all tend to exhibit nonessential dependency of the running time on the size of the coefficients (being polynomials over unique factorization domain). In the data structures layer of this research, we will develop alternative representations of combinatorial objects, which help to avoid an intermediate expressions swell. The objective is to develop succinct representation and new algorithms, that will allow to compute the results in lazy manner, avoiding unnecessary exponential dependency on size of the input. Additionally, in this part we plan to further investigate the robustness of multilayered modular arithmetic. It reduces the multi-precision computations to the computations on several layers of modular images: the lower layer at hardware precision (thus allowing efficient implementation), and higher layer using the special choice of moduli that allows to reconstruct the final result from the set of modular images faster. In the implementation layer of this research, we will continue to investigate applicability and usability of low level hardware implementations of basics tools to accelerate computations appearing on the higher levels. The core of this part will be a standalone C library with the web interface that allows to generate and load to FPGA board specialized circuits, evaluating expressions numerically at the rate of one value per clock cycle, which is orders of magnitude faster than optimized compiled code.