Integer relation algorithm: Difference between revisions

Revision as of 01:30, 10 November 2010

Revision as of 19:15, 24 January 2011

Line 5:

An '''integer relation algorithm''' is an [[algorithm]] for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain [[upper bound]].<ref>Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.</ref>

== History ==

For the case ''n'' = 2, an extension of the [[Euclidean algorithm]] can determine whether there is an integer relation between any two real numbers ''x''₁ and ''x''₂. The algorithm generates successive terms of the [[continued fraction]] expansion of ''x''₁/''x''₂; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.

Line 11:

*The [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|'''LLL algorithm''']], developed by [[Arjen Lenstra]], [[Hendrik Lenstra]] and [[László Lovász]] in 1982.<ref>{{MathWorld|urlname=LLLAlgorithm|title=LLL Algorithm}}</ref>

*The '''HJLS algorithm''', developed by Johan Hastad, Bettina Just, Jeffrey Lagarias, and Claus-Peter Schnorr in 1986.<ref>{{MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm}}</ref><ref>Johan Hastad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: ''Polynomial time algorithms for finding integer relations among real numbers.'' Preliminary version: STACS 1986 (''Symposium Theoret. Aspects Computer Science'') Lecture Notes Computer Science 210 (1986), p. 105–118. ''SIAM J. Computing'', Vol. 18 (1989), p. 859–881</ref>

*The '''PSOS algorithm''', developed by Ferguson in 1988.<ref>{{MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm}}</ref>

*The '''HJLSPSLQ algorithm''', developed by Ferguson and [[DavidBailey H.in Bailey|David1992 and substantially simplified by Ferguson, Bailey]], and Arno in 19921999.<ref>{{MathWorld|urlname=HJLSAlgorithmPSLQAlgorithm|title=HJLSPSLQ Algorithm}}</ref><ref>[http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf ''A Polynomial Time, Numerically Stable Integer Relation Algorithm''] by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992</ref>

*The '''PSLQ algorithm''', also developed by Ferguson and Bailey in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999.<ref>{{MathWorld|urlname=PSLQAlgorithm|title=PSLQ Algorithm}}</ref><ref>[http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf ''A Polynomial Time, Numerically Stable Integer Relation Algorithm''] by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992</ref>

In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by [[Jack Dongarra]] and Francis Sullivan.<ref>{{cite journal |author=Barry A. Cipra |url=http://amath.colorado.edu/resources/archive/topten.pdf |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4}}</ref>