HJLS Algorithm

An algorithm for finding Integer Relations whose running time is bounded by a polynomial in thenumber of real variables. It is much faster than other algorithms such as the Ferguson-Forcade Algorithm, LLLAlgorithm, and PSOS Algorithm.

Unfortunately, it is numerically unstable and therefore requires extremely highprecision. The cause of this instability is not known (Ferguson and Bailey 1992), but is believed to derive from itsreliance on Gram-Schmidt Orthonormalization, which is know to be numerically unstable (Golub and van Loan 1989).

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.

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.

• Denjoy Integral
• Denominator
• Dense
• Density
• Density (Polygon)
• Density (Sequence)
• Denumerable Set
• Denumerably Infinite
• de Polignac's Conjecture
• Depth (Graph)
• Depth (Size)
• Depth (Statistics)
• Depth (Tree)
• Derangement
• de Rham Cohomology
• Derivative
• Derivative Test
• Derived Set
• Dervish
• Desargues' Theorem
• Descartes Circle Theorem
• Descartes-Euler Polyhedral Formula
• Descartes Folium
• Descartes' Formula
• Descartes Ovals