Algoritmo de Lanczos

Metodo numerico para encontra los valores/vectores propios de un sistema

El algoritmo de Lanczos es un algoritmo iterativo creado por Cornelius Lanczos,[1]​ este es una adaptación de los métodos iterativos para encontrar los valores propios más útiles y vectores propios de un sistema lineal de dimensión realizando un número de operaciones, , donde es más pequeño que .

Aunque computacionalmente eficiente, en principio, el método formulado inicialmente no era útil, debido a su inestabilidad numérica. En 1970, Ojalvo y Newman mostraron cómo hacer el método numéricamente estable.[2]​ Esto se logró utilizando un método para la corrección de los vectores a cualquier grado de precisión que, cuando no se realiza, produce una serie de vectores que están altamente contaminados por los asociados con las frecuencias naturales más bajas. En su trabajo original, estos autores también sugirieron cómo seleccionar un vector de partida (utilizan un generador de números aleatorios para seleccionar cada elemento del vector de partida) y propusieron un método determinado empíricamente para determinar , el reducido número de vectores (debe ser seleccionado para ser de aproximadamente 1 ½ veces el número de valores propios exactos que se desea).

Poco después su trabajo fue seguido por más artículos[3][4]​ que también proporciaron un análisis del error cometido. En el año 1988, Ojalvo[5]​ produjo una historia más detallada de este algoritmo y una prueba de error eficiente para un valor propio. Actualmente, el método es ampliamente utilizado en una variedad de campos técnicos y ha dado lugar una serie de variantes.

Método iterativo para encontrar valores propios

editar

El método iterativo para encontrar el mayor valor propio de una matriz   puede resumirse señalando que si   es un vector aleatorio y  , entonces para un   grande límite   se acerca al vector propio normalizado correspondiente al valor propio más grande.

Si   es la descomposición en valores propios de una matriz de  , entonces  . Como   se hace grande, la matriz diagonal de valores propios estará acotada por el valor propio más grande(despreciando el caso en que el valor más grande este repetido ). Mientras,   convergerán al mayor valor propio y   al vector propio asociado. Si el mayor valor propio es múltiple, entonces   convergerá a un vector en el subespacio generado por los vectores propios asociados con esos valores propios más grandes. Luego de haber encontrado el primer vector propio / valor, uno puede restringir sucesivamente el algoritmo para el espacio nulo (kernel) de los vectores propios conocidos para obtener el segundo mayor vector propio / valores y así sucesivamente.

En la práctica, este sencillo algoritmo no funciona muy bien para el cálculo de muchos de los vectores propios, ya que cualquier error de redondeo podría introducir ligeros cambios a los componentes de los vectores propios más significativos de nuevo en el cálculo, degradando la exactitud del cálculo.

Método de Lanczos

editar

Durante el procedimiento de aplicación del método, al obtener el último valor propio  , también se obtiene una serie de vectores   los cuales son descartados. Como   es con frecuencia grande, puede que se tenga una gran cantidad de información que no se utilice. Los algoritmos más avanzados, Como el el algoritmo de Arnoldi, el algoritmo de Lanczos, guardan esta información y utilizan el proceso de Gram–Schmidt o el algoritmo Householder para ortogonalizar nuevamente en una base que abarca el subespacio de Krylov correspondiente a la matriz  .

El algoritmo

editar

El algoritmo de Lanczos puede ser visto como un sistema simplificado del algoritmo de Arnoldi que se aplica a matrices hermitianas. El   paso del algoritmo transforma la matriz   en una matriz tridiagonal  ; cuando   es igual a la dimensión de  ,   es semejante a  .

Definiciones

editar

Se quiere calcular la matriz tridiagonal y simétrica  

Los elementos de la diagonal se denotan por  , Y los elementos fuera de la diagonal son denotados por  .

Notar que  , debido a la simetría de la matriz.

Iteración

editar

(Nota: siguiendo estos pasos solamente no se encontraran correctamente los valores y vectores propios. Se deben tener en cuenta más consideraciones para corregir errores numéricos. Ver la sección Estabilidad numérica.)

En principio, hay cuatro maneras de escribir el procedimiento de iteración. Paige[1972] y otros trabajos muestran que el siguiente procedimiento es el más estable numéricamente.[6][7]

   vector aleatorio con norma 1.
  
  
 for  
    
    
    
    
    
 endfor
  
  
 return

Aquí,   representa el producto escalar de vectores   y  .

Después de la iteración, se obtiene la   and   con los que se forma una matriz tridiagonal.

 

Los vectores   (vectores de Lanczos) generados sobre la marcha forman la matriz de transformación  , que es útil para el cálculo de los vectores propios (ver más abajo). En la práctica, se podría guardar en cada iteración (pero ocupa memoria), o se podría recalcular cuando se necesite, siempre y cuando se tenga el primer vector  . En cada iteración del algoritmo realiza una multiplicación matriz-vector y otras operaciones de punto flotantes.

Encontrando valores y vectores propios

editar

Después de que la matriz   es calculada, se pueden encontrar sus valores propios   y sus correspondientes vectores propios   (Por ejemplo, usando el algoritmo QR o Multiple Relatively Robust Representations (MRRR)). Los valores y vectores propios de  se pueden obtener en   usando MRRR; si se quiere buscar solo los valores propios estos se calculan en   usando bisección espectral.

Se puede demostrar que los valores propios son valores propios aproximados de la matriz original  .

Los vectores propios   de   se pueden calcular  , donde   es la matriz de transformación cuyos vectores columna son  .

Estabilidad Numérica

editar

Estabilidad significa cuánto se verá afectado el algoritmo (es decir, se encontrara un resultado aproximado cercano al original) si hay pequeños errores numéricos introducidos y acumulados. Estabilidad numérica es el criterio central para juzgar la utilidad de una implementación de un algoritmo en un ordenador con redondeo. Para el algoritmo de Lanczos, se puede demostrar que con una aritmética exacta, el conjunto de vectores   forman una base ortonormal, los valores y vectores propios encontrados son buenas aproximaciones a los de la matriz original. Sin embargo, en la práctica (como los cálculos se realizan en aritméticas de punto flotante donde la inexactitud es inevitable, la ortogonalidad se pierde rápidamente y en algunos casos el nuevo vector incluso podría ser linealmente dependiente del conjunto que ya está construido. Como resultado, algunos de los valores propios de la matriz tridiagonal resultante no son buenas aproximaciones para los de la matriz original. Por lo que, el algoritmo de Lanczos no es muy estable.

Los que usen el algoritmo deben ser capaz de encontrar y eliminar los valores propios "con errores". Las implementaciones prácticas del algoritmo de Lanczos van en tres direcciones para luchar contra este problema de estabilidad:[6][7]

  1. Prevenir la pérdida de ortogonalidad
  2. Recuperar la ortogonalidad después de que se genera la base.
  3. Después de identificar los valores propios "con errores", eliminarlos.

Variantes

editar

Existen variantes en el algoritmo de Lanczos donde los vectores involucrados son vectores columnas, matrices estrechas y las constantes de la normalización son pequeñas matrices cuadradas. Estos se llaman "bloques" y el algoritmo de Lanczos puede ser mucho más rápido en computadoras con un gran número de registros y tiempos de esfuerzo de memoria largos.

Muchas implementaciones del algoritmo de Lanczos reinician después de un cierto número de iteraciones. Una de las variaciones del reinicio más influyentes es el método de Lanczos con reinicio implícito,[8]​ que se implementa enARPACK.[9]​ Esto ha llevado a un número de otras variantes de reinicio tales como reinicio bidiagonalizado de Lanczos.[10]​ Otra variante de reinicio exitosa es el método Thick-Restart de Lanczos,[11]​ que se ha implementado en un paquete de software llamado TRLAN.[12]

Kernel sobre un cuerpo finito

editar

En 1995, Peter Montgomery publicó un algoritmo, basado en el algoritmo de Lanczos para encontrar elementos del kernel de una gran matriz sparse sobre GF(2); ya que el conjunto de personas interesadas en matrices sparse de gran dimensión sobre cuerpos finitos y el conjunto de personas interesadas en los problemas de los valores propios más grandes, tienen pocas personas en común, esto es a menudo también llamado el algoritmo de Lanczos por bloques.

Aplicaciones

editar

Los algoritmos Lanczos son muy atractivos porque la multiplicación por   es la única operación lineal a gran escala. Dado que los motores de recuperación de texto implementan esta operación, el algoritmo Lanczos se puede aplicar de manera eficiente a los documentos de texto (ver indexación semántica latente). Los vectores propios son también importantes para los métodos de clasificación a gran escala tales como el algoritmo HITS desarrollado por Jon Kleinberg, o el PageRank algoritmo usado por Google.

Algoritmos de Lanczos también se utilizan en Física de la materia condensada como un método para resolver hamiltonianas de sistemas de electrones fuertemente correlacionados.[13]

Implementaciones

editar

La biblioteca NAG contiene varias métodos[14]​ para la solución de sistemas lineales grandes y problemas de valores/vectores propios que utilizan el algoritmo de Lanczos.

MATLAB y GNU Octave vienen con ARPACK incorporado. Ambos analizan matrices usando la función eigs() (Matlab/Octave).

La implementación de Matlab del algoritmo de Lanczos (nota: problemas de precisión) está disponible como parte de la Gaussian Belief Propagation Matlab Package. El GraphLab[15]​ biblioteca de filtrado colaborativo incorpora una implementación paralelizada del algoritmo de Lanczos (en C ++) para multinúcleo. La biblioteca PRIMME también implementa el algoritmo de Lanczos.

Referencias

editar
  1. Lanczos, C. “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators”, J. Res. Nat’l Bur. Std. 45, 225-282 (1950).
  2. Ojalvo, I.U. and Newman, M.,”Vibration modes of large structures by an automatic matrix-reduction method”, AIAA J., 8 (7), 1234-1239 (1970).
  3. Paige, C.C., “The computation of eigenvalues and eigenvectors of very large sparse matrices”, the U. of London Ph.D. thesis (1971).
  4. Paige, C.C., “Computational variants of the Lanczos method for the eigenproblem”, J. Inst. Maths Applics 10, 373-381 (1972).
  5. Ojalvo, I.U., “Origins and advantages of Lanczos vectors for large dynamic systems”, Proc. 6th Modal Analysis Conference (IMAC), Kissimmee, FL, 489-494 (1988).
  6. a b Cullum; Willoughby. Lanczos Algorithms for Large Symmetric Eigenvalue Computations 1. ISBN 0-8176-3058-9. 
  7. a b Yousef Saad. Numerical Methods for Large Eigenvalue Problems. ISBN 0-470-21820-7. 
  8. D. Calvetti, L. Reichel, and D.C. Sorensen (1994). «An Implicitly Restarted Lanczos Method for Large Symmetric Eigenvalue Problems». Electronic Transactions on Numerical Analysis 2: 1-21. 
  9. R. B. Lehoucq, D. C. Sorensen, and C. Yang (1998). ARPACK Users Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM. doi:10.1137/1.9780898719628. 
  10. E. Kokiopoulou and C. Bekas and E. Gallopoulos (2004). «Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization». Appl. Numer. Math. 49: 39. doi:10.1016/j.apnum.2003.11.011. 
  11. Kesheng Wu and Horst Simon (2000). «Thick-Restart Lanczos Method for Large Symmetric Eigenvalue Problems». SIAM Journal on Matrix Analysis and Applications (SIAM) 22 (2): 602. doi:10.1137/S0895479898334605. 
  12. Kesheng Wu and Horst Simon (2001). «TRLan software package». Archivado desde el original el 1 de julio de 2007. Consultado el 24 de noviembre de 2014. 
  13. Chen, HY; Atkinson, W.A.; Wortis, R. (julio de 2011). «Disorder-induced zero-bias anomaly in the Anderson-Hubbard model: Numerical and analytical calculations». Physical Review B 84 (4). doi:10.1103/PhysRevB.84.045113. 
  14. The Numerical Algorithms Group. «Keyword Index: Lanczos». NAG Library Manual, Mark 23. Consultado el 9 de febrero de 2012. 
  15. GraphLab Archivado el 14 de marzo de 2011 en Wayback Machine.

Enlaces externos

editar