HJLS Algorithm
المؤلف:
Ferguson, H. R. P. and Bailey, D. H.
المصدر:
"A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept
الجزء والصفحة:
...
18-7-2020
2979
HJLS Algorithm
An algorithm for finding integer relations whose running time is bounded by a polynomial in the number of real variables (Ferguson and Bailey 1992). Unfortunately, it is numerically unstable and therefore requires extremely high numeric precision. The cause of this instability is not known, but is believed to derive from its reliance on Gram-Schmidt orthonormalization (Ferguson and Bailey 1992), which is known to be numerically unstable (Golub and Van Loan 1989).
Rössner and Schnorr (1994) have developed a stable variation of HJLS (Ferguson et al. 1999).
REFERENCES:
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.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
