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

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

$A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^n \text{, with } n > 10^6$

$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=(\Delta - K)$$\Delta$$-6$$6$$1$

est unematrice R n × n complète qui se compose entièrement de uns.$K$$\mathbb{R}^{n \times 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=\Delta$$A=(\Delta - K)$$n$$K$

EDIT: ferait quelque chose comme

// résoudre pour x k + 1 avec Gauss-Seidel$\Delta x^{k+1} = b + Kx^{k}$$x^{k+1}$

$\rho(\Delta^{-1} K) < 1$$\rho$$\Delta^{-1} K$$n$$n=256$

$\Delta$

$\Delta \in \mathbb{R}^{n \times 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);

$n>10^6$$n \approx 10^{12}$$\Delta$$\Delta$

• Utilisez le système bordé

$$\newcommand\ee{\mathbf{e}} M = \begin{pmatrix} \Delta & \ee \\ \ee^T & 1 \end{pmatrix}$$

$\ee$

$$M \begin{pmatrix} \mathbf{x} \\ y \end{pmatrix} = \begin{pmatrix} \mathbf{b} \\ 0 \end{pmatrix}$$

en utilisant un solveur itératif ou direct.

• $A$$\Delta - \ee \ee^T$$P^{-1} \approx \Delta^{-1}$$\Delta$