Talk:Integer relation algorithm

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)

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)

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)

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)

I checked the comments by 24.84.104.223 and indeed, the history section was highly biased so I fixed it. MvH.

Acronym?

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

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

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Integer relation algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html to http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 13:53, 14 November 2017 (UTC)