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

点击翻译按钮获取中文摘要

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.