Algorithme de Lanczos

Résumé

En algèbre linéaire, l’algorithme de Lanczos (ou méthode de Lanczos) est un algorithme itératif pour déterminer les valeurs et vecteurs propres d'une matrice carrée, ou la décomposition en valeurs singulières d'une matrice rectangulaire. Cet algorithme n'a pas de lien avec le fenêtrage de Lanczos (utilisé par exemple pour le redimensionnement d'images), si ce n'est que tous les deux tirent leur nom du même inventeur, le physicien et mathématicien hongrois Cornelius Lanczos. Description de l'algorithme Méthode de la puissance itérée La méthode de la puissance itérée pour trouver la plus grande valeur propre d'une matrice carrée symétrique A, d'ordre p est la suivante. Si x_0 est un vecteur et x_{n+1} = A x_n, alors x_n = A^n x_0. On sait qu'une matrice symétrique est diagonalisable, et les termes \sigma_i , i=1...p de la matrice diagonale sont les valeurs propres de la matrice. Soit donc

Source officielle

https://fr.wikipedia.org/wiki/Algorithme_de_Lanczos

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (12)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (13)

Un problème important en analyse numérique consiste à développer des algorithmes efficaces et stables pour trouver les valeurs propres d'une matrice. Ces algorithmes de recherche de valeurs propres p

En mathématiques, la méthode de la puissance itérée ou méthode des puissances est un algorithme pour calculer la valeur propre dominante d'une matrice. Bien que cet algorithme soit simple à mettre en

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

Afficher plus

Concepts associés

Chargement

Cours associés (1)

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees, describe scalable solution techniques and algorithms, and illustrate the trade-offs involved.

Cours associés

Chargement

Séances de cours associées (1)

Séances de cours associées

Chargement

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

Chargement

, ,

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

Chargement

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

Chargement