主題
Search

HJLS 演算法


一種用於查詢整數關係的演算法,其執行時間受實變數數量的多項式限制 (Ferguson and Bailey 1992)。遺憾的是,它在數值上不穩定,因此需要極高的數值精度。這種不穩定性的原因尚不清楚,但據信源於其對 Gram-Schmidt 正交化的依賴 (Ferguson and Bailey 1992),而 Gram-Schmidt 正交化已知在數值上不穩定 (Golub and Van Loan 1989)。

Rössner 和 Schnorr (1994) 開發了 HJLS 的一個穩定變體 (Ferguson 等人 1999)。


另請參閱

Ferguson-Forcade 演算法, Gram-Schmidt 正交化, 整數關係, LLL 演算法, PSLQ 演算法, PSOS 演算法

使用 探索

參考文獻

Ferguson, H. R. P. and Bailey, D. H. "A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Ferguson, H. R. P.; Bailey, D. H.; and Arno, S. "Analysis of PSLQ, An Integer Relation Finding Algorithm." Math. Comput. 68, 351-369, 1999.Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins, 1996.Hastad, J.; Just, B.; Lagarias, J. C.; and Schnorr, C. P. "Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers." SIAM J. Comput. 18, 859-881, 1988.Rössner, C. and Schnorr, C. P. "A Stable Integer Relation Algorithm." Tech. Rep. TR-94-016. FB Mathematik/Informatik, Universität Frankfurt, 1-11, 1994.

在 中被引用

HJLS 演算法

請引用為

Weisstein, Eric W. “HJLS 演算法。” 來自 Web 資源。 https://mathworld.tw/HJLSAlgorithm.html

主題分類