4 votos

¿Solucionadores laplacianos para la inversión de matrices de gran tamaño?

Tengo una gran matriz L de tamaño 400.000 $\times $ 400,000 . Estoy utilizando esta matriz L de la siguiente manera.

Lin = L $^{-1}$

C = D - B * Lin * B';

B,D son de tamaños adecuados. La matriz L es dispersa y no tiene ninguna estructura particular.

A partir de C que es una matriz densa estoy calculando el fondo $m$ ~ $10$ eigenvectores para realizar otros cálculos.

En el mundo real, el tamaño de la matriz L será mucho mayor.

¿Puede alguien indicarme alguna bibliografía o solucionador que pueda resolver este problema?

Gracias, señor.

1 votos

No soy un experto, pero probablemente no quieras invertir matrices grandes por razones numéricas.

0 votos

@YuvalFilmus : sí , por lo que he leído la inversión es del orden de n^3 por lo tanto computar la inversión para matrices muy grandes no es una buena idea. Pero no estoy seguro de cómo hacerlo de otra manera. cualquier ayuda será apreciada.

0 votos

En realidad quería decir numérico estabilidad no el tiempo de ejecución, que, como usted señala, también es un problema. Quizá pueda decirnos qué problema quiere resolver realmente. Además, haciendo caso omiso de las cuestiones numéricas y de otro tipo, puede invertir matrices en $O(n^{2.373})$ (aunque la constante oculta es muy, muy grande).

3voto

Algebraic Pavel Puntos 11952

Por lo que he entendido del problema, quieres calcular unos cuantos vectores propios asociados a los valores propios más pequeños de $C:=D-BL^{-1}B^T$ (probablemente $C$ es simétrica y definida positiva). Dado que las matrices implicadas son dispersas, puede utilizar métodos basados en el método de Arnoldi implementado, por ejemplo, en ARPACK . Una buena característica de estos métodos es que no es necesario calcular $C$ explícitamente, sino que debes ser capaz de calcular productos matriz-vector.

Una cuestión que se plantea aquí es que, puesto que se desea calcular los vectores propios de la parte "inferior" del espectro (¿significa menor en magnitud si $C$ no es SPD?), puede que necesite utilizar un análogo de la iteración de potencia inversa, es decir, necesita poder calcular matvecs con la función inversa de $C$ o, lo que es lo mismo, resolver sistemas de la forma $Cx=f$ para vectores del lado derecho dados $f$ .

La matriz $C$ tiene la forma de complemento de Schur y, como ya se ha notado, $L^{-1}$ es densa como suele ocurrir al intentar invertir matrices dispersas, por lo que invertirla o intentar calcular $C$ explícitamente de alguna manera no es una buena opción. Si $C$ estaba bien acondicionado, puede resolver $Cx=f$ iterativamente, por ejemplo, mediante gradientes conjugados o GMRES. Estos métodos, de forma similar al método Arnoldi de ARPACK, sólo requieren productos con $C$ por lo que se podría, por ejemplo, factorizar $L$ y luego el producto con $C$ sólo implica multiplicaciones con $B$ , $B^T$ , $D$ y la solución de un sistema con $L$ : $$ \begin{align} g=Cu=(D-BL^{-1}B^T)u: && &v:=B^Tu,\\ && &\text{solve}\;Lw=v,\\ && &g:=Du+Bw. \end{align} $$ Un posible inconveniente es que si $C$ estuviera mal condicionado, la convergencia del GC podría ser lenta.

Si no tienes miedo de factorizar o resolver de cualquier otra forma sistemas indefinidos dispersos, también puedes considerar la siguiente alternativa sobre cómo obtener la solución de $Cx=f$ . Consideremos el sistema "aumentado $$\tag{$ * $} Mu:=\pmatrix{L&B^T\\B&-D}\pmatrix{y\\x}=\pmatrix{0\\-f}. $$ Puede comprobar que el $x$ -componente del vector solución $u$ resuelve $Cx=f$ . Este enfoque tiene una pequeña desventaja: dependiendo de las propiedades de sus matrices, $M$ puede ser indefinido, por lo que hay que tener cuidado al factorizarlo. No obstante, los factores de $M$ son más propensos a ser escasos.

Para más información sobre cómo resolver sistemas como ( $*$ ), véase, por ejemplo este documento . En él se puede encontrar un buen resumen de los métodos para resolver este tipo de problemas, incluidas muchas referencias (aunque el artículo se publicó hace ya algunos años).

0 votos

Excelente respuesta; muchas gracias también por el enlace al artículo; estoy trabajando en programación no lineal no convexa y esto puede ser de gran utilidad. Muchas gracias de nuevo.

1 votos

@Autolatry ¡De nada! No sé qué son exactamente las matrices, pero como está relacionado con grafos laplacianos y resolución de sistemas con ellos, también podrías echar un vistazo en este documento . También hay un montón de artículos interesantes que lo citan (véase la lista en Google Scholar) que podrían ser útiles.

0 votos

Muchas gracias pero me temo que ese enlace debe estar roto ya que veo un 404. Muchas gracias.

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