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

该研究项目致力于设计和实现快速符号算法和用于计算组合和以及求解高阶差分方程组的多层数值工具包。应用领域包括组合恒等式的自动证明、特殊函数的多精度求值、计算机模拟和数学常数的高精度求值。研究自然分为三层：算法、高效的数据结构，以及实现的低层编程和硬件支持。所有这些都由一个共同的主题联系在一起：创造性的伸缩和应用，包括解线性差分方程组和快速计算组合和。创造性伸缩是计算计算机代数中的定和、定积分和证明组合恒等式的一种强有力的技术。在过去的几十年里，这项技术经历了各种算法的概括和改进。然而，一些严重的问题仍然没有解决。例如，构造望远镜的算法的运行时间可能不必要地表现出对输入大小的指数依赖。算法层的这项研究的目的是为了开发一套新的算法，克服长期存在的缺点。此外，在望远镜被有效地建造后，人们想要求解伸缩方程的线性差。对于不同类别的解(多项式、有理、超几何)，有许多算法可以做到这一点，这些算法都倾向于表现出运行时间对系数大小的非本质依赖(是唯一因式分解域上的多项式)。在本研究的数据结构层，我们将开发组合对象的替代表示，这有助于避免中间表达式的膨胀。我们的目标是开发简洁的表示法和新的算法，允许以懒惰的方式计算结果，避免不必要的对输入大小的指数依赖。此外，在这一部分中，我们计划进一步研究多层模运算的健壮性。它将多精度计算减少为对几层模块图像的计算：较低层以相同的硬件精度(从而允许高效实施)，较高层使用特殊的模块选择，允许更快地从模块图像集重建最终结果。在本研究的实现层，我们将继续调查基本工具的低级别硬件实现的适用性和可用性，以加速出现在较高级别的计算。这一部分的核心将是一个独立的C库，它具有Web界面，允许生成并加载到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.