Résoudre un énorme système linéaire dense?

11

Y a-t-il un espoir de résoudre efficacement le système linéaire suivant avec une méthode itérative?

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

Ax=b

avec

, où Δ est une matrice très clairsemée avec quelques diagonales, résultant de la discrétisation de l'opérateur de Laplace. Sur sa diagonale principale, il y a - 6 et il y a 6 autres diagonales avec 1 dessus.A=(ΔK)Δ661

est unematrice R n × n complète qui se compose entièrement de uns.KRn×n

Résoudre fonctionne bien avec des méthodes itératives comme Gauss-Seidel, car c'est une matrice à dominante diagonale clairsemée. Je soupçonne que le problème A = ( Δ - K ) est à peu près impossible à résoudre efficacement pour un grand nombre de n , mais y a-t-il une astuce pour le résoudre, en exploitant la structure de K ?A=ΔA=(ΔK)nK

EDIT: ferait quelque chose comme

// résoudre pour x k + 1 avec Gauss-SeidelΔxk+1=b+Kxkxk+1

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

Δ

ΔRn×n

Il est créé de la manière suivante dans 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);

yon
la source
Δ
Δ
La Woodbury Matrix Identity vous aide-t-elle puisque K est de bas rang?
Aron Ahmadia

Réponses:

14

n>106n1012ΔΔ

  • Utilisez le système bordé

M=(ΔeeT1)

e

M(xy)=(b0)

en utilisant un solveur itératif ou direct.

  • AΔeeTP1Δ1Δ
Jed Brown
la source
KAzh=Δzy=he(eTz)z
Wolfgang Bangerth