Talk:Integer relation algorithm
|WikiProject Mathematics||(Rated Start-class, Mid-importance)|
Top Ten Algorithms of the Century
SIAM news dropped the ball in their description of integer relation finding in "Top Ten Algorithms of the Century". They give the credit to 1977/1979 Ferguson-Forcade and write that their algorithm was used to find a degree 120 polynomial related to bifurcation points. However, that is simply impossible, the original Ferguson-Forcade is too inefficient to reach n=120. The first algorithms that can actually do this computation are LLL and HJLS (1982 and 1986). The actual degree 120 computation that SIAM mentioned was done by the 1992/1999 PSLQ algorithm, but published sources state that PSLQ is essentially equivalent to 1986 HJLS. Ferguson-Forcade 1977/1979 certainly deserve credit for moving the topic forward. However, the ability to handle problems with large n is due to LLL and HJLS both of which predate PSLQ. SIAM dropped the ball by mentioning an n=120 application, without crediting the authors that first made that possible. Mark van Hoeij, Feb 4 2014. — Preceding unsigned comment added by MvH (talk • contribs) 14:31, 4 February 2014 (UTC)
Rambling garbage? Perhaps, but maybe not. The fact that you think so might indicate a lack of knowledge/understanding on your part. I don't really care about wikipedia, but if you do you might want to change the history to accurately reflect things.
The name HJLS is due to Ferguson and Bailey, the actual algorithm is due to Hastad, Just, Lagarias and Schnorr who called it the small integer relation algorithm. Their paper is easily found online.
PSLQ (with parameter gamma=sqrt(2)) and HJLS (with full reductions) are equivalent algorithms. The differences observed by Bailey are due to implementational choices (the bit on mathworld about the numerical instability being due to using the Gram-Schmidt process to construct the initial basis is a load of crap put forth by Bailey, it is due to the lack of full reductions by Hastad et al. in an effort to save time). You may wish to look up the work of Meichsner here.
Also, the page seems to suggest that the LLL algorithm was developed as an extension of Ferguson and Forcades generalized Euclidean algorithm. You may wish to look up the initial paper on LLL (yes, I know LLL can be used to find integer relations and that there are strong similarities between the algorithms). —Preceding unsigned comment added by 18.104.22.168 (talk) 19:32, 20 April 2009 (UTC)
- The deleted contribution of 22.214.171.124 (17 April 2009) is too valuable for letting it disappear:
- "The above history is crap. "HJLS" was developed by Hastad, Just, Lagarias and Schnorr before Ferguson's "PSLQ" algorithm (I would guess that Bailey's contrabution is the multilevel implementation using lower precision arithemtic and that Ferguson is responsible for the actual algorithm). These horrible names are due to Ferguson and Bailey. Hastad, Just, Lagarias and Schnorr called their algorthim "the small integer relation algorithm" which is a much better name. Ferguson and Bailey initially claimed the two algorithms are distinct but this is false. The differences observed are due to implementational choices. Unfortunately, since the proof of termination only requires the off-diagonal element of the matrix H'(in PSLQ) to be at most half the magnitude of the above diagonal element, the authors of HJLS figured they could save some time by only partially reducing the matrix H' at each step. This is what causes the numerical instability (it also cause the vectors in their basis for the lattice Z^n to not converge to the vector x which was the whole point in the first place). The second implementational difference is due to Bailey and Ferguson and comes from their deviation from the described theoretical algorithm. They terminate as soon as they think they have found an integer relation instead of waiting for there to be only one nonzero entry in the final column of the matrix H'. Although not a terrible thing to do, it does cause them to lose the ability to claim that norm of the returned integer relation is no larger than gamma^(n-2) times the norm of the smallest integer relation for x. If one looks at the algorithms described in the paper, the ones that they prove are correct, terminate, and find a small relation (not the final implemenations where they cut corners), one can show that these two algorithms are equivalent. The equivalence of the theoretical algorithms "PSLQ" and "HJLS" was shown by Meichsner(2001). The Wolfram/Mathematica/Mathworld people who write their history/definition pages don't really seem to do anything other than copy down junk without understanding it. You should use the same caution when refering to them as you do when refering to articles on Wikipedia."
- I checked the comments by 126.96.36.199 and indeed, the history section was highly biased so I fixed it. MvH.
- Ferguson and Bailey's 1992 paper says "This algorithm has been named “PSLQ,” since it is based on a partial sum of squares scheme like the PSOS algorithm, yet it can be efficiently implemented with a LQ (lower trapezoidal–orthogonal) matrix factorization". Gandalf61 (talk) 14:28, 11 August 2008 (UTC)
PSLQ is no longer state of the art.
In 2001 I developed an algorithm for factoring in Q[x] that is based on integer-relation finding. I implemented two versions in Maple, one based on PSLQ and one based on LLL. Both worked well, but the LLL version was substantially faster than the PSLQ version. Of course, this could have been due to Maple-specific issues, however, since then there have been drastic improvements in LLL (both practical as well as complexity improvements). These improvements convince me that recent LLL implementations (e.g. by Novocin) outperform PSLQ. Mark van Hoeij (Oct 1, 2011).
- I decided to check this by comparing CPU timings, I took the example with r=s=10 on page 24 from http://www.davidhbailey.com/dhbtalks/dhb-carma-20100824.pdf With Magma's implementation of LLL this takes 76 seconds (on 1 core, on a PC from 2008), compared with 2747 seconds reported on page 24. Page 25 (large test problems) lists PSLQ applications with n in 145, 120, 118, 125 but I remember seeing a paper where LLL was used with n=640 which suggests that modern LLL versions are stronger than PSLQ. Mark van Hoeij (Feb 4 2014).