Lanczos Algorithm

O repositório a seguir contém uma implementação do algoritmo Lanczos padrão.

Instalação

Para brincar com o algoritmo você mesmo, git clone o repositório na máquina local. Em seguida, no diretório clonado, inicialize o ambiente do CONDA executando

 conda env create --file environment.yml

A partir daí, você pode ativar o ambiente como assim

 conda activate LanczosAlgo

e execute o notebook em src/lanczos.ipynb .

Introdução

O algoritmo de Lanczos é um algoritmo direto criado por Cornelius Lanczos, que é uma adaptação de métodos de poder para encontrar o $ m $ "mais útil" (tendendo a mais altos/mais baixos) valores próprios e autovetores de um $ n times n $ Matriz hermitiana, onde $ m $ geralmente é, mas não necessariamente muito menor do que $ n $ .

Algoritmo

O algoritmo prossegue o seguinte:

1. Dado uma matriz hermitiana $ A $ de tamanho $ n times n $ , e um vetor arbitrário $ v_1 $ Com a norma euclidiana 1, especifique um número padrão de chamadas de função $ m = n $
2. Deixar $ w_1 '$ = $ AV_1 $
3. Deixar $ alpha_1 = w_1 '^* v_1 $
4. Deixar $ w_1 = w_1 '^*- alpha_1 v_1 $

Nós nos referimos às etapas 2 - 4 como as primeiras etapas de iteração. Posteriormente,

5. Deixar $ beta_j = || w_ {j-1} || $
6. Se $ beta_j neq0 $ , deixar $ v_j = frac {w_ {j-1}} { beta_j} $ . Caso contrário, deixe $ v_j $ ser um vetor arbitrário com norma euclidiana 1 que é ortogonal para $ v_1, ..., v_ {j-1} $
7. Deixar $ w_j '= av_j $
8. Deixar $ alpha_j = w_j'v_j $
9. Deixar $ w_j = w_j '- alpha_j v_j- beta_j v_ {j-1} $

onde $ j $ denota o número de iteração e deve satisfazer $ 2 LEQ J LEQ M $ . Finalmente, a saída é uma matriz tridiagonalizada $ T $ com $ alpha_1, ..., alpha_m $ ao longo da diagonal principal e $ beta_2, ..., beta_m $ ao longo dos super e subdiagonais.

Trabalho futuro

Atualmente, estão os esforços para estender o algoritmo para incluir sistemas de estado de dispersão. Estrela este repo se você quiser ser notificado quando isso for ao ar!