Méthode de la puissance itérée

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 œuvre et populaire, il ne converge pas très vite. Calcul de valeurs propres Étant donné une matrice A, on cherche une valeur propre de plus grand module et un vecteur propre associé. Le calcul de valeurs propres n'est en général pas possible directement (avec une formule close) : on utilise alors des méthodes itératives, et la méthode des puissances est la plus simple d'entre elles. Algorithme La méthode repose sur le théorème suivant, s'appuyant sur la réduction de Jordan. Convergence Lorsque les multiplicités algébriques et géométriques associées à la valeur propre λ sont égales, le taux de convergence de l'algorithme se comporte en O\left(|\lambda_2/\lambda_1|^n\right), où λ et λ sont la plus grande et la seconde plus grande valeurs prop

À 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 (9)

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (10)

Concepts associés

Chargement

Cours associés (10)

Cours associés

Chargement

Séances de cours associées (25)

Séances de cours associées

Chargement

MATH-456: Numerical analysis and computational mathematics

The course provides an introduction to scientific computing. Several numerical methods are presented for the computer solution of mathematical problems arising in different applications. The software MATLAB is used to solve the problems and verify the theoretical properties of the numerical methods.

PHYS-460: Nonlinear dynamics, chaos and complex systems

The course provides students with the tools to approach the study of nonlinear systems and chaotic dynamics. Emphasis is given to concrete examples and numerical applications are carried out during the exercise sessions.

EE-556: Mathematics of data: from theory to computation

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.

Robust Differentiable SVD

Zheng Dang, Pascal Fua, Yinlin Hu, Mathieu Salzmann, Wei Wang

Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. However, the derivatives of the eigenvectors tend to be numerically unstable, whether using the SVD to compute them analytically or using the Power Iteration (PI) method to approximate them. This instability arises in the presence of eigenvalues that are close to each other. This makes integrating eigendecomposition into deep networks difficult and often results in poor convergence, particularly when dealing with large matrices. While this can be mitigated by partitioning the data into small arbitrary groups, doing so has no theoretical basis and makes it impossible to exploit the full power of eigendecomposition. In previous work, we mitigated this using SVD during the forward pass and PI to compute the gradients during the backward pass. However, the iterative deflation procedure required to compute multiple eigenvectors using PI tends to accumulate errors and yield inaccurate gradients. Here, we show that the Taylor expansion of the SVD gradient is theoretically equivalent to the gradient obtained using PI without relying in practice on an iterative process and thus yields more accurate gradients. We demonstrate the benefits of this increased accuracy for image classification and style transfer.

2021

Chargement

PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization

Martin Jaggi, Thijs Vogels

We study lossy gradient compression methods to alleviate the communication bottleneck in data-parallel distributed optimization. Despite the significant attention received, current compression schemes either do not scale well, or fail to achieve the target test accuracy. We propose a new low-rank gradient compressor based on power iteration that can i) compress gradients rapidly, ii) efficiently aggregate the compressed gradients using all-reduce, and iii) achieve test performance on par with SGD. The proposed algorithm is the only method evaluated that achieves consistent wall-clock speedups when benchmarked against regular SGD using highly optimized off-the-shelf tools for distributed communication. We demonstrate reduced training times for convolutional networks as well as LSTMs on common datasets. Our code is available at https://github.com/epfml/powersgd.

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Chargement

Multi Space Reduced Basis Preconditioners for Large-Scale Parametrized PDEs

Niccolò Dal Santo, Simone Deparis, Andrea Manzoni, Alfio Quarteroni

In this work we introduce a new two-level preconditioner for the efficient solution of large-scale linear systems arising from the discretization of parametrized PDEs. The proposed preconditioner combines in a multiplicative way a reduced basis solver, which plays the role of coarse component, and a “traditional” fine-grid preconditioner, such as one-level additive Schwarz, block Gauss--Seidel, or block Jacobi preconditioners. The coarse component is built upon a new multi space reduced basis (MSRB) method that we introduce for the first time in this paper, where a reduced basis space is built through the proper orthogonal decomposition algorithm at each step of the iterative method at hand, like the flexible GMRES method. MSRB strategy consists in building reduced basis spaces that are well suited to perform a single iteration, by addressing the error components which have not been treated yet. The Krylov iterations employed to solve the resulting preconditioned system target small tolerances with a very small iteration count and in a very short time, showing good optimality and scalability properties. Simulations are carried out to evaluate the performance of the proposed preconditioner in different large-scale computational settings related to parametrized advection diffusion equations and compared with the current state-of-the-art algebraic multigrid preconditioners. Read More: https://epubs.siam.org/doi/abs/10.1137/16M1089149

Chargement

Valeur propre, vecteur propre et espace propre

En mathématiques, et plus particulièrement en algèbre linéaire, le concept de vecteur propre est une notion algébrique s'appliquant à une application linéaire d'un espace dans lui-même. Il correspon

Algorithme de recherche de valeur propre

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

Algorithme de Lanczos

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 si