¿Se pueden resolver los sistemas lineales simétricos diagonales más fijos en tiempo cuadrático después de la precomputación?

21

¿Existe un método $O(n^3+n^2 k)$ para resolver $k$ sistemas lineales de la forma $(D_i + A) x_i = b_i$ donde $A$ es una matriz SPD fija y $D_i$ son matrices diagonales positivas?

Por ejemplo, si cada $D_i$ es escalar, es suficiente para calcular la SVD de $A$ . Sin embargo, esto se rompe para el general $D$ debido a la falta de conmutatividad.

Actualización : las respuestas hasta ahora son "no". ¿Alguien tiene alguna intuición interesante de por qué? Una respuesta sin respuesta significa que no hay una forma no trivial de comprimir la información entre dos operadores que no viajan diariamente. No es terriblemente sorprendente, pero sería genial entenderlo mejor.

linear-algebra algorithms performance complexity Geoffrey Irving
fuente

SPD = definido semi positivo?

rcollyer

Sí, aunque el problema es esencialmente el mismo sin SPD. Agregué esa restricción solo para asegurar que los sistemas nunca sean singulares.

Geoffrey Irving

19

Las respuestas positivas más cercanas a su pregunta que pude encontrar son las perturbaciones diagonales dispersas (ver más abajo).

Dicho esto, no conozco ningún algoritmo para el caso general, aunque hay una generalización de la técnica que mencionó para los cambios escalares de las matrices SPD a todas las matrices cuadradas:

Dada cualquier matriz cuadrada , existe una descomposición de Schur , donde es unitaria y es triangular superior, y proporciona una descomposición de Schur de . Por lo tanto, su idea de precomputación se extiende a todas las matrices cuadradas a través del algoritmo: $A$ $A=U T U^H$ $U$ $T$ $A+\sigma I = U (T + \sigma I) U^H$ $A + \sigma I$

Calcule en el trabajo de como máximo . $[U,T]=\mathrm{schur}(A)$ $\mathcal{O}(n^3)$
Resuelva cada través de en el trabajo (la inversión media es simplemente la sustitución inversa). $(A+\sigma I) x = b$ $x := U (T +\sigma I)^{-1} U^H b$ $\mathcal{O}(n^2)$

Esta línea de razonamiento se reduce al enfoque que mencionó cuando es SPD ya que la descomposición de Schur se reduce a un EVD para matrices normales, y el EVD coincide con el SVD para matrices definidas positivas de Hermit. $A$

Respuesta a la actualización: hasta que tenga una prueba, que no tengo, me niego a afirmar que la respuesta es "no". Sin embargo, puedo dar algunas ideas de por qué es difícil, así como otro subcampo donde la respuesta es sí.

La dificultad esencial es que, a pesar de que la actualización es diagonal, todavía está en rango completo, por lo que la herramienta principal para actualizar un inverso, la fórmula de Sherman-Morrison-Woodbury , no parece ayudar. Aunque el caso de desplazamiento escalar también es de rango completo, es un caso extremadamente especial ya que conmuta con cada matriz, como mencionó.

Dicho esto, si cada era escasa, es decir, cada uno tenía nonzeros, entonces la fórmula de Sherman-Morrison-Woodbury produce una solución de con cada par . Por ejemplo, con un único distinto de cero en la entrada diagonal , de modo que : $D$ $\mathcal{O}(1)$ $\mathcal{O}(n^2)$ $\{D,b\}$ $j$ $D=\delta e_j e_j^H$

[A^{- 1} + δ e_{j} e_{j}^{H}]^{- 1} = A^{- 1} - \frac{δ A^{- 1} e_{j} e_{j}^{H} A^{- 1}}{1 + δ (e_{j}^{H} A^{- 1} e_{j})},

$[A^{-1}+\delta e_j e_j^H]^{-1} = A^{-1} - \frac{\delta A^{-1} e_j e_j^H A^{-1}}{1+\delta (e_j^H A^{-1} e_j)},$

donde es el ésimo vector base estándar . $e_j$ $j$

Otra actualización: debo mencionar que probé el preacondicionador que @GeoffOxberry sugirió en algunas matrices SPD aleatorias usando PCG y, tal vez no sea sorprendente, parece reducir en gran medida el número de iteraciones cuando es pequeño, pero no cuando es o mayor. $A^{-1}$ $1000 \times 1000$ $||D||_2/||A||_2$ $\mathcal{O}(1)$

Jack Poulson
fuente

12

Si es diagonalmente dominante para cada , entonces el trabajo reciente de Koutis, Miller y Peng (ver el sitio web de Koutis para el trabajo sobre matrices simétricas diagonalmente dominantes) podría usarse para resolver cada sistema en tiempo (en realidad tiempo, donde es el número máximo de entradas distintas de cero en sobre todo $(D_{i} + A)$ $i$ $\mathcal{O}(n^2 \log(n))$ $\mathcal{O}(m\log(n))$ $m$ $(D_{i} + A)$ , para que puedas aprovechar la escasez también). Entonces, el tiempo total de ejecución sería , que es mejor que elenfoque de resolver cada sistema ingenuamente usando álgebra lineal densa, pero un poco peor que el tiempo de ejecución cuadrático lo pides. $i$ $\mathcal{O}(n^2 \log(n) k)$ $\mathcal{O}(n^3 k)$

Escasez significativa en para todos podría ser explotada por solucionadores dispersas para producir un algoritmo, pero supongo que si había escasez significativa, entonces habría mencionado. $(D_{i} + A)$ $i$ $\mathcal{O}(n^2 k)$

También puede usar como preacondicionador para resolver cada sistema utilizando métodos iterativos y ver cómo funciona. $A^{-1}$

Respuesta a la actualización : @JackPaulson hace un gran punto desde el punto de vista de álgebra lineal numérica y algoritmos. Me centraré en los argumentos de complejidad computacional.

La complejidad computacional de la solución de sistemas lineales y la complejidad computacional de la multiplicación de matrices son esencialmente iguales. (Consulte la teoría de la complejidad algebraica ). Si puede encontrar un algoritmo que pueda comprimir la información entre dos operadores que no viajan (ignorando la parte semidefinida positiva) y resolver directamente la colección de sistemas que propone en tiempo cuadrático en , entonces es es probable que pueda usar dicho algoritmo para hacer inferencias sobre una multiplicación de matriz más rápida. Es difícil ver cómo se podría usar una estructura semidefinida positiva en un método denso y directo para que los sistemas lineales disminuyan su complejidad computacional. $n$

Al igual que @JackPaulson, no estoy dispuesto a decir que la respuesta es "no" sin una prueba, pero dadas las conexiones anteriores, el problema es muy difícil y de interés para la investigación actual. Lo mejor que podría hacer desde un punto de vista asintótico sin aprovechar una estructura especial es una mejora en el algoritmo de Coppersmith y Winograd, obteniendo un algoritmo , donde . Ese algoritmo sería difícil de codificar y probablemente sería lento para matrices pequeñas, porque el factor constante que precede a la estimación asintótica es probablemente enorme en relación con la eliminación gaussiana. $\mathcal{O}(n^{\alpha}k)$ $\alpha \approx 2.375$

Geoff Oxberry
fuente

3

Todavía no he visto una declaración concreta de dónde podría estar el crossover, pero varias fuentes acreditadas han declarado que (dejando de lado los problemas de implementación), Coppersmith-Winograd no puede superar los métodos estándar para tamaños de matriz que podrán caber en la memoria en un futuro próximo. (unas pocas décadas). Dado que el punto de referencia de Linpack tarda más de un día en ejecutarse en las mejores máquinas actuales, no parece probable que Coppersmith-Winograd se use en la práctica. Strassen es realmente práctico para grandes problemas, aunque es algo menos estable numéricamente.

Jed Brown

Eso no me sorprende. +1 para los detalles de implementación.

Geoff Oxberry

6

Se puede usar una expansión de Taylor de primer orden para mejorar la convergencia sobre el retraso simple. Supongamos que tenemos un preacondicionador (o factores para una resolución directa) disponible para , y queremos utilizarlo para el preacondicionamiento . Podemos calcular $A+D$ $A$

\begin{aligned} A^{- 1} & = (A + D - D)^{- 1} (A + D) (A + D)^{- 1} \\ = [(A + D)^{- 1} (A + D - D)]^{- 1} (A + D)^{- 1} \\ = [I - (A + D)^{- 1} D]^{- 1} (A + D)^{- 1} \\ \approx [I + (A + D)^{- 1} D] (A + D)^{- 1} \end{aligned}

$\begin{align} A^{-1} &= (A+D-D)^{-1} (A+D) (A+D)^{-1} \\ &= [(A+D)^{-1} (A+D-D)]^{-1} (A+D)^{-1} \\ &= [I - (A+D)^{-1} D]^{-1} (A+D)^{-1} \\ &\approx [I + (A+D)^{-1} D] (A+D)^{-1} \end{align}$

$A+D$

$D\gtrsim 0$ $D \lesssim \min \sigma(A)$

$\sqrt 2$ $A+D$ $A+D$ ), entonces este método de primer orden puede tener sentido.

Jed Brown
fuente

¿Se pueden resolver los sistemas lineales simétricos diagonales más fijos en tiempo cuadrático después de la precomputación?

Respuestas: