Rozwiązywanie ogromnego gęstego układu liniowego?

Czy jest jakaś nadzieja na skuteczne rozwiązanie następującego układu liniowego za pomocą metody iteracyjnej?

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

$Ax=b$

z

Δ - 6 6 $A=(\Delta - K)$ , gdzie jest bardzo rzadką macierzą o kilku przekątnych, wynikającą z dyskretyzacji Operatora Laplace'a. Na głównej przekątnej znajduje się i jest innych przekątnych z na niej.$\Delta$$-6$$6$$1$

R n × $K$ jest pełną macierzą , która składa się całkowicie z nich.$\mathbb{R}^{n \times n}$

Rozwiązanie działa dobrze z iteracyjnymi metodami, takimi jak Gauss-Seidel, ponieważ jest to rzadka macierz diagonalnie dominująca. Podejrzewam, że problem jest praktycznie niemożliwy do skutecznego rozwiązania dla dużej liczby , ale czy jest jakiś sposób, aby go rozwiązać, wykorzystując strukturę ?$A=\Delta$$A=(\Delta - K)$$n$$K$

EDYCJA: Zrobiłbym coś takiego

x k + $\Delta x^{k+1} = b + Kx^{k}$ // rozwiąż dla pomocą Gaussa-Seidela$x^{k+1}$

konwergować do właściwego rozwiązania? Czytam, że taka metoda podziału jest zbieżna, jeśli , gdzie jest normą spektralną. Ręcznie obliczyłem wartości własne dla niektórych różnych małych wartości a wszystkie one wynoszą zero, z wyjątkiem tej, która ma dość wysoką wartość ujemną. (około ~ 500 dla ) Myślę więc, że to nie zadziała.ρ Δ - 1 K n n = $\rho(\Delta^{-1} K) < 1$$\rho$$\Delta^{-1} K$$n$$n=256$

EDYCJA: Więcej informacji o$\Delta$ :

$\Delta \in \mathbb{R}^{n \times n}$ jest symetryczny i jest zdecydowanie ujemny i dominuje po przekątnej.

Jest on tworzony w Matlab w następujący sposób

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$

• Użyj systemu granicznego

gdzie to wektor kolumnowy składający się ze wszystkich i rozwiązujący system$\ee$

za pomocą iteracyjnego lub bezpośredniego solvera.

• Użyj metody Kryłowa i zastosuj macierz jako (tj. Macierz rzadką plus poprawkę rangi 1. Użyj istniejącego warunku wstępnego lub , szczególnie jeśli chcesz użyć bezpośredniego rozwiązania z , zaktualizuj go za pomocą formuły Sherman-Morrison .Δ - e e T P - 1 ≈ Δ - 1$A$$\Delta - \ee \ee^T$$P^{-1} \approx \Delta^{-1}$$\Delta$