¿Resolviendo un enorme sistema lineal denso?

11

¿Hay alguna esperanza en resolver el siguiente sistema lineal de manera eficiente con un método iterativo?

ARn×n,xRn,bRn, with n>106

Ax=b

con

, donde Δ es una matriz muy escasa con algunas diagonales, que surge de la discretización del operador de Laplace. En su diagonal principal hay - 6 y hayotras 6 diagonales con 1 en él.A=(ΔK)Δ661

es unamatriz R n × n completa que consta completamente de unos.KRn×n

Resolver funciona bien con métodos iterativos como Gauss-Seidel, porque es una matriz escasamente dominante en diagonal. Sospecho que el problema A = ( Δ - K ) es prácticamente imposible de resolver de manera eficiente para grandes números de n , pero ¿hay algún truco para resolverlo, explotando la estructura de K ?A=ΔA=(ΔK)nK

EDITAR: Haría algo como

// resolver para x k + 1 con Gauss-SeidelΔxk+1=b+Kxkxk+1

ρ(Δ1K)<1ρΔ1Knn=256

Δ

ΔRn×n

Se crea de la siguiente manera en matlab

n=W*H*D;

e=ones(W*H*D,1);

d=[e,e,e,-6*e,e,e,e];

delta=spdiags(d, [-W*H, -W, -1, 0, 1, W, W*H], n, n);

a lo lejos
fuente
Δ
Δ
¿ Le ayuda la identidad de la matriz de Woodbury ya que K es de rango bajo?
Aron Ahmadia

Respuestas:

14

n>106n1012ΔΔ

  • Usa el sistema de borde

M=(ΔeeT1)

e

M(xy)=(b0)

utilizando un solucionador iterativo o directo.

  • Use un método de Krylov y aplique la matriz como ΔAΔeeTP1Δ1Δ
Jed Brown
fuente
Tiendo a pensar que estás mucho mejor con el segundo enfoque. El punto simplemente es que no debe tratar de almacenar la matriz en la memoria ni tratar de hacer un producto de matriz de vectores con ella. Por el contrario, cada vez que tiene que multiplicar con A con un vector z en su esquema iterativo, multiplica h = ΔKAzh=Δzy=he(eTz)z
Wolfgang Bangerth