LOBPCG

El método realiza una maximización (o minimización) iterativa del cociente de Rayleigh generalizado.

$${\displaystyle \rho (x):=\rho (A,B;x):={\frac {x^{\mathsf {T}}Ax}{x^{\mathsf {T}}Bx}},}$$

lo que resulta en encontrar los pares propios más grandes (o más pequeños) de${\displaystyle Ax=\lambda Bx.}$

La dirección del ascenso más pronunciado, que es el gradiente , del cociente de Rayleigh generalizado es directamente proporcional al vector

$${\displaystyle r:=Ax-\rho (x)Bx,}$$

llamado residuo de vector propio . Si un precondicionador${\displaystyle T}$Está disponible, se aplica al residuo y da como resultado el vector

$${\displaystyle w:=Tr,}$$

llamado residuo preacondicionado. Sin preacondicionamiento, establecemos${\displaystyle T:=I}$y entonces${\displaystyle w:=r}$Un método iterativo

$${\displaystyle x^{i+1}:=x^{i}+\alpha ^{i}T\left(Ax^{i}-\rho (x^{i})Bx^{i}\right),}$$

o, en resumen,

$${\displaystyle {\begin{aligned}x^{i+1}&:=x^{i}+\alpha ^{i}w^{i},\,\\w^{i}&:=Tr^{i},\,\\r^{i}&:=Ax^{i}-\rho (x^{i})Bx^{i},\end{aligned}}}$$

se conoce como ascenso (o descenso) más pronunciado precondicionado, donde el escalar${\displaystyle \alpha ^{i}}$se denomina tamaño de paso. El tamaño de paso óptimo se puede determinar maximizando el cociente de Rayleigh, es decir,

$${\displaystyle x^{i+1}:=\arg \max _{y\in \operatorname {span} \{x^{i},w^{i}\}}\rho (y)}$$

(o${\displaystyle \arg \min }$en caso de minimizar), en cuyo caso el método se denomina óptimo local.

Para acelerar drásticamente la convergencia del ascenso (o descenso) más pronunciado precondicionado localmente óptimo, se puede agregar un vector adicional a la relación de recurrencia de dos términos para convertirla en una relación de tres términos:

$${\displaystyle x^{i+1}:=\arg \max _{y\in \operatorname {span} \{x^{i},w^{i},x^{i-1}\}}\rho (y)}$$

(usar${\displaystyle \arg \min }$(en caso de minimización). La maximización/minimización del cociente de Rayleigh en un subespacio tridimensional se puede realizar numéricamente mediante el método de Rayleigh-Ritz . Agregar más vectores, como por ejemplo la extrapolación de Richardson , no produce una aceleración significativa ^{[ 8 ]} , pero aumenta los costos computacionales, por lo que generalmente no se recomienda.

A medida que las iteraciones convergen, los vectores${\displaystyle x^{i}}$y${\displaystyle x^{i-1}}$se vuelven casi linealmente dependientes , lo que resulta en una pérdida de precisión y hace que el método de Rayleigh-Ritz sea numéricamente inestable en presencia de errores de redondeo. La pérdida de precisión puede evitarse sustituyendo el vector${\displaystyle x^{i-1}}$con un vector${\displaystyle p^{i}}$, que puede estar más lejos de${\displaystyle x^{i}}$, en la base del subespacio tridimensional${\displaystyle \operatorname {span} \{x^{i},w^{i},x^{i-1}\}}$, manteniendo el subespacio sin cambios y evitando la ortogonalización o cualquier otra operación adicional. ^{[ 8 ]} Además, puede ser necesario ortogonalizar la base del subespacio tridimensional para problemas de valores propios mal condicionados para mejorar la estabilidad y la precisión alcanzable.

Esta es una versión de vector único del método LOBPCG, una de las posibles generalizaciones de los solucionadores lineales de gradiente conjugado precondicionados al caso de problemas de valores propios simétricos . ^{[ 8 ]} Incluso en el caso trivial${\displaystyle T=I}$y${\displaystyle B=I}$la aproximación resultante con${\displaystyle i>3}$será diferente de la obtenida por el algoritmo de Lanczos , aunque ambas aproximaciones pertenecerán al mismo subespacio de Krylov .

La extrema simplicidad y la alta eficiencia de la versión de vector único de LOBPCG la hacen atractiva para aplicaciones relacionadas con valores propios bajo severas limitaciones de hardware, que van desde la detección de anomalías en tiempo real basada en agrupamiento espectral mediante partición de grafos en ASIC o FPGA integrados hasta el modelado de fenómenos físicos de complejidad computacional récord en supercomputadoras de exaescala TOP500 .

Los pares propios subsiguientes pueden calcularse uno por uno mediante LOBPCG de vector único complementado con una deflación ortogonal o simultáneamente como un bloque. En el primer enfoque, las imprecisiones en los vectores propios aproximados ya calculados afectan de forma aditiva la precisión de los vectores propios calculados posteriormente, aumentando así el error con cada nuevo cálculo. Iterar varios vectores propios aproximados juntos en un bloque de forma localmente óptima en la versión de bloque de LOBPCG ^{[ 8 ]} permite un cálculo rápido, preciso y robusto de los vectores propios, incluidos aquellos correspondientes a autovalores casi múltiples donde el LOBPCG de vector único sufre de una convergencia lenta. El tamaño del bloque puede ajustarse para equilibrar la estabilidad numérica frente a la velocidad de convergencia frente a los costes computacionales de las ortogonalizaciones y el método de Rayleigh-Ritz en cada iteración.

El enfoque de bloques en LOBPCG reemplaza a los vectores individuales.${\displaystyle x^{i},\,w^{i},}$y${\displaystyle p^{i}}$con vectores de bloques, es decir matrices${\displaystyle X^{i},\,W^{i},}$y${\displaystyle P^{i}}$, donde, por ejemplo, cada columna de${\displaystyle X^{i}}$aproxima uno de los autovectores. Todas las columnas se iteran simultáneamente y la siguiente matriz de autovectores aproximados${\displaystyle X^{i+1}}$se determina mediante el método de Rayleigh-Ritz en el subespacio generado por todas las columnas de matrices${\displaystyle X^{i},\,W^{i},}$y${\displaystyle P^{i}}$Cada columna de${\displaystyle W^{i}}$se calcula simplemente como el residuo precondicionado para cada columna de${\displaystyle X^{i}.}$La matriz${\displaystyle P^{i}}$se determina de tal manera que los subespacios abarcados por las columnas de${\displaystyle [X^{i},\,P^{i}]}$y de${\displaystyle [X^{i},\,X^{i-1}]}$son lo mismo.

El resultado del método de Rayleigh-Ritz está determinado por el subespacio generado por todas las columnas de las matrices.${\displaystyle X^{i},\,W^{i},}$y${\displaystyle P^{i}}$donde una base del subespacio puede ser teóricamente arbitraria. Sin embargo, en la aritmética computacional inexacta, el método de Rayleigh-Ritz se vuelve numéricamente inestable si algunos de los vectores base son aproximadamente linealmente dependientes. Las inestabilidades numéricas suelen ocurrir, por ejemplo, si algunos de los autovectores en el bloque iterativo ya alcanzan la precisión alcanzable para una precisión computacional dada y son especialmente prominentes en baja precisión, por ejemplo, precisión simple .

El arte de implementar LOBPCG de forma diversa consiste en garantizar la estabilidad numérica del método de Rayleigh-Ritz con un coste computacional mínimo mediante la elección de una buena base del subespacio. El enfoque posiblemente más estable, que consiste en hacer que los vectores base sean ortogonales, por ejemplo, mediante el proceso de Gram-Schmidt , es también el más costoso computacionalmente. Por ejemplo, las implementaciones de LOBPCG ^{[ 9 ] [ 10 ]} utilizan la descomposición de Cholesky, inestable pero eficiente , de la matriz normal , que se realiza únicamente en matrices individuales.${\displaystyle W^{i}}$y${\displaystyle P^{i}}$, en lugar de en todo el subespacio. La cantidad de memoria de computadora en constante aumento permite tamaños de bloque típicos hoy en día en el${\displaystyle 10^{3}-10^{4}}$rango, donde el porcentaje de tiempo de cálculo dedicado a las ortogonalizaciones y el método de Rayleigh-Ritz comienzan a predominar.

Los métodos de bloques para problemas de valores propios que iteran subespacios suelen presentar convergencias más rápidas entre algunos vectores propios iterativos que otros, lo que motiva el bloqueo de los vectores propios ya convergidos, es decir, su eliminación del bucle iterativo, para evitar cálculos innecesarios y mejorar la estabilidad numérica. La simple eliminación de un vector propio puede generar su duplicado en vectores que aún se encuentran en iteración. El hecho de que los vectores propios de problemas de valores propios simétricos sean ortogonales entre sí sugiere que todos los vectores iterativos deben ser ortogonales a los vectores bloqueados.

El bloqueo puede implementarse de manera diferente manteniendo la precisión numérica y la estabilidad al tiempo que se minimizan los costos de computación. Por ejemplo, las implementaciones de LOBPCG, ^{[ 9 ] [ 10 ]} siguen, ^{[ 8 ] [ 11 ]} separando el bloqueo duro, es decir una deflación por restricción, donde los autovectores bloqueados sirven como entrada de código y no cambian, del bloqueo blando, donde los vectores bloqueados no participan en el paso iterativo típicamente más costoso de calcular los residuos, sin embargo, participan completamente en el método Rayleigh-Ritz y por lo tanto se permite que sean cambiados por el método Rayleigh-Ritz.

LOBPCG incluye todas las columnas de matrices${\displaystyle X^{i},\,W^{i},}$y${\displaystyle P^{i}}$en el método Rayleigh-Ritz, lo que resulta en un hasta${\displaystyle 3k}$-por-${\displaystyle 3k}$problema de valores propios necesario para resolver y hasta${\displaystyle 9k^{2}}$productos escalares para calcular en cada iteración, donde${\displaystyle k}$indica el tamaño del bloque: el número de columnas. Para tamaños de bloque grandes${\displaystyle k}$Esto comienza a dominar los costos de computación y E/S, y a limitar la paralelización, donde varios dispositivos de computación funcionan simultáneamente.

El artículo original de LOBPCG ^{[ 8 ]} describe una modificación, llamada LOBPCG II, para abordar dicho problema ejecutando la versión de vector único del método LOBPCG para cada par propio deseado con el procedimiento de Rayleigh-Ritz resolviendo${\displaystyle k}$de problemas de valores propios proyectados de 3x3. El procedimiento global de Rayleigh-Ritz para todos${\displaystyle k}$Los pares propios se calculan en cada iteración, pero solo en las columnas de la matriz.${\displaystyle X^{i}}$, reduciendo así el número de productos escalares necesarios a${\displaystyle k^{2}+3k}$de${\displaystyle 9k^{2}}$y el tamaño del problema global de valores propios proyectados a${\displaystyle k}$-por-${\displaystyle k}$de${\displaystyle 3k}$-por-${\displaystyle 3k}$En cada iteración. La referencia ^{[ 12 ]} va más allá al aplicar el algoritmo LOBPCG a cada vector propio aproximado por separado, es decir, ejecutar la versión sin bloqueo del método LOBPCG para cada par propio deseado durante un número fijo de iteraciones. Los procedimientos de Rayleigh-Ritz en estas ejecuciones solo necesitan resolver un conjunto de problemas de valores propios proyectados de 3 × 3. El procedimiento global de Rayleigh-Ritz para todos los pares propios deseados se aplica solo periódicamente al final de un número fijo de iteraciones sin bloqueo de LOBPCG.

Estas modificaciones pueden ser menos robustas en comparación con el LOBPCG original. Las ramas que se ejecutan individualmente en el LOBPCG de un solo vector pueden no seguir rutas iterativas continuas, sino que se invierten y crean aproximaciones duplicadas al mismo vector propio. El LOBPCG de un solo vector puede no ser adecuado para valores propios agrupados, pero las ejecuciones separadas del LOBPCG de bloques pequeños requieren que se determinen automáticamente sus tamaños de bloque durante el proceso de iteraciones, ya que el número de grupos de valores propios y sus tamaños pueden ser desconocidos a priori.