整數(shù)關(guān)系探測(cè)算法是零誤差計(jì)算的算法基礎(chǔ)。事實(shí)上，整數(shù)關(guān)系問(wèn)題最早可被追溯到歐幾里得時(shí)代。歷史上，Jacobi、Hermite、Poincaré等著名數(shù)學(xué)家都曾試圖給出有效算法，直到1977年由兩位美國(guó)數(shù)學(xué)家Ferguson和Forcade給出了一個(gè)可行的方法。在此基礎(chǔ)上，F(xiàn)erguson 和 Bailey 給出的改進(jìn)算法PSLQ被廣泛應(yīng)用于計(jì)算數(shù)論、計(jì)算物理、實(shí)驗(yàn)數(shù)學(xué)等領(lǐng)域，被喻為“20世紀(jì)十大算法之一”(SIAM News 33(4):1-2, 2000)。然而，在實(shí)際計(jì)算中，該算法依賴于高精度的浮點(diǎn)運(yùn)算，其數(shù)值穩(wěn)定性及計(jì)算復(fù)雜度等問(wèn)題自上世紀(jì)七十年代被提出以來(lái)，一直懸而未決。重慶研究院近期的這項(xiàng)工作解決了PSLQ算法的數(shù)值穩(wěn)定性問(wèn)題，為進(jìn)一步解決數(shù)值PSLQ算法的計(jì)算復(fù)雜度問(wèn)題提供了良好的理論工具。審稿人評(píng)價(jià)為“… The results are definitely new – this reviewer is not aware of any other similar results.”
通過(guò)對(duì)原始算法的重新分析，新發(fā)現(xiàn)了算法中的一個(gè)不變關(guān)系?；谶@一關(guān)系，該研究給出了改進(jìn)算法，給出并證明了改進(jìn)算法的新的終止條件。以此為基礎(chǔ)，對(duì)算法進(jìn)行擾動(dòng)分析，揭示了輸入數(shù)據(jù)精度與輸出質(zhì)量的內(nèi)在關(guān)系，從而建立了如下的前向誤差定理：
該定理能夠很好地解釋大量實(shí)驗(yàn)數(shù)據(jù)所顯示出的規(guī)律，為數(shù)值PSLQ算法的設(shè)計(jì)與分析奠定了理論基礎(chǔ)。該項(xiàng)研究獲得國(guó)家自然科學(xué)基金項(xiàng)目、中科院前沿科學(xué)重點(diǎn)研究項(xiàng)目、中科院青促會(huì)項(xiàng)目的支持。
論文鏈接：
http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2018-03356-7/