Lanczos Algorithm

Le référentiel suivant contient une implémentation de l'algorithme Lanczos standard.

Installation

Pour jouer avec l'algorithme vous-même, git clone le référentiel sur votre machine locale. Ensuite, dans le répertoire cloné, initialisez l'environnement conda en fonctionnant

 conda env create --file environment.yml

De là, vous pouvez activer l'environnement comme ainsi

 conda activate LanczosAlgo

et exécutez le cahier dans src/lanczos.ipynb .

Introduction

L'algorithme Lanczos est un algorithme direct conçu par Cornelius Lanczos qui est une adaptation des méthodes de puissance pour trouver le $ m $ "les plus utiles" (tendant vers l'extrême les plus élevés / les plus bas) les valeurs propres et les vecteurs propres d'un $ n Times n $ Matrice hermitienne, où $ m $ est souvent mais pas nécessairement beaucoup plus petit que $ n $ .

Algorithme

L'algorithme se déroule comme suit:

1. Étant donné une matrice hermitienne $ A $ de taille $ n Times n $ et un vecteur arbitraire $ v_1 $ Avec la norme euclidienne 1, spécifiez un nombre par défaut d'appels de fonction $ m = n $
2. Laisser $ w_1 '$ = $ Av_1 $
3. Laisser $ alpha_1 = w_1 '^ * v_1 $
4. Laisser $ w_1 = w_1 '^ * - alpha_1 v_1 $

Nous appelons les étapes 2 à 4 comme les premières étapes d'itération. Ensuite,

5. Laisser $ beta_j = || w_ {j-1} || $
6. Si $ beta_j neq0 $ , laisser $ v_j = frac {w_ {j-1}} { beta_j} $ . Sinon, laissez $ v_j $ être un vecteur arbitraire avec la norme 1 euclidienne 1 qui est orthogonale à $ v_1, ..., v_ {j-1} $
7. Laisser $ w_j '= av_j $
8. Laisser $ alpha_j = w_j'v_j $
9. Laisser $ w_j = w_j '- alpha_j v_j- beta_j v_ {j-1} $

où $ j $ indique le numéro d'itération et doit satisfaire 2 $ leq j leq m $ . Enfin, la sortie est une matrice tridiagonalisée $ T $ avec $ alpha_1, ..., alpha_m $ le long de la diagonale principale, et $ beta_2, ..., beta_m $ le long des super- et subagonales.

Travail futur

Des efforts sont actuellement en cours pour étendre l'algorithme pour inclure des systèmes à l'état de diffusion. Jouez ce dépôt si vous souhaitez être averti quand cela sera mis en ligne!