9 votos

Algoritmo rápido para aproximar la distribución del valor propio de matriz escasa grande

Estoy interesado en el autovalor de distribución de un gran $2^{16}$x$2^{16}$ Hermitian matriz dispersa con espectro contenida en $[-1,1]$. Que es que no necesita saber todos los autovalores exactamente, sino más bien el número aproximado de autovalores, digamos, en los intervalos de $[-1,-0.99],\dots,[0.99,1]$.

El comando de Matlab eig falla debido a que no aceptan las matrices dispersas y la matriz es demasiado grande para ser almacenados como una normal de la matriz. El comando eigs no me ayuda mucho ya que solo me da la $k$ mayores autovalores y tarda una eternidad.

Son el rápido aproximado de algoritmos para la aproximación de la densidad espectral?

6voto

Algebraic Pavel Puntos 11952

Se puede aplicar un enfoque común se conoce como el espectro de rebanar. Suponga que $M$ es un Hermitian matriz factorizada como $$\tag{1}M=LDL^*$$ (a complex variant of the $LDL^T$ factorisation), where $L$ is unit lower triangular and $D$ diagonal. The inertia (the number of negative, zero, and positive eigenvalues) of $M$ and $D$ is the same and since $D$ is diagonal, you can get the inertia of $M$ pretty easily.

Now fix a $\sigma\in\mathbb{R}$. The eigenvalues of $M-\sigma I$ (where $I$ is the identity matrix) are the eigenvalues of $M$ minus $\sigma$. Considere la posibilidad de la factorización $$ M-\sigma I=L_{\sigma}D_{\sigma}L_{\sigma}^*. $$ Tanto en $M-\sigma I$ $D_{\sigma}$ tiene de nuevo la misma inercia de modo que, por ejemplo, el número de negativos en las entradas de la diagonal de a $D_{\sigma}$ determina el número de valores propios de a $M$ menor que $\sigma$.

En tu caso, ya que usted sabe que el espectro de $M$ está contenida en el intervalo de $[-1,1]$, se deben realizar sólo dos factorisations para determinar cuántos valores propios están contenidas en los intervalos de $[-1,-\alpha)$ $(\alpha,1]$ algunos $\alpha\in(0,1)$. En particular, $$ M+\alpha I=L_+D+L_+^*, \quad\text{y}\quad M-\alpha I=L_-D_-L_-^*. $$ Entonces, el número de negativos diagonal entradas en $D_+$ le da el número de autovalores de a $M$ menor que $-\alpha$ {es decir, en el intervalo de $[-1,-\alpha)$} y el número de resultados positivos de las entradas de la diagonal de a $D_-$ da el número de autovalores de a $M$ mayor que $\alpha$ {es decir, en el intervalo de $(\alpha,1]$}.

En MATLAB, la factorización usted busca está implementado en la función ldl.

En realidad, también se podría usar eigs a calcular, dicen, $k$ autovalores de mayor magnitud (es decir, cerca de los límites del intervalo de $[-1,1]$) y comprobar si el resultado te dio un autovalor con una magnitud menor que $\alpha$ con ambos signos). Si es así, entonces el resultado de eigs contiene todos los autovalores de a $[-1,-\alpha)$ $(\alpha,1]$ además de algunos valores fuera de estos intervalos. Si este criterio no se cumple, es necesario aumentar la $k$. Por supuesto, esto puede ser bastante costoso, especialmente si los autovalores se agruparán en torno a $-1$ $1$ lo cual requeriría el uso relativamente alto $k$.

P. S.: La matriz $D$ generalmente no es diagonal, pero el bloque diagonal con $1\times 1$ $2\times 2$ bloques. Aún así, los autovalores de a $D$ (y, por tanto, los signos que importa aquí) pueden obtenerse fácilmente.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X