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

用于加速伸缩及相关问题的高效算法和简洁数据结构

• 批准号: RGPIN-2021-03147
• 负责人: Zima, Evgueni
• 金额: $ 1.75万
• 依托单位: Wilfrid Laurier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742401
• 关键词: Efficient; algorithms; succinct; data; structures

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.

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