|
|
|
An algorithm for finding Integer Relations whose running time is bounded by a polynomial in the number of real variables. It is much faster than other algorithms such as the Ferguson-Forcade Algorithm, LLL Algorithm, and PSOS Algorithm.
Unfortunately, it is numerically unstable and therefore requires extremely high precision. The cause of this instability is not known (Ferguson and Bailey 1992), but is believed to derive from its reliance on Gram-Schmidt Orthonormalization, which is know to be numerically unstable (Golub and van Loan 1989).
See also Ferguson-Forcade Algorithm, Integer Relation, LLL Algorithm, PSLQ Algorithm, PSOS Algorithm
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.