Resolviendo

Tengo matrices y . es escaso y es con muy grande (puede ser del orden de varios millones). es una matriz alta de con bastante pequeño ( ) y cada columna solo puede tener una sola entrada con el resto siendo 's, de tal manera que . es enorme, por lo que es muy difícil invertir, y puedo resolver un sistema lineal como $A$ $G$ $A$ $n\times n$ $n$ $G$ $n\times m$ $m$ $1 \lt m \lt 1000$ $1$ $0$ $G^TG = I$ $A$ usando iterativamente un método de subespacio de Krylov como , pero no tengo explícitamente. $Ax = b$ $\mathrm{BiCGStab}(l)$ $A^{-1}$

Quiero resolver un sistema de la forma: , donde y son vectores de longitud . Una forma de hacerlo es usar un algoritmo iterativo dentro de un algoritmo iterativo para resolver para cada iteración del algoritmo iterativo externo. Sin embargo, esto sería extremadamente costoso computacionalmente. Me preguntaba si hay una manera computacionalmente más fácil de resolver este problema. $(G^TA^{-1}G)x = b$ $x$ $b$ $m$ $A^{-1}$

linear-algebra linear-solver sparse-matrix krylov-method Costis
fuente

Acabo de agregar a mi respuesta un comentario sobre la explotación de la estructura 0-1.

Arnold Neumaier

Respuestas:

Introduzca el vector y resuelva el sistema acoplado grande , para simultáneamente, utilizando un método iterativo. Si es simétrico (como parece probable aunque no lo diga explícitamente), entonces el sistema es simétrico (pero indefinido, aunque cuasidefinito si $y:=-A^{-1}Gx$ $Ay+Gx=0$ $G^Ty=-b$ $(y,x)$ $A$ $A$ es positivo definido), lo que podría ayudarlo a elegir un método apropiado. (palabras clave relevantes: matriz KKT, matriz cuasidefinita).

Editar: como es simétrico complejo, también lo es la matriz aumentada, pero no hay cuasidefinidad. Sin embargo, puede utilizar la rutina para calcular ; por lo tanto, podría adaptar un método como QMR ftp://ftp.math.ucla.edu/pub/camreport/cam92-19.pdf (diseñado para sistemas reales, pero puede reescribirlo fácilmente para sistemas complejos, utilizando el adjunto en lugar de la transposición) para resolver su problema. $A$ $Ax$ $A^*x=\overline{A\overline x}$

Edit2: En realidad, la estructura (0,1) de significa que puede eliminar y los componentes de simbólicamente, terminando así con un sistema más pequeño para resolver. Esto significa jugar con la estructura de , y paga solo cuando se da explícitamente en formato disperso en lugar de como un operador lineal. $G$ $x$ $G^Ty$ $A$ $A$

Arnold Neumaier
fuente

¡Gracias! A es complejo simétrico. ¿Hay alguna razón para esperar que la condición de la matriz aumentada sea peor que la de la matriz original

? Si m es pequeño, la matriz aumentada tiene un tamaño marginalmente mayor que A, por lo que sospecho que resolver este sistema aumentado de forma iterativa no debería ser mucho más difícil que resolver un sistema con A.

A

$A$

Costis

El número de condición de los dos sistemas generalmente no está relacionado; depende mucho de lo que es

- Agregué a mi respuesta información sobre cómo explotar la simetría compleja.

G

$G$

Arnold Neumaier

¡Hola chicos! Gracias por todas las respuestas; Este lugar es genial! Una extensión de la pregunta original: supongamos ahora que tengo

, donde G y A tienen el mismo significado que en la pregunta original pero B es una matriz nxn deficiente en rango ( mismo tamaño que A) y todo

es rango completo. ¿Cómo resolvería el nuevo sistema, ya que ahora no existe el inverso de B, por lo que no puede tener

(G^{T} A^{- H} B A^{- 1} G) x = b

$(G^TA^{-H}BA^{-1}G)x=b$

G^{T} A^{- H} B A^{- 1} G

$G^TA^{-H}BA^{-1}G$

A B^{- 1} A^{H}

$AB^{-1}A^H$ . No creo que funcione simplemente con el pseudoinverso de B tampoco.

Costis

Introduzca

, y proceda en analogía con el caso resuelto. (Posiblemente también necesite factorizar

en matrices de rango completo e introducir un vector intermedio adicional).

y := A^{- 1} G x

$y:=A^{-1}Gx$

z := A^{- H} B y

$z:=A^{-H}By$

B

$B$

Arnold Neumaier

Hola arnold Gracias, esto realmente funciona! Lo probé con algunos ejemplos de prueba muy pequeños, y funciona muy bien. Sin embargo, mi solucionador iterativo está teniendo grandes problemas para invertir la matriz aumentada. Si bien solo se necesitan unas 80 iteraciones (unos segundos) para resolver un sistema de la forma

con la matriz A original, el sistema con la matriz aumentada (que es 2n + mx 2n + mo 2n-mx 2n- m usando el enfoque de @ wolfgang-bangerth) toma decenas de miles de iteraciones (varias horas) para resolver un RHS. ¿Hay alguna estrategia para acelerar la convergencia? tal vez un preacondicionador?

A x = b

$Ax=b$

Costis

Después de la respuesta de Arnold, hay algo que puede hacer para simplificar el problema. Específicamente, reescriba el sistema como . Luego, tenga en cuenta que, a partir de la afirmación de que es alto y angosto y que cada fila tiene solo un 1 y ceros, de lo contrario, la afirmación significa que un subconjunto de los elementos de tiene un valor fijo, es decir, los elementos de . $Ay+Gx=0, G^Ty=-b$ $G$ $G^Ty=-b$ $y$ $-b$

Digamos que para simplificar que tiene columnas filas y que exactamente las primeras filas tienen unas y que reordenando los elementos de , puedo hacer que tenga la matriz de identidad en la parte superior y una matriz cero en la parte inferior. Entonces puedo dividir en "restringidos" y "libres" para que $G$ $m$ $n$ $m$ $x$ $G$ $m \times m$ $n-m \times m$ $y=(y_c,y_f)$ $m$ $n-m$ . También puedo dividir para que . De la ecuación , obtengo lo siguiente: $y_c=-b$ $A$ $A=\begin{pmatrix} A_{cc} & A_{cf} \\ A_{fc} & A_{ff} \end{pmatrix}$ $Ay+Gx=0$ y usando lo que sabemos sobre que tenemos de la segunda de estas ecuaciones y consecuentemente En otras palabras, la única matriz que tiene que invertir es el subconjunto de

A_{c c} y_{c} + A_{c f} y_{f} + x = 0, A_{f c} y_{c} + A_{f f} y_{f} = 0

$A_{cc} y_c + A_{cf} y_f + x = 0, \\ A_{fc} y_c + A_{ff} y_f = 0$

y_{c}

$y_c$

A_{f f} y_{f} = A_{f c} b

$A_{ff} y_f = A_{fc} b$

x = A_{c c} b - A_{c f} A_{f f}^{- 1} A_{f c} b .

$x = A_{cc} b - A_{cf} A_{ff}^{-1} A_{fc} b.$

A

$A$ cuyas filas y columnas no se mencionan en

(el espacio nulo de

). Esto se puede hacer fácilmente: (i) calcular

; (ii) use cualquier solucionador que tenga para resolver

; (iii) calcule

G

$G$

G

$G$

z = A_{f c} b

$z=A_{fc} b$

A_{f f} h = z

$A_{ff} h = z$

x = A_{c c} b - A_{c f} h

$x = A_{cc} b - A_{cf} h$

En otras palabras, dada la estructura de , resolviendo el sistema lineal que tiene en realidad no es más difícil que la solución de un solo sistema lineal con . $G$ $A$

Wolfgang Bangerth
fuente

$G$ $G^T$ $A$

$G^T A^{-1} G x = b$

$G G^T A^{-1} G x = G b$

$G^T G = I$ $G^T = G^{-1}$ $G G^T=I$

$A^{-1} G x = G b$

$A A^{-1} G x = A G b$

$G x = A G b$

$G^T G x = G^T A G b$

$x = G^T A G b$

$G$ $A$ $b$

Phil H
fuente

G^{T}

$G^T$

G

$G$

G = e_{1}

$G=e_1$

G^{T} = e_{1}^{T}

$G^T=e_1^T$

G G^{T} = e_{1} e_{1}^{T} \neq I

$GG^T=e_1e_1^T\neq I$

G \in C^{n} \otimes C^{m}

$G\in \mathbb{C}^n\otimes \mathbb{C}^m$

G^{T} G = I_{m \times m}

$G^TG=I_{m\times m}$

G G^{T} \neq I_{n \times n}

$GG^T\ne I_{n\times n}$