主題
Search

PSLQ 演算法


一種可用於查詢實數 整數關係 的演算法 x_1, ..., x_n 使得

 a_1x_1+a_2x_2+...+a_nx_n=0,

並非所有 a_i=0 都為零。雖然該演算法透過操作格來執行,但它不會將其簡化為短向量基,因此不是 格縮減 演算法。PSLQ 基於平方和部分和方案(如 PSOS 演算法),使用 QR 分解 實現。它由 Ferguson 和 Bailey (1992) 開發。Ferguson等人 (1999) 隨後開發了一個大大簡化的演算法版本,該版本還將演算法擴充套件到複數和四元數。Ferguson等人 (1999) 還證明了 PSLQ 與 HJLS 演算法 不同。

PSLQ 演算法在迭代次數上是多項式有界的,其迭代次數受 n 的多項式限制,並使用數值穩定的矩陣縮減程式 (Ferguson and Bailey 1992)。由於巧妙的技術允許在許多中間步驟中使用機器算術,PSLQ 往往比 Ferguson-Forcade 演算法LLL 演算法 更快。LLL 演算法 相比之下,必須使用中等精度,儘管通常不如 HJLS 演算法

雖然 LLL 演算法 是一種比 PSLQ 更通用的 格縮減 演算法,但使用 LLL 來獲得整數關係在某種意義上是一種“技巧”,而使用 PSLQ,人們要麼得到一個關係,要麼得到多項式次數和係數大小的下界,關係必須滿足這些界限。


另請參閱

Ferguson-Forcade 演算法, 整數關係, LLL 演算法, PSOS 演算法

使用 探索

參考文獻

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; 和 Moll, V. H. "整數關係檢測。" §2.2 in 實驗數學行動。 Wellesley, MA: A K Peters, pp. 29-31, 2007.Bailey, D. H.; Borwein, J. M.; 和 Girgensohn, R. "尤拉和的實驗評估。" Exper. Math. 3, 17-30, 1994.Bailey, D. H. 和 Broadhurst, D. J. "並行整數關係檢測:技術與應用。" Math. Comput. 70, 1719-1736, 2000.Bailey, D. H. "整數關係檢測。" Computing in Science and Engineering 2, 24-28, 2000.Bailey, D. 和 Plouffe, S. "識別數值常數。" 有機數學。1995 年 12 月 12-14 日在加拿大不列顛哥倫比亞省伯納比舉行的研討會論文集 (Ed. J. Borwein, P. Borwein, L. Jörgenson, 和 R. Corless). Providence, RI: Amer. Math. Soc., pp. 73-88, 1997. http://www.cecm.sfu.ca/organics/papers/bailey/. Bertok, P. "PSLQ 整數關係演算法實現。" http://library.wolfram.com/infocenter/MathSource/4263/.Borwein, J. 和 Bailey, D. 實驗數學:21 世紀的合理推理。 Wellesley, MA: A K Peters, pp. 51-54, 2003.Borwein, J. M. 和 Corless, R. M. "實驗數學的新興工具。" Amer. Math. Monthly 106, 899-909, 1999.實驗與構造數學中心. "整數關係。" http://www.cecm.sfu.ca/projects/IntegerRelations/.Crandall, R. E. 高等科學計算主題。 New York: Springer-Verlag, 1996.Ferguson, H. R. P. 和 Bailey, D. H. "多項式時間、數值穩定的整數關係演算法。" RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Ferguson, H. R. P.; Bailey, D. H.; 和 Arno, S. "PSLQ 演算法分析,一種整數關係查詢演算法。" Math. Comput. 68, 351-369, 1999.Zimmerman, P. "GMP 中 PSLQ 的實現。" http://www.loria.fr/~zimmerma/free/pslq-1.0.c.

在 中被引用

PSLQ 演算法

引用為

Weisstein, Eric W. "PSLQ 演算法。" 來自 Web 資源。 https://mathworld.tw/PSLQAlgorithm.html

主題分類