Algoritmo eigenvalue divide y vencerás

Los algoritmos Divide y Vencerás eigenvalue son una clase de algoritmos eigenvalue para hermitanos o matrices reales simétricas que recientemente (cerca de 1990) se han hecho competitivos en plazo de estabilidad y eficiencia con los algoritmos más tradicionales como algoritmos QR. El concepto básico detrás de estos algoritmos es divide y vencerás llevado a las ciencias informáticas.Un problema eigenvalue se divide en dos problemas de aproximadamente la mitad del problema general; cada uno de estos problemas es resuelto recursivamente y los eigenvalue del problema original son computados a partir de los resultados de los problemas más pequeños.

Aquí presentamos la versión más sencilla de un algoritmo de dividir y vencerás, similar al originalmente propuesto por Cuppen en 1981. Muchos detalles que quedan fuera del alcance de este artículo serán omitidos; aun así, sin considerar estos detalles, el algoritmo no es plenamente estable.

Ideas principales

Como la mayoría de los algoritmos eigenvalue para matrices Hermitianas, divide y vencerás empieza con una reducción a una forma tridiagonal.  Para una matriz de $m*m$, el método estándar para este, se hace por vía de la Transformación de Householder; toma ${3 \over 4}m^{3}$ o ${8 \over 3}m^{3}$${\displaystyle }$si los eigenvectors fueran necesitados. Hay otros algoritmos, como la iteración de Arnoldi, los cuales pueden funcionar mejor para otros tipos de matrices; nosotros no profundizaremos más en estos. En ciertos casos, es posible reducir un problema eigenvalue en problemas más pequeños. Consideremos un bloque de matriz diagonal. 

$T={\bigl (}{\begin{smallmatrix}T1&0\\0&T2\end{smallmatrix}}{\bigr )}$

Los eigenvalues y eigenvectors de $T$ son sencillamente aquellos $T1$ y $T2$, y casi siempre es más rápido solucionar estos dos problemas más pequeños que solucionar todo el problema original inmediatamente. Esta técnica puede ser usada para mejorar la eficiencia de muchos algoritmos eigenvalue, pero tiene una especial importancia para dividir y vencerás. Para el resto de este artículo, asumiremos que la entrada al algoritmo de divide y vencerás es una matriz real simétrica tridimensional de $m*m$ . Además de que el algoritmo puede ser modificado para matrices Hermitianas, aquí no daremos los detalles.

Divide

La parte de dividir de divide y vencerás proviene de la realización de una tridiagonalización a la matriz, es “casi” un bloque diagonal.

El tamaño de la submatrix $T1$ la llamaremos $n*n$ y entonces $T2$ es $(m-n)*(m-n)$, notemos que el comentario sobre $T$ puede modificar el bloque diagonal dependiendo de la elección del $n$. Hay muchas maneras de descomponer la matriz. de todas formas, un sensato punto de vista es escoger el $n$ $\approx m/2$,

Nosotros escribimos $T$ como una matriz de bloque diagonal más una corrección Rank-1

La única diferencia entre $T1$ y ${\hat {T1}}$ es que el cuadrante inferior derecho $T_{nn}$ en ${\hat {T1}}$ ha sido reemplazado con $T_{nn}-\beta$ y similarmente en ${\hat {T2}}$, el cuadrante superior izquierdo ha sido reemplazado con $T_{n+1},_{n+1}-\beta$.

El resto de los pasos de la división es para resolver el eigenvalue (y si lo desea eigenvectores) de ${\hat {T1}}$ y ${\hat {T2}}$ esto es para hallar la diagonalización ${\hat {T1}}=Q_{1}D_{1}{Q_{1}}^{T}$ y ${\hat {T_{2}}}=Q_{2}D_{2}{Q_{2}}^{T}$ y puede ser complementado con llamadas recursivas al algoritmo divide y vencerás, también implementaciones prácticas a menudo cambian al algoritmo QR para submatrices suficientemente pequeñas.

Conquista

La parte de conquista del algoritmo es la parte intuitiva. Dadas las diagonalizaciones de las submatrices, sobre lo calculado.

¿Cómo encontramos la diagonalizacion de la matriz original?

Primero, definir $z^{T}=({q_{1}}^{T},{q_{1}}^{T})$ donde ${q_{1}}^{T}$ es la última fila de $Q_{1}$ y ${q_{2}}^{T}$ es la primera fila de $Q_{2}$. Ahora es elementar mostrar esto

$T={\begin{bmatrix}Q_{1}&\\&Q_{2}\end{bmatrix}}{\Biggl (}{\begin{bmatrix}D_{1}&\\&D_{2}\end{bmatrix}}+\beta zz^{T}{\biggr )}{\begin{bmatrix}{Q_{1}}^{T}&\\&{Q_{2}}^{T}\end{bmatrix}}$

La tarea pendiente ha sido reducida a encontrar el eigenvalue de una matriz diagonal más una corrección Rank-1. Antes de mostrar como hacer esto, vamos a simplificar la notación. Cuando Estamos buscando el eigenvalue de la matriz $D+ww^{T}$ donde $D$ es diagonal con distintas entradas y $w$ es algún vector con distinto de cero.

Si $w_{i}$ es cero,$(e_{i},d_{i})$ es una pareja propia de $D+ww^{T}$desde ($D+ww^{T}$) si $\lambda$ es un eigenvalue, tenemos:

$D+ww^{T}$$q=\lambda q$

donde $q$ es el correspondiente eigenvector. Ahora

$(D-\lambda I)q+w(w^{t}q)=0$

$q+(D-\lambda I)^{-1}w(w^{t}q)=0$

$W^{t}q+w^{t}(D-\lambda I)^{-1}w(w^{t}q)=0$

manten en mente que $w^{t}q$ es una escalar distinto de cero. Tampoco $w$ ni $q$ son ceros.Si $w^{t}q$ fuera a ser cero, $q$ podría ser un eigenvector de $D$ para $(D+ww^{t})q=\lambda q$. Si este fuera el caso, $q$ contiene solo una posición distinta de cero en una diagonal distinta de $D$, de esta manera el producto interno $w^{t}q$ no puede ser cero después de todo. Por lo tanto, tenemos

$1+w^{t}{D-\lambda I}^{-}1w=0$

o escrito como una ecuación escalar:

$1+\textstyle \sum _{j=1}^{m}\displaystyle {\operatorname {w_{j}} ^{2} \over \operatorname {d_{j}+\lambda } }$ ;

Esta ecuanción es conocida como la ecuación escalar. Por tanto el problema ha sido reducido a encontrar las raíces de la función racional definida por la parte izquierda de esta ecuación.

Generalmente el algoritmo Eigenvalue debe ser iterativo y el algoritmo divide y vencerá no es diferente. Resolver la ecuación secular no linear requiere una técnica iterativa, como el método Newton-Raphson. Igualmente cada raíz puede ser hallada en $O(1)$ iteración, cada una requiere $\Theta (m)$ descenso (para una función de grado $m$), haciendo el costo de la parte iterativa de este algoritmo $\Theta (m^{2})$.${\displaystyle }$

Análisis

Como es común el algoritmo divide y vencerás, utilizaremos el Teorema Maestro para analizar el tiempo de ejecución. Recordar que con estas condiciones escojemos $n$ $\approx m/2$. Podemos escribir la relación recurrente:

$T(n)=2xT(\operatorname {n} /\operatorname {2} )+\Theta (m^{2})$

En la notación del Teorema Maestro,$a=b=2$ y así ${log_{b}}^{a}=1$. Claramente, $\Theta (m^{2})$=$\Omega (m)$ , entonces tenemos

$T(n)=\Theta (m^{2})$.

Recordar que señalamos reducir la matriz hermitiana a forma tridiagonal toma ${3 \over 4}m^{3}$ . Estos tiempos son pequeñps para el tiempo de ejecución de la parte dividen y vencerás, y en este punto no está claro que ventajas ofrece el algoritmo divide y vencerás frente al algoritmo QR (que también usa $\Theta (m^{2})$ para las matrices tridiagonales). La ventaja de divide y vencerás se muestra cuando se necesitan eigenvector. Si este es el caso, la reducción a forma tridiagonal será ${8 \over 3}m^{3}$, pero la segunda parte del algoritmo será $\Theta (m^{3})$. Para el algoritmo QR con una precisión razonable, esto es $\approx 6m^{3}$ considerando que para dividir y conquistar esto es ${3 \over 4}m^{3}$.
La razón de esta mejora en divide y vencerás es que el $\Theta (m^{3})$ parte del algoritmo (multiplicando $Q$ matrices) está separada de la iteración, mientras que en el QR, esto ocurre en cada paso de la iteración. Sumando el ${8 \over 3}m^{3}$ de la reducción, el total de mejoras es desde $9m^{3}\thickapprox 4m^{3}$.
El uso práctico del algoritmo divide y vencerás ha mostrado en los más realistas problemas eigenvalues, funciona mejor que lo estimado. La razón es que muy a menudo las matrices $Q$ y los vectores $z$ tienden a ser numéricamente dispersos, esto significa que tienen muchas entradas con valores más pequeños que la precisión punto flotante, admitiendo deformaciones numérica, i.e. separando el problema en subproblemas separados.

Existen técnicas especializadas de búsqueda de raíces que funcionarian mejor que el método de Newton-Raphson en ambos términos rendimiento y estabilidad. Estos pueden ser usados para mejorar la parte iterativa del algoritmo divide y vencerás.

Variantes e implementación

El algoritmo presentado aquí es la versión más sencilla. En muchas implementaciones prácticas más complicadas correcciones Rank-1 son usadas para garantizar estabilidad. Incluso algunas variantes usan correcciones Rank-2.

Existen técnicas especializadas de búsqueda de raíces que funcionarían mejor que el método de Newton-Raphson en ambos términos rendimiento y estabilidad. Estos pueden ser usados para mejorar la parte iterativa del algoritmo divide y vencerás.

El algoritmo divide y vencerás es fácilmente paralelizado y computarizado en paquetes de álgebra lineal así como LAPACK contiene implementaciones paralelas de una alta calidad

Referencias

• Demmel, James W. (1997), Aplicado Álgebra Lineal Numérica, Filadelfia, PA: Society for industrial and Applied Mathematics,​ ISBN 0-89871-389-7, MR1463942 .

• Datos: Q5283998