整数关系探测算法是零误差计算的算法基础。事实上，整数关系问题最早可被追溯到欧几里得时代。历史上，Jacobi、Hermite、Poincaré等著名数学家都曾试图给出有效算法，直到1977年由两位美国数学家Ferguson和Forcade给出了一个可行的方法。在此基础上，Ferguson 和 Bailey 给出的改进算法PSLQ被广泛应用于计算数论、计算物理、实验数学等领域，被喻为“20世纪十大算法之一”(SIAM News 33(4):1-2, 2000)。然而，在实际计算中，该算法依赖于高精度的浮点运算，其数值稳定性及计算复杂度等问题自上世纪七十年代被提出以来，一直悬而未决。重庆研究院近期的这项工作解决了PSLQ算法的数值稳定性问题，为进一步解决数值PSLQ算法的计算复杂度问题提供了良好的理论工具。审稿人评价为“… The results are definitely new – this reviewer is not aware of any other similar results.”
通过对原始算法的重新分析，新发现了算法中的一个不变关系。基于这一关系，该研究给出了改进算法，给出并证明了改进算法的新的终止条件。以此为基础，对算法进行扰动分析，揭示了输入数据精度与输出质量的内在关系，从而建立了如下的前向误差定理：
该定理能够很好地解释大量实验数据所显示出的规律，为数值PSLQ算法的设计与分析奠定了理论基础。该项研究获得国家自然科学基金项目、中科院前沿科学重点研究项目、中科院青促会项目的支持。
论文链接：
http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2018-03356-7/