整数关系探测的误差可控算法与应用

Over the last few decades, error-controllable hybrid symbolic-numeric computation has been receiving increasing attention from both academic community and industry. In this field, there exists an important direction that focuses on the topic of obtaining exact value by approximate computing. Many results of this direction have been successfully applied in several areas, including information technology and digital design and manufacturing. However, as one of the most frequently used tools in this direction, the integer relation finding algorithm, named one of the top 10 algorithms in the twentieth century, has no bit-complexity analysis, while it is only analyzed under the exact real arithmetic model. This state has already impeded the direction of obtaining exact value by approximate computing. In the present project, we are going to investigate the essential link between integer relation finding and lattice reduction, adapt the techniques used in floating-point lattice reduction algorithms, design efficient floating-point integer relation finding algorithms, and analyze their bit-complexity bounds. The applicant has had several research results related to integer relation finding, lattice reduction and obtaining exact value by approximate computing. In view of these facts, the bit-complexity bounds of the integer relation finding algorithm will be hopefully disclosed during this project.

近年来，误差可控的符号-数值混合计算已越来越受到学术界和工业界的重视。其中，一个重要的研究方向以采用近似计算获得准确值为研究内容，并被成功地应用到包括信息技术、数字化设计制造等国民经济关键领域。然而这一方向所采用的基本工具之一——整数关系探测算法（二十世纪十大算法之一）——的复杂度理论仅建立在精确实数计算模型下，缺乏实际的位复杂度分析，阻碍了该方向的发展。本项目针对这一现状，拟通过揭示整数关系探测和格约化之间的本质联系、改进浮点格约化算法的相关技术，设计基于浮点算术的误差可控高效整数关系探测算法，并给出其位复杂度分析。鉴于申请者在整数关系探测、格约化以及采用近似计算获得准确值等方面已有一定的研究基础，通过本项目的实施，有望攻克整数关系探测算法的位复杂度分析难题，进而推动采用近似计算获得准确值这一方向的进一步发展。

整数关系探测问题是指：对给定的一组实数 x_1, …, x_n，如何找到一组不全为零的整数 m_1,..., m_n 使得 m_1*x_1+...+m_n*x_n=0？该问题在计算机科学、计算数论、量子场论等诸多领域有重要应用，并由此开创了“实验数学”——用计算的方式发现数学定理——的数学研究新范式，同时，也是张景中院士、冯勇研究员提出的“采用近似计算获得准确值”这一符号数值计算新思想的理论基础。针对已有的 PSLQ 整数关系探测算法（ “二十世纪十大算法”之一）缺乏有效的数值分析和数值算法，而基于格基约化 LLL 算法的整数关系计算的理论复杂度上界与实验结果差距明显等问题，本项目主要完成了以下工作：.建立了这两类整数关系探测算法之间的联系，成功设计出采用 PSLQ 算法的策略来进行格基约化的算法。论文发表在国际会议 ICCSN 2017 上，也在第九届全国计算机数学学术会议上报告了相关工作。.基于上述格约化算法与整数关系探测算法之间的联系，我们通过借鉴数值格约化算法的已有经验，成功解决了 PSLQ 算法的数值稳定性问题，设计并分析了相应的数值 PSLQ 算法。论文已在线发表在 JCR 数学类一区刊物 Math. Comp. 上. .应用 LLL 算法求解整数关系时，理论上的复杂度上界与实际的观察出入很大。针对这一问题，我们提出了一个全新的 LLL 算法分析工具，证明了 LLL 算法中迭代次数的一个新的上界。该上界与传统分析得到的上界相比，降低了一个因子 n，这里的 n 是指求解问题的维数。相关论文发表在 ACM 符号与代数计算顶级会议 ISSAC 上。.本项目的实验研究也已完成，我们对已有的计算整数关系问题的开源软件进行了系统的评估与分析，得出的结论是目前基于LLL格基约化的方法应是整数关系计算的首选，而软件包首选推荐本项目的合作者之一，法国 CNRS 的 Gilles Villard 研究员主导开发的 hplll，该软件较 UC Berkley 的 D. H. Bailey 教授开发的 PSLQ 算法的软件包MPFUN2015 效率提高近百倍。相关论文已形成初稿，拟投 ACM 符号与代数计算顶级会议 ISSAC。