Lanczos algorithm

Summary

The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the m "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an n \times n Hermitian matrix, where m is often but not necessarily much smaller than n . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability. In 1970, Ojalvo and Newman showed how to make the method numerically stable and applied it to the solution of very large engineering structures subjected to dynamic loading. This was achieved using a method for purifying the Lanczos vectors (i.e. by repeatedly reorthogonalizing each newly generated vector with all previously generated ones) to any degree of accuracy, which when not performed, produced a series of vectors that were highly contaminated by those associated with the lo

Official source

https://en.wikipedia.org/wiki/Lanczos_algorithm

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (12)

Related publications

Related people (1)

Related people

Related units (1)

Related units

Related concepts (13)

In numerical analysis, 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

In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix A, the algorithm will produce a number \lambda, wh

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of g

Related concepts

Related courses (1)

Related courses

Related lectures (1)

Related lectures

Recompression Of Hadamard Products Of Tensors In Tucker Format

Daniel Kressner, Lana Perisa

The Hadamard product features prominently in tensor-based algorithms in scientific computing and data analysis. Due to its tendency to significantly increase ranks, the Hadamard product can represent a major computational obstacle in algorithms based on low-rank tensor representations. It is therefore of interest to develop recompression techniques that mitigate the effects of this rank increase. In this work, we investigate such techniques for the case of the Tucker format, which is well suited for tensors of low order and small to moderate multilinear ranks. Fast algorithms are attained by combining iterative methods, such as the Lanczos method and randomized algorithms, with fast matrix-vector products that exploit the structure of Hadamard products. The resulting complexity reduction is particularly relevant for tensors featuring large mode sizes I and small to moderate multilinear ranks R. To implement our algorithms, we have created a new Julia library for tensors in Tucker format.

Siam Publications2017

, ,

The ground state and zero-temperature magnetization process of the spin-1/2 Ising-Heisenberg model on two-dimensional triangles-in-triangles lattices are exactly calculated using eigenstates of the smallest commuting spin clusters. Our ground-state analysis of the investigated classical-quantum spin model reveals three unconventional dimerized or trimerized quantum ground states besides two classical ground states. It is demonstrated that the spin frustration is responsible for a variety of magnetization scenarios with up to three or four intermediate magnetization plateaus of either quantum or classical nature. The exact analytical results for the Ising-Heisenberg model are confronted with the corresponding results for the purely quantum Heisenberg model, which were obtained by numerical exact diagonalizations based on the Lanczos algorithm for finite-size spin clusters of 24 and 21 sites, respectively. It is shown that the zero-temperature magnetization process of both models is quite reminiscent, and hence, one may obtain some insight into the ground states of the quantum Heisenberg model from the rigorous results for the Ising-Heisenberg model even though exact ground states for the Ising-Heisenberg model do not represent true ground states for the pure quantum Heisenberg model. DOI: 10.1103/PhysRevB.87.054419

2013

Accelerated filtering on graphs using Lanczos method

Daniel Kressner, Nathanaël Perraudin, Ana Susnjara, Pierre Vandergheynst

Signal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames constructed from graphs, like wavelets on graphs, has substantially increased. To attain scalability for large graphs, fast graph-signal filtering techniques are needed. In this contribution, we propose an accelerated algorithm based on the Lanczos method that adapts to the Laplacian spectrum without explicitly computing it. The result is an accurate, robust, scalable and efficient algorithm. Compared to existing methods based on Chebyshev polynomials, our solution achieves higher accuracy without increasing the overall complexity significantly. Furthermore, it is particularly well suited for graphs with large spectral gaps.

Institute of Electrical and Electronics Engineers