Talk:Integer relation algorithm

crap

24.84.104.223, why dont you correct the article with a readable explanation, rather than rambling garbage? —Preceding unsigned comment added by 146.6.200.213 (talk) 20:36, 17 April 2009 (UTC)[reply]

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 24.84.104.223 (talk) 19:32, 20 April 2009 (UTC)[reply]

The deleted contribution of 24.84.104.223 (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'll try to come back later to this theme. --TeesJ (talk) 06:47, 25 January 2011 (UTC)[reply]

Acronym?

What does PSLQ stand for? --Slashme (talk) 14:15, 11 August 2008 (UTC)[reply]

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)[reply]

PSLQ is no longer state of the art.

This article should not portray PSLQ as the state of the art in integer-relation finding.

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