El inverso, y el inverso de la matriz

Necesito calcular muchas inversas de matriz (para la descomposición polar de iteración de Newton), con un número muy pequeño de casos degenerados ( ). $3\times3$ $<0.1\%$

El inverso explícito (a través de matrices menores divididas por determinante) parece funcionar, y es de aproximadamente 32 ~ 40 flops fusionados (dependiendo de cómo calculo recíproco del determinante). Sin considerar el factor de escala det, son solo 18 flops fusionados (cada uno de los 9 elementos tiene la forma ab-cd, 2 flops fusionados).

Pregunta:

¿Hay alguna manera de calcular el inverso de usando menos de 18 (con escala arbitraria) o 32 (con la escala adecuada, considerando recíproco 1 op) flops fusionados? $3\times 3$
¿Hay alguna forma económica (usando ~ 50 f-flops) para calcular un inverso izquierdo estable hacia atrás de una matriz ? $3\times 3$

Estoy usando flotadores de precisión simple (juego para iOS). La estabilidad hacia atrás es un nuevo concepto interesante para mí y quiero experimentar. Aquí está el artículo que provocó el pensamiento.

matrix matrix-equations inverse matrix-factorization Sergiy Migdalskiy
fuente

¿Qué pasa con el uso del teorema de Cayley-Hamilton para el inverso?

nicoguaro

Si este es un cuello de botella para usted, ¿podría otro algoritmo de descomposición polar ser más rápido en este caso? ¿A través de SVD, por ejemplo? ¿O acelerar el método de Newton como en 3.3 de eprints.ma.man.ac.uk/694/01/covered/MIMS_ep2007_9.pdf ?

Kirill

Respuestas:

Intentaré reflexionar sobre la primera pregunta sobre el inverso rápido de $3\times 3$ . Considerar

UNA = [\begin{array}{ccc} una & re & sol \\ si & mi & h \\ C & F & yo \end{array}]

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

Dado que las matrices son pequeñas y muy generales (no presentan ninguna estructura conocida, ceros, escalas relativas de los elementos), creo que sería imposible dar un algoritmo de escala arbitraria (sin ) inverso que sea más rápido que el 18 fracasos fusionados, ya que cada uno de los 9 elementos requiere 2 fracasos fusionados, y todos los productos son únicos, siempre hay información previa sobre entradas 's . $1/\det(A)$ $A$ $a,\ldots,i$ Aquí,denota adyuvante (transposición de cofactores), que esencialmente es una inversa con "escala arbitraria" (siempre que exista la inversa).

{UNA}^{- 1} det (UNA) = adj (UNA) = [\begin{array}{ccc} mi yo - F h & re yo - F sol & sol mi - re h \\ si yo - C h & una yo - C sol & una h - si sol \\ C mi - si F & una F - C re & una mi - si 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)$

$\det(A)$

\begin{aligned} det (UNA) & = una (mi yo - F h) + si (F sol - re yo) + C (re h - sol mi) \\ = una \underset{*}{\underset{⏟}{(mi yo - F h)}} - si \underset{*}{\underset{⏟}{(re yo - F sol)}} - C \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)$

$\text{adj}(A)$

Entonces,

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

NÓTESE BIEN:

esta respuesta no trata la estabilidad numérica
tampoco se discute el posible potencial para la vectorización y la optimización del patrón de acceso a la memoria

Anton Menshov
fuente