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$

$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$

$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

$\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. $\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);

linear-solver dense-matrix linear-system

— tam
źródło

Czy możesz podać więcej informacji na temat ? Symetryczny? Określony, półokreślony, nieokreślony?

Δ

$\Delta$

— Stefano M

Δ

$\Delta$ jest symetryczna i ujemna.

— dniu

Czy Woodbury Matrix Identity pomaga ci, ponieważ K jest niskiej rangi?

— Aron Ahmadia

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

Użyj systemu granicznego

M = (\begin{matrix} Δ & e \\ e^{T} & 1 \end{matrix})

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

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

M (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} b \\ 0 \end{matrix})

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

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 . $A$ $\Delta - \ee \ee^T$ $P^{-1} \approx \Delta^{-1}$ $\Delta$

— Jed Brown
źródło

Myślę, że przy drugim podejściu znacznie lepiej. Chodzi o to, że nie wolno próbować przechowywać macierzy w pamięci ani próbować tworzyć z nią produktu wektora macierzy. Raczej za każdym razem, gdy trzeba pomnożyć przez z wektorem w schemacie iteracyjnym, mnożymy a następnie obliczamy . Termin w nawiasach to tylko suma pozycji a obliczasz go tylko raz. Jed już to dobrze wyjaśnił, ale chciałem podkreślić kolejność operacji.

K

$K$

A

$A$

z

$z$

h = Δ z

$h = \Delta z$

y = h - e (e^{T} z)

$y = h - \mathbf e (\mathbf e^T z)$

z

$z$

— Wolfgang Bangerth