Talk:Integer relation algorithm - Revision history

Cewbot: Maintain {{WPBS}}: 1 WikiProject template. Remove 1 deprecated parameter: field.

2024-03-09T01:35:11Z

Maintain {{WPBS}}: 1 WikiProject template. Remove 1 deprecated parameter: field.

← Previous revision		Revision as of 01:35, 9 March 2024
Line 1:		Line 1:
	{{WikiProject banner shell\|class=Start\|		{{WikiProject banner shell\|class=Start\|
	{{WikiProject Mathematics\|importance=mid~~\|field=number theory~~}}		{{WikiProject Mathematics\|importance=mid}}
	}}		}}

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-01-30T08:03:26Z

Implementing WP:PIQA (Task 26)

← Previous revision		Revision as of 08:03, 30 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|class=Start\|
	{{~~maths~~ ~~rating\|class=start~~\|importance=mid\|field=number theory}}		{{WikiProject Mathematics\|importance=mid\|field=number theory}}

			}}

	== Top Ten Algorithms of the Century ==		== Top Ten Algorithms of the Century ==

InternetArchiveBot: Notification of altered sources needing review #IABot (v1.6.1)

2017-11-14T13:53:22Z

Notification of altered sources needing review #IABot (v1.6.1)

← Previous revision		Revision as of 13:53, 14 November 2017
Line 36:		Line 36:
	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).		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).		: 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 [[special:diff/810310306\|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot\|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.

			{{sourcecheck\|checked=false\|needhelp=}}

			Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 13:53, 14 November 2017 (UTC)

Mark viking: Added maths banner

2014-02-28T04:14:38Z

Added maths banner

← Previous revision		Revision as of 04:14, 28 February 2014
Line 1:		Line 1:
			{{maths rating\|class=start\|importance=mid\|field=number theory}}


	== Top Ten Algorithms of the Century ==		== 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. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:MvH\|MvH]] ([[User talk:MvH\|talk]] • [[Special:Contributions/MvH\|contribs]]) 14:31, 4 February 2014 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		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. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:MvH\|MvH]] ([[User talk:MvH\|talk]] • [[Special:Contributions/MvH\|contribs]]) 14:31, 4 February 2014 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

71.229.28.197: /* PSLQ is no longer state of the art. */

2014-02-04T20:28:31Z

PSLQ is no longer state of the art.

← Previous revision		Revision as of 20:28, 4 February 2014
Line 32:		Line 32:

	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).		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)~~. This suggests that for n=100~~, ~~Magma's~~ ~~LLL~~ on 1 ~~core is faster than PSLQ~~ on 64 ~~cores~~. 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 ~~significantly~~ stronger than PSLQ. Mark van Hoeij (Feb 4 2014).		: 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).

MvH: /* PSLQ is no longer state of the art. */

2014-02-04T15:42:30Z

PSLQ is no longer state of the art.

← Previous revision		Revision as of 15:42, 4 February 2014
Line 32:		Line 32:

	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).		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). This suggests that for n=100, Magma's LLL on 1 core is faster than PSLQ on 64 cores. 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 ~~can solve~~ significantly ~~larger~~ ~~problems~~. Mark van Hoeij (Feb 4 2014).		: 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). This suggests that for n=100, Magma's LLL on 1 core is faster than PSLQ on 64 cores. 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 significantly stronger than PSLQ. Mark van Hoeij (Feb 4 2014).

MvH: /* PSLQ is no longer state of the art. */

2014-02-04T15:41:01Z

PSLQ is no longer state of the art.

← Previous revision		Revision as of 15:41, 4 February 2014
Line 31:		Line 31:
	== PSLQ is no longer state of the art. ==		== 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).
	This article should not portray PSLQ as the state of the art in integer-relation finding.
			: 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). This suggests that for n=100, Magma's LLL on 1 core is faster than PSLQ on 64 cores. 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 can solve significantly larger problems. Mark van Hoeij (Feb 4 2014).

⚫	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). <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/71.229.31.123\|71.229.31.123]] ([[User talk:71.229.31.123\|talk]]) 01:18, 2 October 2011 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

SineBot: Signing comment by MvH - ""

2014-02-04T14:32:48Z

Signing comment by MvH - ""

← Previous revision		Revision as of 14:32, 4 February 2014
Line 1:		Line 1:
	== Top Ten Algorithms of the Century ==		== 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.		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. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:MvH\|MvH]] ([[User talk:MvH\|talk]] • [[Special:Contributions/MvH\|contribs]]) 14:31, 4 February 2014 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

	== crap ==		== crap ==

MvH at 14:31, 4 February 2014

2014-02-04T14:31:44Z

← Previous revision		Revision as of 14:31, 4 February 2014
Line 1:		Line 1:
			== 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.

	== crap ==		== crap ==
	24.84.104.223, why dont you correct the article with a readable explanation, rather than rambling garbage? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/146.6.200.213\|146.6.200.213]] ([[User talk:146.6.200.213\|talk]]) 20:36, 17 April 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->		24.84.104.223, why dont you correct the article with a readable explanation, rather than rambling garbage? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/146.6.200.213\|146.6.200.213]] ([[User talk:146.6.200.213\|talk]]) 20:36, 17 April 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

71.229.28.197: /* crap */ I fixed the comments from this Talk-section in the main page, I think this (unfortunately named!) Talk-section is now obsolete.

2014-02-04T04:14:00Z

crap: I fixed the comments from this Talk-section in the main page, I think this (unfortunately named!) Talk-section is now obsolete.

← Previous revision		Revision as of 04:14, 4 February 2014
Line 18:		Line 18:
	:I'll try to come back later to this theme. --[[User:TeesJ\|TeesJ]] ([[User talk:TeesJ\|talk]]) 06:47, 25 January 2011 (UTC)		:I'll try to come back later to this theme. --[[User:TeesJ\|TeesJ]] ([[User talk: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. [[User:MvH\|MvH]].


	==Acronym?==		==Acronym?==