A matriz inversa rápida e estável (esquerda)

Preciso para calcular uma série de $3\times3$ matriz inversa (por Newton iteração decomposição polar), com muito pequeno número de casos degenerados ( $<0.1\%$ ).

Inverso explícito (via menores de matriz divididos por determinante) parece funcionar e tem cerca de ~ 32 ~ 40 fracassos fundidos (dependendo de como eu calculo o inverso do determinante). Sem considerar o fator de escala de detecção, são apenas 18 flops fundidos (cada um dos 9 elementos tem a forma ab-cd, 2 flops fundidos).

Questão:

Existe uma maneira de calcular inversos de $3\times 3$ usando menos de 18 (com escala arbitrária) ou 32 (com escala adequada, considerando 1 op op) falhanços fundidos?
Existe uma forma económica (utilizando 50 ~ f-flops) para calcular uma retro-estável deixado inversa de um $3\times 3$ matriz?

Estou usando carros alegóricos de precisão única (jogo para iOS). A estabilidade para trás é um novo conceito interessante para mim e quero experimentar. Aqui está o artigo que provocou o pensamento.

matrix matrix-equations inverse matrix-factorization Sergiy Migdalskiy
fonte

Que tal usar o teorema de Cayley-Hamilton para o inverso?

nicoguaro

Se esse é um gargalo para você, outro algoritmo para decomposição polar pode ser mais rápido nesse caso? Através do SVD, por exemplo? Ou acelerando o método de Newton como em 3.3 de eprints.ma.man.ac.uk/694/01/covered/MIMS_ep2007_9.pdf ?

Kirill

Respostas:

Tentarei refletir sobre a primeira pergunta sobre o inverso rápido $3\times 3$ . Considerar

UMA = [\begin{array}{ccc} uma & d & g \\ b & e & h \\ c & f & Eu \end{array}]

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

Como as matrizes são pequenas e muito gerais (não apresentam nenhuma estrutura conhecida, zeros, escalas relativas dos elementos), acho que seria impossível fornecer um algoritmo para escala arbitrária (sem ) inversa que seja mais rápido do que 18 fracassos fundidos, como cada um de 9 elementos requer 2 fracassos fundidos, e todos os produtos são únicos, desde nenhuma informação prévia sobre entradas de . $1/\det(A)$ $A$ $a,\ldots,i$ Aqui,indica o adjugado (transposição de cofatores), que é essencialmente um inverso com "escala arbitrária" (desde que exista o inverso).

A^{- 1} det (A) = adj (A) = [\begin{array}{ccc} e i - f h & d i - f g & g e - d h \\ b i - c h & a i - c g & a h - b g \\ c e - b f & a f - c d & a e - b d \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)$

$\det(A)$

\begin{aligned} det (A) & = a (e i - f h) + b (f g - d i) + c (d h - g e) \\ = a \underset{*}{\underset{⏟}{(e i - f h)}} - b \underset{*}{\underset{⏟}{(d i - f g)}} - c \underset{*}{\underset{⏟}{(g e - d 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)$

$\text{adj}(A)$

Assim,

$\text{adj}(A)$
$\det(A)$ $\text{adj}(A)$
$\frac{1}{\det(A)}$
$\text{adj}(A)$ $\frac{1}{\det(A)}$

$|\det(A)|>\epsilon$ $\epsilon$ if

$3\times 3$ $A^2$ $3\times 3$

NB:

esta resposta não lida com a estabilidade numérica
o possível potencial de vetorização e otimização do padrão de acesso à memória também não é discutido

Anton Menshov
fonte