整數(shù)關(guān)系探測算法是零誤差計算的算法基礎(chǔ)。事實上，整數(shù)關(guān)系問題最早可被追溯到歐幾里得時代。歷史上，Jacobi、Hermite、Poincaré等著名數(shù)學(xué)家都曾試圖給出有效算法，直到1977年由兩位美國數(shù)學(xué)家Ferguson和Forcade給出了一個可行的方法。在此基礎(chǔ)上，F(xiàn)erguson 和 Bailey 給出的改進算法PSLQ被廣泛應(yīng)用于計算數(shù)論、計算物理、實驗數(shù)學(xué)等領(lǐng)域，被喻為“20世紀(jì)十大算法之一”(SIAM News 33(4):1-2, 2000)。然而，在實際計算中，該算法依賴于高精度的浮點運算，其數(shù)值穩(wěn)定性及計算復(fù)雜度等問題自上世紀(jì)七十年代被提出以來，一直懸而未決。重慶研究院近期的這項工作解決了PSLQ算法的數(shù)值穩(wěn)定性問題，為進一步解決數(shù)值PSLQ算法的計算復(fù)雜度問題提供了良好的理論工具。審稿人評價為“… The results are definitely new – this reviewer is not aware of any other similar results.”

　　通過對原始算法的重新分析，新發(fā)現(xiàn)了算法中的一個不變關(guān)系。基于這一關(guān)系，該研究給出了改進算法，給出并證明了改進算法的新的終止條件。以此為基礎(chǔ)，對算法進行擾動分析，揭示了輸入數(shù)據(jù)精度與輸出質(zhì)量的內(nèi)在關(guān)系，從而建立了如下的前向誤差定理：

　　該定理能夠很好地解釋大量實驗數(shù)據(jù)所顯示出的規(guī)律，為數(shù)值PSLQ算法的設(shè)計與分析奠定了理論基礎(chǔ)。該項研究獲得國家自然科學(xué)基金項目、中科院前沿科學(xué)重點研究項目、中科院青促會項目的支持。

　　論文鏈接：  

　　http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2018-03356-7/