Lanczos algorithm - Revision history

128.131.126.87: In Cullum 1986 the subtraction of the previous state is done earlier.

2025-05-23T10:58:13Z

In Cullum 1986 the subtraction of the previous state is done earlier.

← Previous revision		Revision as of 10:58, 23 May 2025
Line 24:		Line 24:
	:## If <math> \beta_j \neq 0 </math>, then let <math> v_j = w_{j-1} / \beta_j </math>,		:## If <math> \beta_j \neq 0 </math>, then let <math> v_j = w_{j-1} / \beta_j </math>,
	:##: else pick as <math>v_j</math> an arbitrary vector with Euclidean norm <math>1</math> that is orthogonal to all of <math> v_1,\dots,v_{j-1} </math>.		:##: else pick as <math>v_j</math> an arbitrary vector with Euclidean norm <math>1</math> that is orthogonal to all of <math> v_1,\dots,v_{j-1} </math>.
	:## Let <math> w_j' = A v_j </math>.		:## Let <math> w_j' = A v_j - \beta_j v_{j-1} </math>.
	:## Let <math> \alpha_j = w_j'^* v_j </math>.		:## Let <math> \alpha_j = w_j'^* v_j </math>.
	:## Let <math> w_j = w_j' - \alpha_j v_j ~~- \beta_j v_{j-1}~~ </math>.		:## Let <math> w_j = w_j' - \alpha_j v_j </math>.
	:# Let <math>V</math> be the matrix with columns <math> v_1,\dots,v_m </math>. Let <math>T = \begin{pmatrix}		:# Let <math>V</math> be the matrix with columns <math> v_1,\dots,v_m </math>. Let <math>T = \begin{pmatrix}
	\alpha_1 & \beta_2 & & & & 0 \\		\alpha_1 & \beta_2 & & & & 0 \\
Line 35:		Line 35:
	0 & & & & \beta_m & \alpha_m \\		0 & & & & \beta_m & \alpha_m \\
	\end{pmatrix}</math>.		\end{pmatrix}</math>.
	:'''Note''' <math> A v_j ~~= w_j'~~ = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 2 < j < m </math>.		:'''Note''' <math> A v_j = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 2 < j < m </math>.

	There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book\|last1=Cullum \|last2= Willoughby\|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations\|year= 1985\|volume= 1\| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book\|author=Yousef Saad\|title=Numerical Methods for Large Eigenvalue Problems\| isbn= 0-470-21820-7\|url= http://www-users.cs.umn.edu/~saad/books.html\|author-link=Yousef Saad\|date=1992-06-22}}</ref>		There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book\|last1=Cullum \|last2= Willoughby\|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations\|year= 1985\|volume= 1\| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book\|author=Yousef Saad\|title=Numerical Methods for Large Eigenvalue Problems\| isbn= 0-470-21820-7\|url= http://www-users.cs.umn.edu/~saad/books.html\|author-link=Yousef Saad\|date=1992-06-22}}</ref>

AaronAegeus: Separated paragraphs

2024-05-15T09:57:22Z

Separated paragraphs

← Previous revision		Revision as of 09:57, 15 May 2024
Line 46:		Line 46:

	=== Application to the eigenproblem ===		=== Application to the eigenproblem ===
	The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition. If <math>\lambda</math> is an eigenvalue of <math>T</math>, and <math>x</math> its eigenvector (<math>Tx=\lambda x</math>), then <math> y = V x </math> is a corresponding eigenvector of <math>A</math> with the same eigenvalue:		The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition.

			If <math>\lambda</math> is an eigenvalue of <math>T</math>, and <math>x</math> its eigenvector (<math>Tx=\lambda x</math>), then <math> y = V x </math> is a corresponding eigenvector of <math>A</math> with the same eigenvalue:

	<math display=block>\begin{align} A y &= A V x \\ &= V T V^* V x \\ &= V T I x \\ &= V T x \\ &= V (\lambda x) \\ &= \lambda V x \\& = \lambda y.\end{align}</math>		<math display=block>\begin{align} A y &= A V x \\ &= V T V^* V x \\ &= V T I x \\ &= V T x \\ &= V (\lambda x) \\ &= \lambda V x \\& = \lambda y.\end{align}</math>

AaronAegeus: Improved elucidation and changed formatting

2024-05-15T09:56:27Z

Improved elucidation and changed formatting

← Previous revision		Revision as of 09:56, 15 May 2024
Line 46:		Line 46:

	=== Application to the eigenproblem ===		=== Application to the eigenproblem ===
	The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition. If <math>\lambda</math> is an eigenvalue of <math>T</math>, and <math> T x = \lambda x </math> ~~the corresponding eigenvector~~, then <math> y = V x </math> is ~~the~~ corresponding eigenvector of <math>A</math> with the same eigenvalue: <math> A y = A V x = V T V^* V x = V T I x = V T x = V (\lambda x) = \lambda V x = \lambda y</math>. Thus the Lanczos algorithm transforms the eigendecomposition problem for <math>A</math> into the eigendecomposition problem for <math>T</math>.		The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition. If <math>\lambda</math> is an eigenvalue of <math>T</math>, and <math>x</math> its eigenvector (<math>Tx=\lambda x</math>), then <math> y = V x </math> is a corresponding eigenvector of <math>A</math> with the same eigenvalue:

			<math display=block>\begin{align} A y &= A V x \\ &= V T V^* V x \\ &= V T I x \\ &= V T x \\ &= V (\lambda x) \\ &= \lambda V x \\& = \lambda y.\end{align}</math>

			Thus the Lanczos algorithm transforms the eigendecomposition problem for <math>A</math> into the eigendecomposition problem for <math>T</math>.
	# For tridiagonal matrices, there exist a number of specialised algorithms, often with better computational complexity than general-purpose algorithms. For example, if <math>T</math> is an <math>m \times m</math> tridiagonal symmetric matrix then:		# For tridiagonal matrices, there exist a number of specialised algorithms, often with better computational complexity than general-purpose algorithms. For example, if <math>T</math> is an <math>m \times m</math> tridiagonal symmetric matrix then:
	#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.		#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.

AaronAegeus: Fixed an error in proof of eigencorrespondence and improved elaboration

2024-05-15T08:20:14Z

Fixed an error in proof of eigencorrespondence and improved elaboration

← Previous revision		Revision as of 08:20, 15 May 2024
Line 46:		Line 46:

	=== Application to the eigenproblem ===		=== Application to the eigenproblem ===
	The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition. If <math>\lambda</math> is an eigenvalue of <math>A</math>, and if <math> T x = \lambda x </math> ~~(<math>x</math>~~ ~~is an~~ eigenvector ~~of <math>T</math>)~~ then <math> y = V x </math> is the corresponding eigenvector of <math>A</math> ~~(since~~ <math> A y = A V x = V T V^* V x = V T I x = V T x = V (\lambda x) = \lambda V x = \lambda y</math>). Thus the Lanczos algorithm transforms the eigendecomposition problem for <math>A</math> into the eigendecomposition problem for <math>T</math>.		The Lanczos algorithm is most often brought up in the context of finding the [[eigenvalue]]s and [[eigenvector]]s of a matrix, but whereas an ordinary [[Matrix diagonalization\|diagonalization of a matrix]] would make eigenvectors and eigenvalues apparent from inspection, the same is not true for the tridiagonalization performed by the Lanczos algorithm; nontrivial additional steps are needed to compute even a single eigenvalue or eigenvector. Nonetheless, applying the Lanczos algorithm is often a significant step forward in computing the eigendecomposition. If <math>\lambda</math> is an eigenvalue of <math>T</math>, and <math> T x = \lambda x </math> the corresponding eigenvector, then <math> y = V x </math> is the corresponding eigenvector of <math>A</math> with the same eigenvalue: <math> A y = A V x = V T V^* V x = V T I x = V T x = V (\lambda x) = \lambda V x = \lambda y</math>. Thus the Lanczos algorithm transforms the eigendecomposition problem for <math>A</math> into the eigendecomposition problem for <math>T</math>.
	# For tridiagonal matrices, there exist a number of specialised algorithms, often with better computational complexity than general-purpose algorithms. For example, if <math>T</math> is an <math>m \times m</math> tridiagonal symmetric matrix then:		# For tridiagonal matrices, there exist a number of specialised algorithms, often with better computational complexity than general-purpose algorithms. For example, if <math>T</math> is an <math>m \times m</math> tridiagonal symmetric matrix then:
	#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.		#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.

Pwesterbaan: /* The algorithm */Changed 1
2023-12-15T05:22:12Z

The algorithm: Changed 1<j<m to 2<j<m since $\beta_1$ doesn't exist

← Previous revision Revision as of 05:22, 15 December 2023
Line 35: Line 35:

0 & & & & \beta_m & \alpha_m \\

0 & & & & \beta_m & \alpha_m \\

\end{pmatrix}</math>.

\end{pmatrix}</math>.

:'''Note''' <math> A v_j = w_j' = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 1 < j < m </math>.

:'''Note''' <math> A v_j = w_j' = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 2 < j < m </math>.

There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book|last1=Cullum |last2= Willoughby|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations|year= 1985|volume= 1| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book|author=Yousef Saad|title=Numerical Methods for Large Eigenvalue Problems| isbn= 0-470-21820-7|url= http://www-users.cs.umn.edu/~saad/books.html|author-link=Yousef Saad|date=1992-06-22}}</ref>

There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book|last1=Cullum |last2= Willoughby|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations|year= 1985|volume= 1| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book|author=Yousef Saad|title=Numerical Methods for Large Eigenvalue Problems| isbn= 0-470-21820-7|url= http://www-users.cs.umn.edu/~saad/books.html|author-link=Yousef Saad|date=1992-06-22}}</ref>

OAbot: Open access bot: doi updated in citation with #oabot.

2023-12-02T16:53:49Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 16:53, 2 December 2023
Line 50:		Line 50:
	#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.		#* The [[Tridiagonal matrix#Determinant\|continuant recursion]] allows computing the [[characteristic polynomial]] in <math>O(m^2)</math> operations, and evaluating it at a point in <math>O(m)</math> operations.
	#* The [[divide-and-conquer eigenvalue algorithm]] can be used to compute the entire eigendecomposition of <math>T</math> in <math>O(m^2)</math> operations.		#* The [[divide-and-conquer eigenvalue algorithm]] can be used to compute the entire eigendecomposition of <math>T</math> in <math>O(m^2)</math> operations.
	#* The Fast Multipole Method<ref>{{cite journal\|last1=Coakley\|first1=Ed S.\|last2=Rokhlin\|first2=Vladimir\|title=A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices\|journal=Applied and Computational Harmonic Analysis\|date=2013\|volume=34\|issue=3\|pages=379–414\|doi=10.1016/j.acha.2012.06.003\|doi-access=~~free~~}}</ref> can compute all eigenvalues in just <math>O(m \log m)</math> operations.		#* The Fast Multipole Method<ref>{{cite journal\|last1=Coakley\|first1=Ed S.\|last2=Rokhlin\|first2=Vladimir\|title=A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices\|journal=Applied and Computational Harmonic Analysis\|date=2013\|volume=34\|issue=3\|pages=379–414\|doi=10.1016/j.acha.2012.06.003\|doi-access=}}</ref> can compute all eigenvalues in just <math>O(m \log m)</math> operations.
	# Some general eigendecomposition algorithms, notably the [[QR algorithm]], are known to converge faster for tridiagonal matrices than for general matrices. Asymptotic complexity of tridiagonal QR is <math>O(m^2)</math> just as for the divide-and-conquer algorithm (though the constant factor may be different); since the eigenvectors together have <math>m^2</math> elements, this is asymptotically optimal.		# Some general eigendecomposition algorithms, notably the [[QR algorithm]], are known to converge faster for tridiagonal matrices than for general matrices. Asymptotic complexity of tridiagonal QR is <math>O(m^2)</math> just as for the divide-and-conquer algorithm (though the constant factor may be different); since the eigenvectors together have <math>m^2</math> elements, this is asymptotically optimal.
	# Even algorithms whose convergence rates are unaffected by unitary transformations, such as the [[power method]] and [[inverse iteration]], may enjoy low-level performance benefits from being applied to the tridiagonal matrix <math>T</math> rather than the original matrix <math>A</math>. Since <math>T</math> is very sparse with all nonzero elements in highly predictable positions, it permits compact storage with excellent performance vis-à-vis [[Cache (computing)\|caching]]. Likewise, <math>T</math> is a [[real number\|real]] matrix with all eigenvectors and eigenvalues real, whereas <math>A</math> in general may have complex elements and eigenvectors, so real arithmetic is sufficient for finding the eigenvectors and eigenvalues of <math>T</math>.		# Even algorithms whose convergence rates are unaffected by unitary transformations, such as the [[power method]] and [[inverse iteration]], may enjoy low-level performance benefits from being applied to the tridiagonal matrix <math>T</math> rather than the original matrix <math>A</math>. Since <math>T</math> is very sparse with all nonzero elements in highly predictable positions, it permits compact storage with excellent performance vis-à-vis [[Cache (computing)\|caching]]. Likewise, <math>T</math> is a [[real number\|real]] matrix with all eigenvectors and eigenvalues real, whereas <math>A</math> in general may have complex elements and eigenvectors, so real arithmetic is sufficient for finding the eigenvectors and eigenvalues of <math>T</math>.

Macrakis: more useful short description

2023-06-30T21:18:56Z

more useful short description

← Previous revision		Revision as of 21:18, 30 June 2023
Line 1:		Line 1:
	{{Short description\|~~Iterative~~ ~~numerical~~ ~~method~~}}		{{Short description\|Numerical eigenvalue calculation}}
	{{for\|the null space-finding algorithm\|block Lanczos algorithm}}		{{for\|the null space-finding algorithm\|block Lanczos algorithm}}
	{{for\|the interpolation method\|Lanczos resampling}}		{{for\|the interpolation method\|Lanczos resampling}}

MichaelMaggs: Adding local short description: "Iterative numerical method", overriding Wikidata description "numerical method for find eigenvalues"

2023-06-30T19:48:43Z

Adding local short description: "Iterative numerical method", overriding Wikidata description "numerical method for find eigenvalues"

← Previous revision		Revision as of 19:48, 30 June 2023
Line 1:		Line 1:
			{{Short description\|Iterative numerical method}}
	{{for\|the null space-finding algorithm\|block Lanczos algorithm}}		{{for\|the null space-finding algorithm\|block Lanczos algorithm}}
	{{for\|the interpolation method\|Lanczos resampling}}		{{for\|the interpolation method\|Lanczos resampling}}

LongingLament: /* A more provident power method */ Fix a typo

2023-04-03T17:59:30Z

A more provident power method: Fix a typo

← Previous revision		Revision as of 17:59, 3 April 2023
Line 76:		Line 76:
	:## Let <math> u_{j+1} = u_{j+1}' / \\| u_{j+1}' \\|.</math>		:## Let <math> u_{j+1} = u_{j+1}' / \\| u_{j+1}' \\|.</math>
	:* In the large <math>j</math> limit, <math>u_j</math> approaches the normed eigenvector corresponding to the largest magnitude eigenvalue.		:* In the large <math>j</math> limit, <math>u_j</math> approaches the normed eigenvector corresponding to the largest magnitude eigenvalue.
	A critique that can be raised against this method is that it is wasteful: it spends a lot of work (the matrix–vector products in step 2.1) extracting information from the matrix <math>A</math>, but pays attention only to the very last result; implementations typically use the same variable for all the vectors <math>u_j</math>, having each new iteration overwrite the results from the previous one. It may be desirable to instead ~~keeptl~~ all the intermediate results and organise the data.		A critique that can be raised against this method is that it is wasteful: it spends a lot of work (the matrix–vector products in step 2.1) extracting information from the matrix <math>A</math>, but pays attention only to the very last result; implementations typically use the same variable for all the vectors <math>u_j</math>, having each new iteration overwrite the results from the previous one. It may be desirable to instead keep all the intermediate results and organise the data.

	One piece of information that trivially is available from the vectors <math>u_j</math> is a chain of [[Krylov subspace]]s. One way of stating that without introducing sets into the algorithm is to claim that it computes		One piece of information that trivially is available from the vectors <math>u_j</math> is a chain of [[Krylov subspace]]s. One way of stating that without introducing sets into the algorithm is to claim that it computes

Cond-mat: added further reading

2023-03-20T08:52:27Z

added further reading

← Previous revision		Revision as of 08:52, 20 March 2023
Line 298:		Line 298:
	* {{cite book \|first1=Gene H. \|last1=Golub \|author-link=Gene H. Golub \|first2=Charles F. \|last2=Van Loan \|author-link2=Charles F. Van Loan \|title=Matrix Computations \|location=Baltimore \|publisher=Johns Hopkins University Press \|year=1996 \|isbn=0-8018-5414-8 \|pages=470–507 \|chapter=Lanczos Methods \|chapter-url=https://books.google.com/books?id=mlOa7wPX6OYC&pg=PA470 }}		* {{cite book \|first1=Gene H. \|last1=Golub \|author-link=Gene H. Golub \|first2=Charles F. \|last2=Van Loan \|author-link2=Charles F. Van Loan \|title=Matrix Computations \|location=Baltimore \|publisher=Johns Hopkins University Press \|year=1996 \|isbn=0-8018-5414-8 \|pages=470–507 \|chapter=Lanczos Methods \|chapter-url=https://books.google.com/books?id=mlOa7wPX6OYC&pg=PA470 }}
	* {{cite journal \|first1=Andrew Y. \|last1=Ng \|author-link=Andrew Ng \|first2=Alice X. \|last2=Zheng \|first3=Michael I. \|last3=Jordan \|author-link3=Michael I. Jordan \|title=Link Analysis, Eigenvectors and Stability \|journal=IJCAI'01 Proceedings of the 17th International Joint Conference on Artificial Intelligence \|volume=2 \|pages=903–910 \|date=2001 \|url=https://ai.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf }}		* {{cite journal \|first1=Andrew Y. \|last1=Ng \|author-link=Andrew Ng \|first2=Alice X. \|last2=Zheng \|first3=Michael I. \|last3=Jordan \|author-link3=Michael I. Jordan \|title=Link Analysis, Eigenvectors and Stability \|journal=IJCAI'01 Proceedings of the 17th International Joint Conference on Artificial Intelligence \|volume=2 \|pages=903–910 \|date=2001 \|url=https://ai.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf }}
			* {{cite book\|author=Erik Koch\|chapter-url=http://www.cond-mat.de/events/correl19/manuscripts/koch.pdf\|chapter=Exact Diagonalization and Lanczos Method\|editor1= E. Pavarini \|editor2=E. Koch \|editor3=S. Zhang \|title= Many-Body Methods for Real Materials\|publisher= Jülich \|year=2019\|isbn=978-3-95806-400-3}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

← Previous revision		Revision as of 21:18, 30 June 2023
Line 1:		Line 1:
	{{Short description\|~~Iterative~~ ~~numerical~~ ~~method~~}}		{{Short description\|Numerical eigenvalue calculation}}
	{{for\|the null space-finding algorithm\|block Lanczos algorithm}}		{{for\|the null space-finding algorithm\|block Lanczos algorithm}}
	{{for\|the interpolation method\|Lanczos resampling}}		{{for\|the interpolation method\|Lanczos resampling}}

← Previous revision		Revision as of 19:48, 30 June 2023
Line 1:		Line 1:
			{{Short description\|Iterative numerical method}}
	{{for\|the null space-finding algorithm\|block Lanczos algorithm}}		{{for\|the null space-finding algorithm\|block Lanczos algorithm}}
	{{for\|the interpolation method\|Lanczos resampling}}		{{for\|the interpolation method\|Lanczos resampling}}

← Previous revision		Revision as of 05:22, 15 December 2023
Line 35:		Line 35:
	0 & & & & \beta_m & \alpha_m \\		0 & & & & \beta_m & \alpha_m \\
	\end{pmatrix}</math>.		\end{pmatrix}</math>.
	:'''Note''' <math> A v_j = w_j' = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 1 < j < m </math>.		:'''Note''' <math> A v_j = w_j' = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> for <math> 2 < j < m </math>.

	There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book\|last1=Cullum \|last2= Willoughby\|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations\|year= 1985\|volume= 1\| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book\|author=Yousef Saad\|title=Numerical Methods for Large Eigenvalue Problems\| isbn= 0-470-21820-7\|url= http://www-users.cs.umn.edu/~saad/books.html\|author-link=Yousef Saad\|date=1992-06-22}}</ref>		There are in principle four ways to write the iteration procedure. Paige and other works show that the above order of operations is the most numerically stable.<ref name="CW1985">{{Cite book\|last1=Cullum \|last2= Willoughby\|title=Lanczos Algorithms for Large Symmetric Eigenvalue Computations\|year= 1985\|volume= 1\| isbn= 0-8176-3058-9}}</ref><ref name="Saad1992">{{Cite book\|author=Yousef Saad\|title=Numerical Methods for Large Eigenvalue Problems\| isbn= 0-470-21820-7\|url= http://www-users.cs.umn.edu/~saad/books.html\|author-link=Yousef Saad\|date=1992-06-22}}</ref>