Rzadki liniowy solver dla wielu prawych stron

12

Muszę rozwiązać ten sam rzadki układ liniowy (300 x 300 do 1000 x 1000) z wieloma prawymi bokami (300 do 1000). Oprócz tego pierwszego problemu chciałbym również rozwiązać różne systemy, ale z tymi samymi niezerowymi elementami (tylko różne wartości), to znaczy wiele rzadkich systemów o stałym wzorcu rzadkości. Moje macierze są nieokreślone.

Wydajność faktoryzacji i inicjalizacji nie jest ważna, ale wydajność etapu rozwiązywania jest. Obecnie zastanawiam się nad PaStiX lub Umfpack i prawdopodobnie będę bawić się ze Petsc (który obsługuje oba solver). Czy istnieją biblioteki zdolne do korzystania z moich konkretnych potrzeb (wektoryzacja, wielowątkowość) lub czy powinienem polegać na ogólnych rozwiązaniach, i może zmodyfikować je nieco dla moich potrzeb?

Co jeśli rzadka matryca jest większa, do ? $10^6 \times 10^6$

— nat chouf
źródło

10

Nie podejmując dyskusji na temat tego, czy stosować solwery bezpośrednie, czy iteracyjne, chcę tylko dodać dwie kwestie:

Istnieją metody Kryłowa dla systemów z wieloma prawymi bokami (zwane metodami blokowymi Kryłowa ). Jako dodatkowy bonus, często mają one większą zbieżność niż standardowe metody Kryłowa, ponieważ przestrzeń Kryłowa jest zbudowana z większej kolekcji wektorów. Zobacz Dianne P. O'Leary, Algorytm gradientu sprzężonego bloku i metody pokrewne . Algebra liniowa i jej zastosowania 29 (1980), strony 239–322. i Martin H. Gutknecht, Metody przestrzenne Block Krylowa dla układów liniowych z wieloma prawymi bokami: Wprowadzenie (2007).
Jeśli masz różne macierze o tym samym wzorze rzadkości, możesz wstępnie obliczyć faktoryzację symboliczną dla pierwszej macierzy, którą można ponownie wykorzystać przy obliczaniu faktoryzacji numerycznej dla tej i kolejnych macierzy. (W UMFPACK możesz to zrobić, używając umfpack di symbolici przekazując wynik umfpack_di_numeric.)

— Christian Clason
źródło

9

$O(N)$

— Wolfgang Bangerth
źródło

4

O (N^{2})

$O(N^2)$

O (N^{4 / 3})

$O(N^{4/3})$

O (N^{4 / 3})

$O(N^{4/3})$

N

$N$

3

O (N)

$O(N)$

O (N^{4 / 3})

$O(N^{4/3})$

2

10^{5}

$10^5$

n < 300 k

$n<300k$

3

W swoim stwierdzeniu problemu nie jest całkiem jasne, kiedy mówimy o „tych samych niezerowych elementach (tylko różnych wartościach)”. Czy mówisz, że macierz ma stały wzorzec rzadkości, ale rzeczywiste wartości się zmieniają? A może mówisz, że matryca jest w rzeczywistości stała?

$PA=LU$ $O(n^2)$

W przypadku wielu prawych stron i układów równań tej wielkości metody iteracyjne zwykle nie są tego warte.

Wszystkie wspomniane pakiety oferują metody bezpośredniej faktoryzacji (chociaż PetSc jest znany głównie z iteracyjnych solverów). Jednak twoje systemy są tak małe, że jest mało prawdopodobne, aby można było uzyskać znaczne równoległe przyspieszenia, szczególnie w środowisku pamięci rozproszonej.

Sugeruję użycie Umfpack do tego zadania - PaStix i PetSc są przesadzone.

— Brian Borchers
źródło

Dzięki za odpowiedź. Aby to wyjaśnić: najpierw poprosiłem o pojedynczą matrycę z wieloma prawymi bokami, a następnie kolejnym problemem jest zbiór matryc o tej samej strukturze rzadkości, ale wartości się zmieniają, każda z nich musi zostać rozwiązana dla wielu rh. Dodatkowe pytanie: co jeśli rzadka macierz ma teraz 10 ^ 5x10 ^ 5 do 10 ^ 6x10 ^ 6?

— nat chouf

2

10^{5}

$10^5$

Zastosowanie metody iteracyjnej dla większych systemów z tylko jedną prawą stroną może mieć sens, szczególnie jeśli nie potrzebujesz bardzo dokładnych rozwiązań, a zwłaszcza jeśli możesz znaleźć skuteczny warunek wstępny lub twoje systemy są już dobrze uwarunkowane. Jeśli jednak twoje systemy są źle uwarunkowane, potrzebujesz dokładnych rozwiązań i nie możesz znaleźć dobrego warunku wstępnego, prawdopodobnie nadal będziesz lepiej z bezpośrednim rozkładem na czynniki.

— Brian Borchers,

N

$N$

10^{6}

$10^6$