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.