近日，中国科学院重庆绿色智能技术研究院自动推理与认知中心研究团队在对整数关系探测算法的研究中取得新进展，相关研究成果已在美国数学会会刊之一Mathematics of Computation上在线发表。
整数关系探测算法是零误差计算的算法基础。事实上，整数关系问题最早可被追溯到欧几里得时代。历史上，Jacobi、Hermite、Poincaré等著名数学家都曾试图给出有效算法，直到1977年由两位美国数学家Ferguson和Forcade给出了一个可行的方法。在此基础上，Ferguson 和Bailey 给出的改进算法PSLQ被广泛应用于计算数论、计算物理、实验数学等领域，被喻为“20世纪十大算法之一”(SIAM News 33(4):1-2, 2000)。然而，在实际计算中，该算法依赖于高精度的浮点运算，其数值稳定性及计算复杂度等问题自上世纪七十年代被提出以来，一直悬而未决。重庆研究院近期的这项工作解决了PSLQ算法的数值稳定性问题，为进一步解决数值PSLQ算法的计算复杂度问题提供了良好的理论工具。
通过对原始算法的重新分析，新发现了算法中的一个不变关系。基于这一关系，该研究给出了改进算法，给出并证明了改进算法的新的终止条件。以此为基础，对算法进行扰动分析，揭示了输入数据精度与输出质量的内在关系，从而建立了如下的前向误差定理：
该定理能够很好地解释大量实验数据所显示出的规律，为数值PSLQ算法的设计与分析奠定了理论基础。该项研究获得国家自然科学基金项目、中科院前沿科学重点研究项目、中科院青促会项目的支持。
论文链接
