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 ?106×106

nat chouf
źródło

Odpowiedzi:

10

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

  1. 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).

  2. 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(N2)O(N4/3)O(N4/3)N
3
O(N)O(N4/3)
2
105n<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=LUO(n2)

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
105
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,
N106