Jaki jest najszybszy algorytm obliczania macierzy odwrotnej i jej wyznacznika dla dodatnio określonych macierzy symetrycznych?

Biorąc pod uwagę dodatnią określoną macierz symetryczną, jaki jest najszybszy algorytm obliczania macierzy odwrotnej i jej wyznacznika? W przypadku problemów, którymi jestem zainteresowany, wymiar macierzy wynosi 30 lub mniej.

Wysoka dokładność i szybkość jest naprawdę konieczna. (wykonywane są miliony macierzy)
Wyznacznik jest konieczny. W każdym obliczeniu wymagany jest tylko jeden element macierzy odwrotnej. Dzięki!

algorithms matrix Zamówienia
źródło

Czy musisz odwracać miliony takich matryc? W przeciwnym razie prędkość nie powinna stanowić problemu.

Wolfgang Bangerth

Zredagowałem twój tytuł i pytanie dla jasności. Jeśli popełniłem jakieś błędy, daj mi znać.

Geoff Oxberry

@Wolfgang Bangerth Tak, należy wziąć pod uwagę prędkość.

Zamówienia

Czy wiesz, który element macierzy odwrotnej jest potrzebny? Czy może to być losowy wpis?

Memming

@ Zamówienia Twój komentarz i edycja wydają się sprzeczne: czy potrzebujesz jednego elementu odwrotności, czy wszystkich ?

Federico Poloni

W przypadku problemów, którymi jestem zainteresowany, wymiar macierzy wynosi 30 lub mniej.

Jak zauważa WolfgangBangerth, chyba że masz dużą liczbę tych macierzy (miliony, miliardy), wydajność odwrócenia macierzy zwykle nie stanowi problemu.

Biorąc pod uwagę dodatnią określoną macierz symetryczną, jaki jest najszybszy algorytm obliczania macierzy odwrotnej i jej wyznacznika?

Jeśli problemem jest prędkość, powinieneś odpowiedzieć na następujące pytania:

Czy naprawdę potrzebujesz całej odwrotności? (Wiele aplikacji nie musi tworzyć jawnej odwrotności).
Czy naprawdę potrzebujesz wyznacznika? (Determinanty są rzadkie, ale z pewnością nie są niespotykane w nauce obliczeniowej).
Czy potrzebujesz wysokiej dokładności? (Algorytmy niskiej dokładności wydają się być szybsze).
Czy wystarczyłoby przybliżenie probabilistyczne? (Algorytmy probabilistyczne są zwykle szybsze).

Standardową odpowiedzią na Twój problem odwrócenia małej, dodatniej określonej macierzy i obliczenia jej wyznacznika byłby rozkład Choleskiego. Gdyby $A = LL^{T}$ , następnie $\det(A) = \prod_{i=1}^{n}l_{ii}^{2}$ i . $\det(A^{-1}) = \prod_{i=1}^{n}l_{ii}^{-2}$

Zakładając, że oznacza przez , rozkład Cholesky'ego można obliczyć na około flopach, co stanowi około połowę kosztu rozkładu LU. Taki algorytm nie byłby jednak uważany za „szybki”. Losowo metoda lu $A$ $n$ $n$ $n^{3}/3$ może być szybszym algorytmem wartym rozważenia, jeśli (1) naprawdę musisz wziąć pod uwagę dużą liczbę macierzy, (2) faktoryzacja jest tak naprawdę ograniczającym krokiem w twojej aplikacji, i (3) każdy błąd związany z użyciem algorytmu losowego to do przyjęcia. Twoje macierze są prawdopodobnie zbyt małe, aby były rzadkie algorytmy, aby były opłacalne, więc jedyne inne możliwości szybszych algorytmów wymagałyby dodatkowej struktury macierzy (np. Pasmowej) lub wykorzystania struktury problemów (np. Być może możesz sprytnie zrestrukturyzować algorytm, aby nie dłużej trzeba obliczać macierz odwrotną lub jej wyznacznik). Wydajne algorytmy wyznaczania są w przybliżeniu kosztem rozwiązania układu liniowego w ramach stałego współczynnika, więc te same argumenty stosowane w układach liniowych odnoszą się również do obliczania wyznaczników.

Geoff Oxberry
źródło

Tylko uwaga skrócie: jeśli , aby obliczyć pojedynczy element należy obliczyć tylko th kolumnie . Po obliczeniu faktoryzacji Cholesky'ego dokonuje się tego przez podstawienie do przodu i do tyłu w odniesieniu do wektora rh wszystkich zer i tylko jednego w rzędzie . Ponieważ obliczenia mogą zostać przerwane, gdy tylko zostanie obliczone, najlepszym przypadkiem jest najgorszy przypadek dla którym trzeba wykonać pełne obliczenie z powrotem i forwardowania.

B = A^{- 1}

$B = A^{-1}$

b_{i j}

$b_{ij}$

j

$j$

B

$B$

j

$j$

b_{i j}

$b_{ij}$

b_{n n} = l_{n n}^{- 2}

$b_{nn} = l_{nn} ^{-2}$

b_{11}

$b_{11}$

Stefano M

@StefanoM Nawet lepiej, możesz permutować swoją matrycę przed rozpoczęciem obliczeń, dzięki czemu zawsze będziesz w najlepszym przypadku.

Federico Poloni,

Jaki jest najszybszy algorytm obliczania macierzy odwrotnej i jej wyznacznika dla dodatnio określonych macierzy symetrycznych?

Odpowiedzi: