Szybka i stabilna do tyłu (po lewej)

Muszę obliczyć wiele odwrotności macierzy (dla iteracyjnego rozkładu biegunowego Newtona), z bardzo małą liczbą przypadków zdegenerowanych ( ). $3\times3$ $<0.1\%$

Wyraźnie odwrotne (poprzez nieletnie macierze podzielone przez wyznacznik) wydaje się działać i ma około ~ 32 ~ 40 stopionych klap (w zależności od tego, jak obliczam odwrotność wyznacznika). Nie biorąc pod uwagę współczynnika det det, to tylko 18 stopionych klap (każdy z 9 elementów ma postać ab-cd, 2 stopione klapy).

Pytanie:

Czy istnieje sposób obliczenia odwrotności przy użyciu mniej niż 18 (z dowolną skalą) lub 32 (z odpowiednią skalą, biorąc pod uwagę odwrotną 1 operację) z połączonymi klapami? $3\times 3$
Czy istnieje ekonomiczny sposób (przy użyciu ~ 50 f-flops), aby obliczyć stabilną wstecz odwrotną lewą macierz ? $3\times 3$

Używam pływaków o pojedynczej precyzji (gra na iOS). Stabilność wsteczna jest dla mnie interesującą nową koncepcją i chcę eksperymentować. Oto artykuł, który sprowokował tę myśl.

— Sergiy Migdalskiy
źródło

Co powiesz na zastosowanie twierdzenia Cayleya-Hamiltona dla odwrotności?

— nicoguaro

Jeśli jest to dla ciebie takie wąskie gardło, czy inny algorytm rozkładu biegunowego mógłby być szybszy w tym przypadku? Na przykład przez SVD? Lub przyspieszenie metody Newtona jak w 3.3 eprints.ma.man.ac.uk/694/01/covered/MIMS_ep2007_9.pdf ?

— Kirill,

Postaram się zastanowić nad pierwszym pytaniem dotyczącym postu $3\times 3$ odwrotnie . Rozważać

ZA = [\begin{array}{ccc} za & re & sol \\ b & mi & h \\ do & fa & ja \end{array}]

$A=\left[ \begin{array}{ccc} a & d & g\\ b & e & h\\ c & f & i \end{array}\right]$

Ponieważ matryce są małe i bardzo ogólne (nie zawierają żadnej znanej struktury, zer, względnych skal elementów), myślę, że niemożliwe byłoby podanie algorytmu dla dowolnej skali (bez $1/\det(A)$ ) Odwrotny, że jest szybsze niż 18 skondensowanych klap, a każdy z elementów 9 wymaga 2 skondensowanych flop, a wszystkie produkty są unikalne pod warunkiem, które nie wymaga informacji na temat pozycji „a . Tutaj oznacza dopasowanie (transponowanie kofaktorów), które zasadniczo jest odwrotność z „dowolną skalą” (pod warunkiem, że istnieje odwrotność). $A$ $a,\ldots,i$

{ZA}^{- 1} det (ZA) = przym (ZA) = [\begin{array}{ccc} mi ja - fa h & re ja - fa sol & sol mi - re h \\ b ja - do h & za ja - do sol & za h - b sol \\ do mi - b fa & za fa - do re & za mi - b re \end{array}]

$A^{-1}\det(A)=\text{adj}(A)= \left[\begin{array}{ccc} ei-fh & di-fg & ge-dh\\ bi-ch & ai-cg & ah-bg\\ ce-bf & af-cd & ae-bd \end{array}\right]$

adj (A)

$\text{adj}(A)$

Jednak niektóre obliczenia mogą być ponownie wykorzystane do obliczenia . Jeśli rozwinę ją w pierwszej kolumnie (dostępnych jest jeszcze 5 innych opcji): Uwaga, że (* ) zostało już obliczone podczas oceny . Tak więc odwrotność wyznacznika można obliczyć w 4 dodatkowych połączonych klapach (jeśli wzajemność jest uważana za 1 flop). $\det(A)$

\begin{aligned} det (ZA) & = za (mi ja - fa h) + b (fa sol - re ja) + do (re h - sol mi) \\ = za \underset{*}{\underset{⏟}{(mi ja - fa h)}} - b \underset{*}{\underset{⏟}{(re ja - fa sol)}} - do \underset{*}{\underset{⏟}{(sol mi - re h)}} \end{aligned}

$\begin{aligned} \det(A)&=a(ei-fh)+b(fg-di)+c(dh-ge)\\ &=a\underbrace{(ei-fh)}_*-b\underbrace{(di-fg)}_*-c\underbrace{(ge-dh)}_* \end{aligned}$

adj (A)

$\text{adj}(A)$

1 / det (A)

$1/\det(A)$

Teraz każde 9 elementów powinno być skalowane przez już uzyskaną odwrotność wyznacznika, dodając kolejne 9 stopionych klap. $\text{adj}(A)$

Więc,

Oblicz w 18 połączonych klapach $\text{adj}(A)$
Oblicz w 3 połączonych klapach, używając wpisów już obliczonych $\det(A)$ $\text{adj}(A)$
Znajdź (przy założeniu 1 flopa). $\frac{1}{\det(A)}$
Skaluj każdy element już obliczonego według w kolejnych 9 połączonych klapach. $\text{adj}(A)$ $\frac{1}{\det(A)}$

Powoduje to 18 + 3 + 1 + 9 = 31 połączonych flopów . Nie opisałeś swojego sposobu obliczania wyznacznika, ale myślę, że można zapisać 1 dodatkowy flop. Lub można go użyć do wykonania sprawdzenia w kroku 3, gdzie jest tolerancją dla przypadku zdegenerowanego (nieodwracalnego), co daje 32 stopione klapy (przy założeniu, że 1 flop). $|\det(A)|>\epsilon$ $\epsilon$ if

Nie sądzę, że istnieje szybszy sposób obliczenia odwrotności macierzy ogólnej , ponieważ wszystkie pozostałe obliczenia są unikalne. Korzystanie z Cayleya-Hamiltona nie powinno pomóc w perspektywie prędkości, ponieważ ogólnie będzie wymagać obliczenia dla macierzy oprócz niektórych innych operacji. $3\times 3$ $A^2$ $3\times 3$

NB:

ta odpowiedź nie dotyczy stabilności numerycznej
możliwy potencjał wektoryzacji i optymalizacji wzorca dostępu do pamięci również nie jest omawiany

— Anton Menshov
źródło