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).
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.
