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


11

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

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

Ax=b

z

Δ - 6 6 1A=(Δ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.Δ661

R n × nK jest pełną macierzą , która składa się całkowicie z nich.Rn×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=ΔA=(ΔK)nK

EDYCJA: Zrobiłbym coś takiego

x k + 1Δxk+1=b+Kxk // rozwiąż dla pomocą Gaussa-Seidelaxk+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 = 256ρ(Δ1K)<1ρΔ1Knn=256

EDYCJA: Więcej informacji oΔ :

ΔRn×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);


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

Δ jest symetryczna i ujemna.
dniu

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

Odpowiedzi:


14

n>106n1012ΔΔ

  • Użyj systemu granicznego

M=(ΔeeT1)

gdzie to wektor kolumnowy składający się ze wszystkich i rozwiązujący systeme

M(xy)=(b0)

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ΔeeTP1Δ1Δ

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. A z h = Δ z y = h - e ( e T z ) zKAzh=Δzy=he(eTz)z
Wolfgang Bangerth
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.