Lanczos algorithm

Lanczos algorithm

The Lanczos algorithm is an iterative algorithm invented by Cornelius Lanczos that is an adaptation of power methods to find eigenvalues and eigenvectors of a square matrix or the singular value decomposition of a rectangular matrix. It is particularly useful for finding decompositions of very large sparse matrices. In Latent Semantic Indexing, for instance, matrices relating millions of documents to hundreds of thousands of terms must be reduced to singular value form.

Peter Montgomery published in 1995 an algorithm, based on the Lanczos algorithm, for finding elements of the nullspace of a large sparse matrix over GF(2); since the set of people interested in large sparse matrices over finite fields and the set of people interested in large eigenvalue problems scarcely overlap, this is often also called the "block Lanczos algorithm" without causing unreasonable confusion. See Block Lanczos algorithm for nullspace of a matrix over a finite field.

Power method for finding eigenvalues

The power method for finding the largest eigenvalue of a matrix A, can be summarized by noting that if x_0, is a random vector and x_{n+1} = A x_n,, then in the large n limit, x_n/||x_n|| approaches the eigenvector corresponding to the largest eigenvalue.

If A = U operatorname{diag}(sigma_i) U' , is the eigenvalue decomposition of A,, then A^n = U operatorname{diag}(sigma_i^n) U'. As n, gets very large, the diagonal matrix of eigenvalues will be dominated by whichever eigenvalue is largest (neglecting the case where there are large equal eigenvalues, of course). As this happens, |x_{n+1}| / |x_{n}|, will converge to the largest eigenvalue and x_n / |x_n|, to the associated eigenvector. If the largest eigenvalue is multiple, then x_n , will converge to a vector in the subspace spanned by the eigenvectors associated with those largest eigenvalues. After you get the first eigenvector/value, you can successively restrict the algorithm to the null space of the known eigenvectors to get the other eigenvector/values.

In practice, this simple algorithm does not work very well for computing very many of the eigenvectors because any round-off error will tend to introduce slight components of the more significant eigenvectors back into the computation, degrading the accuracy of the computation. Pure power methods also can converge slowly, even for the first eigenvector.

Lanczos method

During the procedure of applying the power method, while getting the ultimate eigenvector A^{n-1} v, we also got a series of vectors A^j v, , j=0,1,cdots,n-2 which were eventually discarded. That is clearly a huge waste. Some advanced algorithms, such as Arnoldi's algorithm and the Lanczos algorithm save this information and use the Gram–Schmidt process or Householder algorithm to reorthogonalize them into a basis spanning the Krylov subspace corresponding to the matrix A.

The algorithm

The Lanczos algorithm can be viewed as a simplified Arnoldi's algorithm in that it applies to Hermitian matrices. It transforms the original matrix into a tridiagonal matrix which is real and symmetric.

Definitions

We hope to calculate the tridiagonal and symmetric matrix H_{mm} = V_m^* A V_m.

The diagonal elements are denoted by alpha_j = h_{jj}, and the off-diagonal elements are denoted by eta_j = h_{j-1,j} .

Note that h_{j-1,j} = h_{j,j-1} , due to its symmetry.

Iteration

(Note: Following these steps alone will not give you the correct eigenvalue and eigenvectors. More consideration must be applied to correct for the numerical errors. See the section Numerical stability in the following.)

There are in principle four ways to write the iteration procedure. Paige [1972] and other works show that the following procedure is the most numerically stable. [Cullum and Willoughby, "Lanczos Algorithms for Large Symmetric Eigenvalue Computations", Vol. 1, ISBN 0-8176-3058-9(v.1)] [Yousef Saad, "Numerical Methods for Large Eigenvalue Problems", ISBN 0-470-21820-7, http://www-users.cs.umn.edu/~saad/books.html]

v_1 leftarrow random vector with norm 1. v_0 leftarrow 0 eta_1 leftarrow 0 Iteration: for j = 1,2,cdots,m w_j leftarrow A v_j - eta_j v_{j-1} alpha_j leftarrow (w_j, v_j) w_j leftarrow w_j - alpha_j v_j eta_{j+1} leftarrow left| w_j ight| v_{j+1} leftarrow w_j / eta_{j+1} return

Note that (x,y) represents the dot product of vectors x and y here.

After the iteration, we get the alpha_j and eta_j which constructs a tridiagonal matrix

T_{mm} = left( egin{array}{ccccccc}alpha_1 & eta_2 & 0 & 0 & cdots & 0 & 0 \eta_2 & alpha_2 & eta_3 & 0 & cdots & 0 & 0 \0 & eta_3 & alpha_3 & eta_4 & cdots & 0 & 0 \vdots & vdots & vdots & vdots & vdots & vdots & vdots \0 & 0 & 0 & 0 & cdots & alpha_{m-1} & eta_m \0 & 0 & 0 & 0 & cdots & eta_m & alpha_m \end{array} ight)

The vectors v_j (Lanczos vectors) generated on the fly constructs the transformation matrix

V_m = left( v_1, v_2, cdots, v_m ight),

which is useful for calculating the eigenvectors (see below). In practice, it could be saved after generation (but takes a lot of memory), or could be regenerated when needed, as long as one keeps the first vector v_1.

olve for eigenvalue and eigenvectors

After the matrix T_{mm} is calculated, one can solve its eigenvalues lambda_i^{(m)} and their corresponding eigenvectors u_i^{(m)}. This process is pretty simple due to the nature of T being a tridiagonal matrix.

It can be proved that the eigenvalues are approximate eigenvalues of the original matrix A.

The Ritz eigenvectors y_i of A can be calculated by y_i = V_m u_i^{(m)}, where V_m is the transformation matrix whose column vectors are v_1, v_2, cdots, v_m.

Numerical stability

Stability means how much the algorithm will be affected (i.e. will it produce the approximate result close to the original one) if there are small numerical errors introduced and accumulated. Numerical stability is the central criterion for judging the usefulness of implementing an algorithm on a computer with roundoff.

For the Lanczos algorithm, it can be proved that with "exact arithmetic", the set of vectors v_1, v_2, cdots, v_{m+1} constructs an "orthogonal" basis, and the eigenvalues/vectors solved are good approximations to those of the original matrix. However, in practice (as we code it on to digital computers where round-off errors are inevitable), the orthogonality is quickly lost and in some cases the new vector could even be linearly dependent on the set that is already constructed. As a result, some of the eigenvalues of the resultant tridiagonal matrix may not be approximations to the original matrix. Therefore, the Lanczos algorithm is not very stable.

Users of this algorithm must be able to find and remove those "spurious" eigenvalues. Practical implementations of the Lanczos algorithm go in three directions to fight this stability issue:
# Prevent the loss of orthogonality
# Recover the orthogonality after the basis is generated
# After the good and "spurious" eigenvalues are all identified, remove the spurious ones.

Variations

Variations on the Lanczos algorithm exist where the vectors involved are tall, narrow matrices instead of vectors and the normalizing constants are small square matrices. These are called "block" Lanczos algorithms and can be much faster on computers with large numbers of registers and long memory fetch times.

Many implementations of the Lanczos algorithm restart after a certain number of iterations. One of the most influential restarted variations is the implicitly restarted Lanczos method [cite web |author=D. Calvetti, L. Reichel, and D.C. Sorensen |date=1994 |title=An Implicitly Restarted Lanczos Method for Large Symmetric Eigenvalue Problems |publisher=ETNA |url=http://etna.mcs.kent.edu/vol.2.1994/pp1-21.dir/pp1-21.ps] , which is implemented in ARPACK [cite web |author=R. B. Lehoucq, D. C. Sorensen, and C. Yang |date=1998 |title=ARPACK Users Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods |publisher=SIAM |url=http://www.ec-securehost.com/SIAM/SE06.html ] . This has led into a number of other restarted variations such as restarted Lanczos bidiagonalization [cite web |author=E. Kokiopoulou and C. Bekas and E. Gallopoulos |date=2004 |title=Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization |publisher=Appl. Numer. Math. |url=http://dx.doi.org/10.1016/j.apnum.2003.11.011] . Another successful restarted variation is the Thick-Restart Lanczos method [cite web |author=Kesheng Wu and Horst Simon |date=2000 |title=Thick-Restart Lanczos Method for Large Symmetric Eigenvalue Problems |publisher=SIAM |url=http://dx.doi.org/10.1137/S0895479898334605 ] , which has been implemented in a software package called TRLan [cite web |author=Kesheng Wu and Horst Simon |date=2001 |title=TRLan software package |publisher= |url=http://crd.lbl.gov/~kewu/trlan.html ] .

Applications

Lanczos algorithms are very attractive because the multiplication by A, is the only large scale linear operation. Since weighted-term text retrieval engines implement just this operation, the Lanczos algorithm can be applied efficiently to text documents (see Latent Semantic Indexing). Eigenvectors are also important for the analysis of other large scale text retrieval methods such as the HITS algorithm from IBM, or the PageRank algorithm used at one time by Google.

References

External links

* [http://books.google.com/books?vid=ISBN0801854148 Golub and van Loan give very good descriptions of the various forms of Lanczos algorithms in their book "Matrix Computations"]
* [http://ai.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf Andrew Ng et al., an analysis of PageRank]
* [http://www.farcaster.com/papers/crypto-solve/node3.html Lanczos and conjugate gradient methods] B. A. LaMacchia and A. M. Odlyzko, Solving Large Sparse Linear Systems Over Finite Fields


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Block Lanczos algorithm for nullspace of a matrix over a finite field — The Block Lanczos algorithm for nullspace of a matrix over a finite field is a procedure for finding the nullspace of a matrix using only multiplication of the matrix by long, thin matrices. These long, thin matrices are considered as vectors of… …   Wikipedia

  • Lanczos resampling — ( Lanzosh ) is a multivariate interpolation method used to compute new values for any digitally sampled data. It is often used to resize digital images, but could be used for any other digital signal. In the case of digital image resizing, the… …   Wikipedia

  • Cornelius Lanczos — Lanczos redirects here. For resampling method, see Lanczos resampling. Cornelius Lanczos Born February 2, 1893(1893 02 02) Székesfehérvár Died …   Wikipedia

  • Algorithme De Lanczos — En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos. En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de… …   Wikipédia en Français

  • Algorithme de lanczos — En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos. En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de… …   Wikipédia en Français

  • Algorithme de Lanczos — En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos. En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de… …   Wikipédia en Français

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… …   Wikipedia

  • Eigenvalue algorithm — In linear algebra, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors. Contents 1 Characteristic polynomial 2 Power… …   Wikipedia

  • Maurice Clint — was professor of Computer Science at Queen s University Belfast, Northern Ireland. His research interests include parallel algorithms for numerical linear algebra and the use of formal methods in the development of parallel and distributed… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”