El algoritmo de Lanczos es un algoritmo directo ideado por Cornelius Lanczos que es una adaptación de métodos de potencia para encontrar elvalores propios y vectores propios "más útiles" (que tienden hacia los más altos / más bajos) de un Matriz hermitiana , donde es a menudo, pero no necesariamente, mucho más pequeño que . [1] Aunque computacionalmente eficiente en principio, el método tal como se formuló inicialmente no fue útil debido a su inestabilidad numérica .
En 1970, Ojalvo y Newman mostraron cómo hacer que el método fuera numéricamente estable y lo aplicaron a la solución de estructuras de ingeniería muy grandes sometidas a cargas dinámicas. [2] Esto se logró utilizando un método para purificar los vectores de Lanczos (es decir, reortogonalizando repetidamente cada vector recién generado con todos los generados previamente) [2] con cualquier grado de precisión, que cuando no se realizó, produjo una serie de vectores que fueron altamente contaminado por aquellos asociados con las frecuencias naturales más bajas.
En su trabajo original, estos autores también sugirieron cómo seleccionar un vector inicial (es decir, usar un generador de números aleatorios para seleccionar cada elemento del vector inicial) y sugirieron un método determinado empíricamente para determinar , el número reducido de vectores (es decir, debería seleccionarse para que sea aproximadamente 1,5 veces el número de valores propios precisos deseados). Poco después, su trabajo fue seguido por Paige, quien también proporcionó un análisis de errores. [3] [4] En 1988, Ojalvo produjo una historia más detallada de este algoritmo y una prueba de error de valor propio eficiente. [5]
El algoritmo
- Ingrese una matriz hermitiana de tamaño y, opcionalmente, varias iteraciones (por defecto, deje ).
- Estrictamente hablando, el algoritmo no necesita acceso a la matriz explícita, sino solo una función que calcula el producto de la matriz por un vector arbitrario. Esta función se llama como máximo veces.
- Salida un matriz con columnas ortonormales y una matriz simétrica real tridiagonal de tamaño . Si , luego es unitario , y .
- Advertencia La iteración de Lanczos es propensa a la inestabilidad numérica. Cuando se ejecuta en aritmética no exacta, se deben tomar medidas adicionales (como se describe en secciones posteriores) para garantizar la validez de los resultados.
- Dejar ser un vector arbitrario con norma euclidiana .
- Paso de iteración inicial abreviado:
- Dejar .
- Dejar .
- Dejar .
- Para hacer:
- Dejar (también norma euclidiana ).
- Si , luego deja ,
- si no elige como un vector arbitrario con norma euclidiana que es ortogonal a todos los .
- Dejar .
- Dejar .
- Dejar .
- Dejar ser la matriz con columnas . Dejar.
- Nota por .
En principio, hay cuatro formas de escribir el procedimiento de iteración. Paige y otros trabajos muestran que el orden de operaciones anterior es el más estable numéricamente. [6] [7] En la práctica, el vector inicial puede tomarse como otro argumento del procedimiento, con y los indicadores de imprecisión numérica se incluyen como condiciones adicionales de terminación de bucle.
Sin contar la multiplicación matriz-vector, cada iteración hace operaciones aritméticas. La multiplicación matriz-vector se puede hacer en operaciones aritméticas donde es el número medio de elementos distintos de cero seguidos. La complejidad total es entonces, o Si ; el algoritmo de Lanczos puede ser muy rápido para matrices dispersas. Los esquemas para mejorar la estabilidad numérica generalmente se juzgan en función de este alto rendimiento.
Los vectores se denominan vectores de Lanczos . El vector no se usa después se calcula, y el vector no se usa después se calcula. Por tanto, se puede utilizar el mismo almacenamiento para los tres. Del mismo modo, si solo la matriz tridiagonal se busca, entonces la iteración sin procesar no necesita después de haber calculado , aunque algunos esquemas para mejorar la estabilidad numérica lo necesitarían más adelante. A veces, los siguientes vectores de Lanczos se vuelven a calcular a partir de cuando sea necesario.
Aplicación al problema propio
El algoritmo de Lanczos se plantea con mayor frecuencia en el contexto de encontrar los autovalores y autovectores de una matriz, pero mientras que una diagonalización ordinaria de una matriz haría evidentes los autovectores y autovalores de la inspección, lo mismo no es cierto para la tridiagonalización realizada por Lanczos algoritmo; Se necesitan pasos adicionales no triviales para calcular incluso un solo valor propio o vector propio. No obstante, la aplicación del algoritmo de Lanczos suele ser un paso adelante significativo en el cálculo de la descomposición propia. Si es un valor propio de , y si ( es un vector propio de ) luego es el vector propio correspondiente de (desde ). Así, el algoritmo de Lanczos transforma el problema de descomposición propia para en el problema de autodescomposición para .
- Para las matrices tridiagonales, existe una serie de algoritmos especializados, a menudo con mejor complejidad computacional que los algoritmos de propósito general. Por ejemplo, si es un matriz simétrica tridiagonal entonces:
- La recursividad continua permite calcular el polinomio característico en operaciones, y evaluarlo en un punto en operaciones.
- El algoritmo de valor propio divide y vencerás se puede utilizar para calcular la descomposición propia completa de en operaciones.
- El Método Fast Multipole [8] puede calcular todos los valores propios en solo operaciones.
- Se sabe que algunos algoritmos generales de autodescomposición, en particular el algoritmo QR , convergen más rápido para las matrices tridiagonales que para las matrices generales. La complejidad asintótica del QR tridiagonal esal igual que para el algoritmo divide y vencerás (aunque el factor constante puede ser diferente); ya que los autovectores juntos tienen elementos, esto es asintóticamente óptimo.
- Incluso los algoritmos cuyas tasas de convergencia no se ven afectadas por las transformaciones unitarias, como el método de potencia y la iteración inversa , pueden disfrutar de beneficios de rendimiento de bajo nivel al aplicarse a la matriz tridiagonal. en lugar de la matriz original . Desdees muy escaso con todos los elementos distintos de cero en posiciones altamente predecibles, permite un almacenamiento compacto con un rendimiento excelente con respecto al almacenamiento en caché . Igualmente,es una matriz real con todos los autovectores y autovalores reales, mientras que en general puede tener elementos complejos y autovectores, por lo que la aritmética real es suficiente para encontrar los autovectores y autovalores de .
- Si es muy grande, luego se reduce así que eso es de un tamaño manejable todavía permitirá encontrar los autovalores y autovectores más extremos de ; en elregión, el algoritmo de Lanczos puede verse como un esquema de compresión con pérdida para matrices hermitianas, que enfatiza la preservación de los valores propios extremos.
La combinación de un buen rendimiento para matrices dispersas y la capacidad de calcular varios valores propios (sin calcular todos) son las principales razones para optar por utilizar el algoritmo de Lanczos.
Aplicación a la tridiagonalización
Aunque el problema propio es a menudo la motivación para aplicar el algoritmo de Lanczos, la operación que realiza principalmente el algoritmo es la tridiagonalización de una matriz, para lo cual se han favorecido las transformaciones de jefes de hogar numéricamente estables desde los años cincuenta. Durante la década de 1960 se ignoró el algoritmo de Lanczos. El interés en él fue rejuvenecido por la teoría de la convergencia de Kaniel-Paige y el desarrollo de métodos para prevenir la inestabilidad numérica, pero el algoritmo de Lanczos sigue siendo el algoritmo alternativo que uno intenta solo si Householder no es satisfactorio. [9]
Los aspectos en los que se diferencian los dos algoritmos incluyen:
- Lanczos aprovecha siendo una matriz dispersa, mientras que Householder no lo hace, y generará un relleno .
- Lanczos trabaja en su totalidad con la matriz original. (y no tiene ningún problema con que se conozca solo implícitamente), mientras que Householder sin procesar quiere modificar la matriz durante el cálculo (aunque eso puede evitarse).
- Cada iteración del algoritmo de Lanczos produce otra columna de la matriz de transformación final , mientras que una iteración de Householder produce otro factor en una factorización unitaria de . Sin embargo, cada factor está determinado por un solo vector, por lo que los requisitos de almacenamiento son los mismos para ambos algoritmos, y se puede calcular en hora.
- Householder es numéricamente estable, mientras que Lanczos crudo no lo es.
- Lanczos es muy paralelo, con solo puntos de sincronización (los cálculos de y ). El jefe de hogar es menos paralelo, ya que tiene una secuencia de Las cantidades escalares calcularon que cada una depende de la cantidad anterior en la secuencia.
Derivación del algoritmo
Hay varias líneas de razonamiento que conducen al algoritmo de Lanczos.
Un método de poder más previsor
El método de potencia para encontrar el valor propio de mayor magnitud y un vector propio correspondiente de una matriz es aproximadamente
- Elige un vector aleatorio .
- Para (hasta la dirección de ha convergido) hacer:
- Dejar
- Dejar
- En el grande límite, se aproxima al vector propio normalizado correspondiente al valor propio de mayor magnitud.
Una crítica que se puede hacer contra este método es que es un desperdicio: gasta mucho trabajo (los productos matriz-vector en el paso 2.1) extrayendo información de la matriz , pero presta atención solo al último resultado; Las implementaciones suelen utilizar la misma variable para todos los vectores., haciendo que cada nueva iteración sobrescriba los resultados de la anterior. ¿Qué pasa si, en cambio, conservamos todos los resultados intermedios y organizamos sus datos?
Una pieza de información que trivialmente está disponible en los vectores es una cadena de subespacios de Krylov . Una forma de afirmar que sin introducir conjuntos en el algoritmo es afirmar que calcula
- un subconjunto de una base de tal que para cada y todo
esto es trivialmente satisfecho por Mientras es linealmente independiente de (y en el caso de que exista tal dependencia, entonces uno puede continuar la secuencia eligiendo como un vector arbitrario linealmente independiente de ). Una base que contiene elSin embargo, es probable que los vectores estén numéricamente mal condicionados , ya que esta secuencia de vectores está diseñada para converger en un vector propio de. Para evitar eso, se puede combinar la iteración de potencia con un proceso de Gram-Schmidt , para producir en su lugar una base ortonormal de estos subespacios de Krylov.
- Elige un vector aleatorio de la norma euclidiana . Dejar.
- Para hacer:
- Dejar .
- Para todos dejar . (Estas son las coordenadas de con respecto a los vectores base .)
- Dejar . (Cancelar el componente de que esta en .)
- Si entonces deja y ,
- de lo contrario, elige como un vector arbitrario de la norma euclidiana que es ortogonal a todos los .
La relación entre los vectores de iteración de potencia y los vectores ortogonales es eso
- .
Aquí se puede observar que en realidad no necesitamos el vectores para calcular estos , porque y por lo tanto la diferencia entre y es en , que se anula mediante el proceso de ortogonalización. Así, la misma base para la cadena de subespacios de Krylov se calcula mediante
- Elige un vector aleatorio de la norma euclidiana .
- Para hacer:
- Dejar .
- Para todos dejar .
- Dejar .
- Dejar .
- Si entonces deja ,
- de lo contrario, elige como un vector arbitrario de la norma euclidiana que es ortogonal a todos los .
A priori los coeficientes satisfacer
- para todos ;
la definición puede parecer un poco extraño, pero se ajusta al patrón general desde
Porque los vectores de iteración de poder que fueron eliminados de esta recursividad satisfacen los vectores y coeficientes contener suficiente información de que todo de se puede calcular, por lo que no se perdió nada al cambiar los vectores. (De hecho, resulta que los datos recopilados aquí dan aproximaciones significativamente mejores del valor propio más grande que las que se obtienen de un número igual de iteraciones en el método de potencia, aunque eso no es necesariamente obvio en este punto).
Este último procedimiento es la iteración de Arnoldi . El algoritmo de Lanczos surge entonces como la simplificación que se obtiene al eliminar los pasos de cálculo que resultan ser triviales cuando es hermitiano, en particular la mayoría de los los coeficientes resultan ser cero.
Elementalmente, si es hermitiano entonces
Para lo sabemos , y desde por construcción es ortogonal a este subespacio, este producto interno debe ser cero. (Esta es esencialmente también la razón por la cual las secuencias de polinomios ortogonales siempre pueden tener una relación de recurrencia de tres términos ). uno obtiene
ya que este último es real por ser la norma de un vector. Para uno obtiene
lo que significa que esto también es real.
De manera más abstracta, si es la matriz con columnas luego los números pueden identificarse como elementos de la matriz , y por la matriz es Hessenberg superior . Desde
la matriz es hermitiano. Esto implica queTambién es Hessenberg inferior, por lo que de hecho debe ser tridiagional. Siendo hermitiana, su diagonal principal es real, y dado que su primera subdiagonal es real por construcción, lo mismo ocurre con su primera superdiagonal. Por lo tanto, es una matriz simétrica real: la matriz de la especificación del algoritmo de Lanczos.
Aproximación simultánea de valores propios extremos
Una forma de caracterizar los vectores propios de una matriz hermitiana es como puntos estacionarios del cociente de Rayleigh
En particular, el valor propio más grande es el máximo global de y el valor propio más pequeño es el mínimo global de .
Dentro de un subespacio de baja dimensión de puede ser factible ubicar el máximo y mínimo de . Repitiendo eso para una cadena creciente produce dos secuencias de vectores: y tal que y
Entonces surge la pregunta de cómo elegir los subespacios para que estas secuencias converjan a una velocidad óptima.
De , la dirección óptima en la que buscar mayores valores de es el del gradiente , e igualmente de la dirección óptima en la que buscar valores más pequeños de es el del gradiente negativo . En general
por lo que las direcciones de interés son bastante fáciles de calcular en aritmética matricial, pero si se desea mejorar en ambas y entonces hay dos nuevas direcciones a tener en cuenta: y desde y pueden ser vectores linealmente independientes (de hecho, están cerca de ortogonales), en general no se puede esperar y ser paralelo. Por tanto, ¿es necesario aumentar la dimensión de por en cada paso? No si se toman como subespacios de Krylov, porque entonces para todos así en particular para ambos y .
En otras palabras, podemos comenzar con algún vector inicial arbitrario construir los espacios vectoriales
y luego buscar tal que
Desde el El método de potencia itera pertenece a se deduce que una iteración para producir el y no puede converger más lento que el del método de potencia, y logrará más al aproximar ambos extremos de valores propios. Para el subproblema de optimizar en algunos , conviene tener una base ortonormal para este espacio vectorial. Por lo tanto, nuevamente nos encontramos con el problema de calcular iterativamente tal base para la secuencia de subespacios de Krylov.
Convergencia y otras dinámicas
Al analizar la dinámica del algoritmo, es conveniente tomar los autovalores y autovectores de como se dan, aunque el usuario no los conozca explícitamente. Para arreglar la notación, deje ser los valores propios (se sabe que todos son reales y, por lo tanto, es posible ordenarlos) y dejar ser un conjunto ortonormal de autovectores tales que para todos .
También es conveniente fijar una notación para los coeficientes del vector de Lanczos inicial con respecto a esta base propia; dejar para todos , así que eso . Un vector inicialel agotamiento de algún valor propio retrasará la convergencia al valor propio correspondiente, y aunque esto simplemente aparece como un factor constante en los límites de error, el agotamiento sigue siendo indeseable. Una técnica común para evitar ser golpeado consistentemente es elegirdibujando primero los elementos al azar de acuerdo con la misma distribución normal con media y luego cambiar la escala del vector a la norma . Antes del cambio de escala, esto provoca que los coeficientes para ser también independientes variables estocásticas normalmente distribuidas de la misma distribución normal (ya que el cambio de coordenadas es unitario), y después de reescalar el vector tendrá una distribución uniforme en la esfera unitaria en. Esto hace posible acotar la probabilidad de que, por ejemplo,.
El hecho de que el algoritmo de Lanczos sea independiente de las coordenadas (las operaciones solo miran los productos internos de los vectores, nunca los elementos individuales de los vectores) hace que sea fácil construir ejemplos con una estructura propia conocida para ejecutar el algoritmo en: make una matriz diagonal con los valores propios deseados en la diagonal; siempre que el vector inicial tiene suficientes elementos distintos de cero, el algoritmo generará una matriz simétrica tridiagonal general como .
Teoría de la convergencia de Kaniel-Paige
Después pasos de iteración del algoritmo de Lanczos, es un matriz simétrica real, que de manera similar a la anterior tiene valores propios Por convergencia se entiende principalmente la convergencia de a (y la convergencia simétrica de a ) como crece y, en segundo lugar, la convergencia de algún rango de valores propios de a sus contrapartes de . La convergencia del algoritmo de Lanczos es a menudo órdenes de magnitud más rápida que la del algoritmo de iteración de potencia. [9] : 477
Los límites para provienen de la interpretación anterior de los valores propios como valores extremos del cociente de Rayleigh . Desde es a priori el máximo de en la totalidad de mientras que es simplemente el máximo en un -subespacio de Krylov dimensional, trivialmente obtenemos . Por el contrario, cualquier punto en que el subespacio de Krylov proporciona un límite inferior por , por lo que si se puede exhibir un punto para el cual es pequeño, entonces esto proporciona un límite estrecho en .
La dimensión El subespacio de Krylov es
por lo que cualquier elemento puede expresarse como para algún polinomio de grado como máximo ; los coeficientes de ese polinomio son simplemente los coeficientes en la combinación lineal de los vectores. El polinomio que queremos resultará tener coeficientes reales, pero por el momento debemos permitir también coeficientes complejos, y escribiremos para el polinomio obtenido mediante la conjugación compleja de todos los coeficientes de . En esta parametrización del subespacio de Krylov, tenemos
Usando ahora la expresión para como una combinación lineal de vectores propios, obtenemos
y mas en general
para cualquier polinomio .
Por lo tanto
Una diferencia clave entre numerador y denominador aquí es que el término desaparece en el numerador, pero no en el denominador. Por lo tanto, si uno puede elegir ser grande en pero pequeño en todos los demás valores propios, se obtendrá un límite estricto en el error .
Desde tiene muchos más valores propios que tiene coeficientes, esto puede parecer una tarea difícil, pero una forma de cumplirlo es usar polinomios de Chebyshev . Escritura para el grado Polinomio de Chebyshev del primer tipo (el que satisface para todos ), tenemos un polinomio que permanece en el rango en el intervalo conocido pero crece rápidamente fuera de ella. Con algo de escala del argumento, podemos hacer que mapee todos los valores propios excepto dentro . Dejar
(en caso , use en su lugar el valor propio más grande estrictamente menor que ), entonces el valor máximo de por es y el valor mínimo es , entonces
además
la cantidad
(es decir, la relación entre el primer eigengap y el diámetro del resto del espectro ) es, por tanto, de importancia clave para la tasa de convergencia aquí. También escribiendo
podemos concluir que
Por tanto, la tasa de convergencia está controlada principalmente por , ya que este límite se reduce en un factor para cada iteración adicional.
A modo de comparación, se puede considerar cómo la tasa de convergencia del método de potencia depende de , pero dado que el método de la potencia es principalmente sensible al cociente entre valores absolutos de los valores propios, necesitamos para el eigengap entre y ser el dominante. Bajo esa restricción, el caso que más favorece el método de potencia es que, así que considere eso. Al final del método de potencia, el vector de iteración:
- [nota 1]
donde cada nueva iteración multiplica efectivamente el -amplitud por
La estimación del valor propio más grande es entonces
por lo que el límite anterior para la tasa de convergencia del algoritmo de Lanczos debe compararse con
que se encoge por un factor de para cada iteración. La diferencia, por tanto, se reduce a que entre y . En el región, este último es más como , y funciona como lo haría el método de potencia con un eigengap dos veces mayor; una mejora notable. Sin embargo, el caso más desafiante es el de en el cual es una mejora aún mayor en la brecha propia; laLa región es donde el algoritmo de Lanczos en cuanto a la convergencia hace la menor mejora en el método de potencia.
Estabilidad numérica
La estabilidad significa cuánto se verá afectado el algoritmo (es decir, producirá un resultado aproximado cercano al original) si se introducen y acumulan pequeños errores numéricos. La estabilidad numérica es el criterio central para juzgar la utilidad de implementar un algoritmo en una computadora con redondeo.
Para el algoritmo de Lanczos, se puede demostrar que con aritmética exacta , el conjunto de vectoresconstruye una base ortonormal , y los autovalores / vectores resueltos son buenas aproximaciones a los de la matriz original. Sin embargo, en la práctica (dado que los cálculos se realizan en aritmética de coma flotante donde la inexactitud es inevitable), la ortogonalidad se pierde rápidamente y en algunos casos el nuevo vector podría incluso depender linealmente del conjunto que ya está construido. Como resultado, algunos de los valores propios de la matriz tridiagonal resultante pueden no ser aproximaciones a la matriz original. Por tanto, el algoritmo de Lanczos no es muy estable.
Los usuarios de este algoritmo deben poder encontrar y eliminar esos valores propios "falsos". Las implementaciones prácticas del algoritmo de Lanczos van en tres direcciones para combatir este problema de estabilidad: [6] [7]
- Evitar la pérdida de ortogonalidad,
- Recupere la ortogonalidad una vez generada la base.
- Después de identificar los valores propios buenos y "espurios", elimine los falsos.
Variaciones
Existen variaciones en el algoritmo de Lanczos donde los vectores involucrados son matrices altas y estrechas en lugar de vectores y las constantes de normalización son matrices cuadradas pequeñas. Estos se denominan algoritmos de "bloque" de Lanczos y pueden ser mucho más rápidos en equipos con una gran cantidad de registros y tiempos de recuperación de memoria prolongados.
Muchas implementaciones del algoritmo de Lanczos se reinician después de un cierto número de iteraciones. Una de las variaciones reiniciadas más influyentes es el método Lanczos reiniciado implícitamente, [10] que se implementa en ARPACK . [11] Esto ha llevado a una serie de otras variaciones reiniciadas, como la bidiagonalización de Lanczos reiniciada. [12] Otra variación reiniciada con éxito es el método Lanczos de reinicio grueso, [13] que se ha implementado en un paquete de software llamado TRLan. [14]
Espacio nulo sobre un campo finito
En 1995, Peter Montgomery publicó un algoritmo, basado en el algoritmo de Lanczos, para encontrar elementos del espacio nulo de una gran matriz dispersa sobre GF (2) ; Dado que el conjunto de personas interesadas en grandes matrices dispersas sobre campos finitos y el conjunto de personas interesadas en grandes problemas de valores propios apenas se superponen, esto a menudo también se denomina algoritmo de bloque de Lanczos sin causar una confusión irrazonable. [ cita requerida ]
Aplicaciones
Los algoritmos de 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 de términos ponderados implementan solo esta operación, el algoritmo de Lanczos se puede aplicar de manera eficiente a los documentos de texto (consulte Indexación semántica latente ). Los vectores propios también son importantes para los métodos de clasificación a gran escala, como el algoritmo HITS desarrollado por Jon Kleinberg o el algoritmo PageRank utilizado por Google.
Los algoritmos de Lanczos también se utilizan en Física de la Materia Condensada como un método para resolver hamiltonianos de sistemas de electrones fuertemente correlacionados , [15] así como en códigos de modelos de capa en física nuclear . [dieciséis]
Implementaciones
La biblioteca NAG contiene varias rutinas [17] para la solución de sistemas lineales a gran escala y problemas propios que utilizan el algoritmo de Lanczos.
MATLAB y GNU Octave vienen con ARPACK integrado. Tanto las matrices almacenadas como las implícitas se pueden analizar mediante la función eigs () ( Matlab / Octave ).
Una implementación de Matlab del algoritmo de Lanczos (tenga en cuenta los problemas de precisión) está disponible como parte del paquete Matlab de propagación de creencias gaussianas . La biblioteca de filtrado colaborativo GraphLab [18] incorpora una implementación paralela a gran escala del algoritmo de Lanczos (en C ++) para multinúcleo.
La biblioteca PRIMME también implementa un algoritmo similar a Lanczos.
Notas
- ^ No es necesario que ambos coeficientes sean reales, pero la fase tiene poca importancia. Tampoco es necesario que los componentes de otros vectores propios hayan desaparecido por completo, pero se encogen al menos tan rápido como para, entonces describe el peor de los casos.
Referencias
- ↑ Lanczos, C. (1950). "Un método de iteración para la solución del problema de valores propios de operadores integrales y diferenciales lineales" (PDF) . Revista de investigación de la Oficina Nacional de Normas . 45 (4): 255–282. doi : 10.6028 / jres.045.026 .
- ^ a b Ojalvo, IU; Newman, M. (1970). "Modos de vibración de grandes estructuras mediante un método automático de reducción de matriz". Revista AIAA . 8 (7): 1234-1239. Código bibliográfico : 1970AIAAJ ... 8.1234N . doi : 10,2514 / 3,5878 .
- ^ Paige, CC (1971). El cálculo de autovalores y autovectores de matrices dispersas muy grandes (tesis doctoral). U. de Londres. OCLC 654214109 .
- ^ Paige, CC (1972). "Variantes computacionales del método Lanczos para el problema propio". J. Inst. Aplicaciones de matemáticas . 10 (3): 373–381. doi : 10.1093 / imamat / 10.3.373 .
- ^ Ojalvo, IU (1988). "Orígenes y ventajas de los vectores de Lanczos para grandes sistemas dinámicos". Proc. 6ta Conferencia de Análisis Modal (IMAC), Kissimmee, FL . págs. 489–494.
- ^ a b Cullum; Willoughby. Algoritmos de Lanczos para grandes cálculos de valores propios simétricos . 1 . ISBN 0-8176-3058-9.
- ^ a b Yousef Saad (22 de junio de 1992). Métodos numéricos para grandes problemas de valores propios . ISBN 0-470-21820-7.
- ^ Coakley, Ed S .; Rokhlin, Vladimir (2013). "Un algoritmo rápido de divide y vencerás para calcular los espectros de matrices tridiagonales simétricas reales" . Análisis Armónico Computacional y Aplicado . 34 (3): 379–414. doi : 10.1016 / j.acha.2012.06.003 .
- ^ a b Golub, Gene H .; Van Loan, Charles F. (1996). Cálculos matriciales (3. ed.). Baltimore: Universidad Johns Hopkins. Prensa. ISBN 0-8018-5413-X.
- ^ D. Calvetti ; L. Reichel; DC Sorensen (1994). "Un método de Lanczos reiniciado implícitamente para grandes problemas de valores propios simétricos" . Transacciones electrónicas sobre análisis numérico . 2 : 1-21.
- ^ RB Lehoucq; DC Sorensen; C. Yang (1998). Guía del usuario de ARPACK: Solución de problemas de valores propios a gran escala con métodos Arnoldi reiniciados implícitamente . SIAM. doi : 10.1137 / 1.9780898719628 . ISBN 978-0-89871-407-4.
- ^ E. Kokiopoulou; C. Bekas; E. Gallopoulos (2004). "Cálculo de trillizos singulares más pequeños con bidiagonalización de Lanczos reiniciada implícitamente" (PDF) . Apl. Numer. Matemáticas . 49 : 39–61. doi : 10.1016 / j.apnum.2003.11.011 .
- ^ Kesheng Wu; Horst Simon (2000). "Método Lanczos de reinicio grueso para grandes problemas de valores propios simétricos" . Revista SIAM sobre Análisis y Aplicaciones Matriciales . SIAM. 22 (2): 602–616. doi : 10.1137 / S0895479898334605 .
- ^ Kesheng Wu; Horst Simon (2001). "Paquete de software TRLan" . Archivado desde el original el 1 de julio de 2007 . Consultado el 30 de junio de 2007 .
- ^ Chen, HY; Atkinson, WA; Wortis, R. (julio de 2011). "Anomalía de sesgo cero inducida por el trastorno en el modelo de Anderson-Hubbard: cálculos numéricos y analíticos". Physical Review B . 84 (4): 045113. arXiv : 1012.1031 . Código bibliográfico : 2011PhRvB..84d5113C . doi : 10.1103 / PhysRevB.84.045113 .
- ^ Shimizu, Noritaka (21 de octubre de 2013). "Código de modelo de capa nuclear para cálculo paralelo masivo," KSHELL " ". arXiv : 1310,5431 [ nucl-ésimo ].
- ^ El grupo de algoritmos numéricos. "Índice de palabras clave: Lanczos" . Manual de la biblioteca NAG, Mark 23 . Consultado el 9 de febrero de 2012 .
- ^ GraphLab Archivado el 14 de marzo de 2011 en la Wayback Machine.
Otras lecturas
- Golub, Gene H .; Van Loan, Charles F. (1996). "Métodos Lanczos" . Cálculos matriciales . Baltimore: Prensa de la Universidad Johns Hopkins. págs. 470–507. ISBN 0-8018-5414-8.
- Ng, Andrew Y .; Zheng, Alice X .; Jordan, Michael I. (2001). "Análisis de enlaces, autovectores y estabilidad" (PDF) . IJCAI'01 Actas de la 17ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . 2 : 903–910.