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.

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

$$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$

$$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]$$ $\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(A)&=a(ei-fh)+b(fg-di)+c(dh-ge)\\ &=a\underbrace{(ei-fh)}_*-b\underbrace{(di-fg)}_*-c\underbrace{(ge-dh)}_* \end{aligned}$$ $\text{adj}(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,

1. Oblicz w 18 połączonych klapach$\text{adj}(A)$
2. Oblicz w 3 połączonych klapach, używając wpisów już obliczonych$\det(A)$$\text{adj}(A)$
3. Znajdź (przy założeniu 1 flopa).$\frac{1}{\det(A)}$
4. 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