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

See also

Ferguson-Forcade Algorithm, Gram-Schmidt Orthonormalization, Integer Relation, LLL Algorithm, PSLQ Algorithm, PSOS Algorithm

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

HJLS Algorithm

Cite this as:

Weisstein, Eric W. "HJLS Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HJLSAlgorithm.html

Subject classifications