Algorisme de Lanczos

L'algorisme de Lanczos és un mètode iteratiu ideat per Cornelius Lanczos que és una adaptació de mètodes de potència per trobar el $m$ "més útils" (tenent cap a l'extrem més alt/mínim) valors propis i vectors propis d'un $n\times n$ matriu hermitiana, on $m$ sovint, però no necessàriament, és molt més petit que $n$. Encara que en principi computacionalment eficient, el mètode tal com es va formular inicialment no va ser útil, a causa de la seva inestabilitat numèrica.

El 1970, Ojalvo i Newman van mostrar com fer el mètode numèricament estable i el van aplicar a la solució d'estructures d'enginyeria molt grans sotmeses a càrrega dinàmica. Això es va aconseguir mitjançant un mètode per purificar els vectors de Lanczos (és a dir, reortogonalitzant repetidament cada nou vector generat amb tots els generats anteriorment) amb qualsevol grau de precisió, que quan no es realitzava, produïa una sèrie de vectors que estaven molt contaminats per els associats a les freqüències naturals més baixes.

En el seu treball original, aquests autors també van suggerir com seleccionar un vector inicial (és a dir, utilitzar un generador de nombres aleatoris per seleccionar cada element del vector inicial) i van suggerir un mètode determinat empíricament per determinar $m$, el nombre reduït de vectors (és a dir, s'hauria de seleccionar per ser aproximadament 1,5 vegades el nombre de valors propis precisos desitjat). Poc després el seu treball va ser seguit per Paige, que també va proporcionar una anàlisi d'errors. L'any 1988, Ojalvo va produir un historial més detallat d'aquest algorisme i una prova d'error de valors propis eficient.

L'algorisme

Introduir una matriu hermitiana de mida $n\times n$, i opcionalment una sèrie d'iteracions (per defecte, sigui $m=n$).

• En sentit estricte, l'algorisme no necessita accés a la matriu explícita, sinó només una funció $v\mapsto Av$ que calcula el producte de la matriu per un vector arbitrari. Aquesta funció s'anomena com a màxim vegades.

Sortida an matriu amb columnes ortonormals i una matriu simètrica real tridiagonal de mida $m\times m$. Si $m=n$, llavors V és unitari, i $A=VTV^{*}$.

Advertència La iteració de Lanczos és propensa a la inestabilitat numèrica. Quan s'executa en aritmètica no exacta, s'han de prendre mesures addicionals (tal com es descriu en seccions posteriors) per garantir la validesa dels resultats.

1. Sigui ser un vector arbitrari amb norma euclidiana 1.
2. Pas d'iteració inicial abreujat:
   1. Sigui $v_{1}\in \mathbb {C} ^{n}$.
   2. Sigui $\alpha _{1}=w_{1}'^{*}v_{1}$ .
   3. Sigui $w_{1}=w_{1}'-\alpha _{1}v_{1}$.
3. Per $w_{1}=w_{1}'-\alpha _{1}v_{1}$ fer $v_{j}=w_{j-1}/\beta _{j}$:
   1. Sigui $\beta _{j}=\|w_{j-1}\|$ (també norma euclidiana).
   2. Si $\beta _{j}\neq 0$ , llavors fer $v_{j}=w_{j-1}/\beta _{j}$,

      altrament escolliu com un vector arbitrari amb norma euclidiana que és ortogonal a tots $v_{1},\dots ,v_{j-1}$.

   3. Sigui $w_{j}'=Av_{j}$ .
   4. Sigui $\alpha _{j}=w_{j}'^{*}v_{j}$.
   5. Sigui $w_{j}=w_{j}'-\alpha _{j}v_{j}-\beta _{j}v_{j-1}$.
4. Sigui V la matriu amb columnes $v_{1},\dots ,v_{m}$. Sigui $T={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&&0\\\beta _{2}&\alpha _{2}&\beta _{3}&&&\\&\beta _{3}&\alpha _{3}&\ddots &&\\&&\ddots &\ddots &\beta _{m-1}&\\&&&\beta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&&&&\beta _{m}&\alpha _{m}\\\end{pmatrix}}$ .

Nota per $Av_{j}=w_{j}'=\beta _{j+1}v_{j+1}+\alpha _{j}v_{j}+\beta _{j}v_{j-1}$ per $1<j<m$.

En principi hi ha quatre maneres d'escriure el procediment d'iteració. Paige i altres treballs mostren que l'ordre d'operacions anterior és el més estable numèricament. A la pràctica el vector inicial $v_{1}$ es pot prendre com un altre argument del procediment, amb $\beta _{j}=0$ i s'inclouen indicadors d'imprecisió numèrica com a condicions addicionals de terminació del bucle.

Sense comptar la multiplicació matriu-vector, cada iteració ho fa $O(n)$ operacions aritmètiques. La multiplicació matriu-vector es pot fer en $O(dn)$ operacions aritmètiques on $d$ és el nombre mitjà d'elements diferents de zero en una fila. La complexitat total és així $O(dmn)$, o $O(dn^{2})$ si $m=n$; l'algorisme de Lanczos pot ser molt ràpid per a matrius escasses. Els esquemes per millorar l'estabilitat numèrica es jutgen normalment en funció d'aquest alt rendiment.

Aplicacions

Els algorismes de Lanczos són molt atractius perquè la multiplicació per $A\,$ és l'única operació lineal a gran escala. Com que els motors de recuperació de text amb termes ponderats implementen només aquesta operació, l'algoritme de Lanczos es pot aplicar de manera eficient als documents de text (vegeu indexació semàntica latent). Els vectors propis també són importants per als mètodes de classificació a gran escala com l'algoritme HITS desenvolupat per Jon Kleinberg o l'algoritme PageRank utilitzat per Google.

Els algorismes de Lanczos també s'utilitzen en la física de la matèria condensada com a mètode per resoldre els hamiltonians de sistemes electrònics fortament correlacionats, així com en els codis de models de capa en física nuclear.

Implementacions

La biblioteca NAG conté diverses rutines per a la solució de sistemes lineals a gran escala i problemes propis que utilitzen l'algorisme de Lanczos.

MATLAB i GNU Octave inclouen ARPACK integrat. Tant les matrius emmagatzemades com les implícites es poden analitzar mitjançant la funció eigs() (Matlab / Octave ).

De la mateixa manera, a Python, el paquet SciPy té scipy.sparse.linalg.eigsh que també és un embolcall per a les funcions de les funcions SSEUPD i DSEUPD d' ARPACK que utilitzen el mètode Lanczos reiniciat implícitament.

Una implementació de Matlab de l'algoritme Lanczos (anoteu problemes de precisió) està disponible com a part del paquet Gaussian Belief Propagation Matlab . La biblioteca de filtratge col·laboratiu GraphLab incorpora una implementació paral·lela a gran escala de l'algorisme Lanczos (en C++) per a multinucli.

La biblioteca PRIMME també implementa un algorisme semblant a Lanczos.