Block Lanczos algorithm - Revision history

Onel5969: Disambiguating links to Number field sieve (link changed to General number field sieve) using DisamAssist.

2023-10-24T20:23:53Z

Disambiguating links to Number field sieve (link changed to General number field sieve) using DisamAssist.

← Previous revision		Revision as of 20:23, 24 October 2023
Line 1:		Line 1:
	In [[computer science]], the '''block Lanczos algorithm''' is an [[algorithm]] for finding the [[nullspace]] of a [[Matrix (mathematics)\|matrix]] over a [[finite field]], using only multiplication of the matrix by long, thin matrices. Such matrices are considered as vectors of [[tuple]]s of finite-field entries, and so tend to be called 'vectors' in descriptions of the algorithm.		In [[computer science]], the '''block Lanczos algorithm''' is an [[algorithm]] for finding the [[nullspace]] of a [[Matrix (mathematics)\|matrix]] over a [[finite field]], using only multiplication of the matrix by long, thin matrices. Such matrices are considered as vectors of [[tuple]]s of finite-field entries, and so tend to be called 'vectors' in descriptions of the algorithm.

	The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[number field sieve]], and its development has been entirely driven by this application.		The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[General number field sieve\|number field sieve]], and its development has been entirely driven by this application.

	It is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.<ref>{{cite conference \|last=Montgomery \|first=P L \|author-link=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|book-title=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref>		It is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.<ref>{{cite conference \|last=Montgomery \|first=P L \|author-link=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|book-title=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref>

217.197.198.196: Restoring a link (to a description of the algorithm) and a sentence from an old revision

2022-06-23T10:16:09Z

Restoring a link (to a description of the algorithm) and a sentence from an old revision

← Previous revision		Revision as of 10:16, 23 June 2022
Line 3:		Line 3:
	The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[number field sieve]], and its development has been entirely driven by this application.		The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[number field sieve]], and its development has been entirely driven by this application.

			It is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.<ref>{{cite conference \|last=Montgomery \|first=P L \|author-link=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|book-title=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref>
	== Parallelization issues ==		== Parallelization issues ==

Ixfd64: {{linear-algebra-stub}}

2021-09-23T17:14:26Z

← Previous revision		Revision as of 17:14, 23 September 2021
Line 11:		Line 11:
	== References ==		== References ==
	{{reflist}}		{{reflist}}

			{{linear-algebra-stub}}

	[[Category:Numerical linear algebra]]		[[Category:Numerical linear algebra]]

86.159.61.35: The block Lanczos method is far older than claimed, it goes back to at least the 70s. I don't know the original paper but it's definitely before 1995.

2021-06-09T12:41:45Z

The block Lanczos method is far older than claimed, it goes back to at least the 70s. I don't know the original paper but it's definitely before 1995.

← Previous revision		Revision as of 12:41, 9 June 2021
Line 8:		Line 8:

	The [[block Wiedemann algorithm]] is more useful in contexts where several systems each large enough to hold the entire matrix are available, since in that algorithm the systems can run independently until a final stage at the end.		The [[block Wiedemann algorithm]] is more useful in contexts where several systems each large enough to hold the entire matrix are available, since in that algorithm the systems can run independently until a final stage at the end.

	== History ==
	The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|author-link=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|book-title=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.

	== References ==		== References ==

Monkbot: Task 18 (cosmetic): eval 1 template: hyphenate params (2×);

2021-01-14T01:18:24Z

Task 18 (cosmetic): eval 1 template: hyphenate params (2×);

← Previous revision		Revision as of 01:18, 14 January 2021
Line 10:		Line 10:

	== History ==		== History ==
	The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|~~authorlink~~=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|~~booktitle~~=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.		The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|author-link=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|book-title=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.

	== References ==		== References ==

OAbot: Open access bot: doi added to citation with #oabot.

2020-04-18T13:16:16Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 13:16, 18 April 2020
Line 10:		Line 10:

	== History ==		== History ==
	The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.		The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 \|doi-access=free }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.

	== References ==		== References ==

David Eppstein: unstub

2019-01-05T05:53:01Z

unstub

← Previous revision		Revision as of 05:53, 5 January 2019
Line 16:		Line 16:

	[[Category:Numerical linear algebra]]		[[Category:Numerical linear algebra]]


	{{Linear-algebra-stub}}
	{{Algorithm-stub}}

Citation bot: Misc citation tidying. You can use this bot yourself. Report bugs here. | User-activated.

2018-12-18T14:39:06Z

Misc citation tidying. You can use this bot yourself. Report bugs here. | User-activated.

← Previous revision		Revision as of 14:39, 18 December 2018
Line 10:		Line 10:

	== History ==		== History ==
	The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) ~~\|url=https://link.springer.com/chapter/10.1007/3-540-49264-X_9~~ \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag}}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.		The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag\|doi=10.1007/3-540-49264-X_9 }}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.

	== References ==		== References ==

Ixfd64: fix dead link

2018-04-11T16:13:43Z

fix dead link

← Previous revision		Revision as of 16:13, 11 April 2018
Line 10:		Line 10:

	== History ==		== History ==
	The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|url=~~http~~://~~kolxo3~~.~~tiera~~.ru/~~_Papers~~/~~Numerical_methods~~/~~Integer%20factoring/Montgomery.%20Block%20Lanczos%20algorithm%20for%20GF%282%29%20linear%20algebra%2816s%29.ps.gz~~ \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag}}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.		The block Lanczos algorithm was developed by [[Peter Montgomery (mathematician)\|Peter Montgomery]] and published in 1995;<ref>{{cite conference \|last=Montgomery \|first=P L \|authorlink=Peter Montgomery (mathematician) \|year=1995 \|title=A Block Lanczos Algorithm for Finding Dependencies over GF(2) \|url=https://link.springer.com/chapter/10.1007/3-540-49264-X_9 \|conference=EUROCRYPT '95 \|booktitle=Lecture Notes in Computer Science \|volume=921 \|pages=106–120 \|publisher=Springer-Verlag}}</ref> it is based on, and bears a strong resemblance to, the [[Lanczos algorithm]] for finding [[eigenvalue]]s of large sparse real matrices.

	== References ==		== References ==

Maxal at 23:55, 10 October 2013

2013-10-10T23:55:55Z

← Previous revision		Revision as of 23:55, 10 October 2013
Line 1:		Line 1:
	~~The~~ '''block Lanczos algorithm''' is a ~~procedure~~ for finding the [[nullspace]] of a [[Matrix (mathematics)\|matrix]] over a [[finite field]], using only multiplication of the matrix by long, thin matrices. ~~These long, thin~~ matrices are considered as vectors of ~~tuples~~ of finite-field entries, and so tend to be called 'vectors' in descriptions of the algorithm.		In [[computer science]], the '''block Lanczos algorithm''' is an [[algorithm]] for finding the [[nullspace]] of a [[Matrix (mathematics)\|matrix]] over a [[finite field]], using only multiplication of the matrix by long, thin matrices. Such matrices are considered as vectors of [[tuple]]s of finite-field entries, and so tend to be called 'vectors' in descriptions of the algorithm.

	The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[number field sieve]], and its development has been entirely driven by this application.		The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in [[integer factorization]] algorithms such as the [[quadratic sieve]] and [[number field sieve]], and its development has been entirely driven by this application.