Número mínimo de multiplicaciones necesarias para invertir una matriz 4x4

Question

Las matrices de cuatro por cuatro reales (bueno, de punto flotante...) se utilizan en infografía para representar proyecciones . A veces hay que calcular sus inversos. ¿Cuántas multiplicaciones son necesarias?

• SDK de origen de Valve implementa el algoritmo "pen&paper": comienza con una matriz de 4x8 cuyo lado izquierdo es $A$ (la matriz a invertir) y cuyo lado derecho es $I_4$ (la matriz de identidad 4x4); aplicar los movimientos de Gauss hasta que el lado izquierdo sea $I_4$ y la mano derecha será $A^{-1}$ . Este algoritmo requiere (inspeccionando el código) $4 \cdot 8 + 4 \cdot 4 \cdot 8 = 160$ multiplicaciones.
• Resolver $AX = I$ aplicando La regla de Cramer para cada elemento y calculando cada determinante 3x3 con La regla de Sarrus mejora: necesitamos $6 \cdot 16$ multiplicación de los cofactores, entonces $4$ más para el determinante de la matriz 4x4, más $16$ multiplicaciones para la inversa de eso, para un total de $6 \cdot 16 + 4 + 16 = 116$ multiplicaciones.
• Precálculo inteligente de productos de dos elementos como en esta respuesta requiere (de nuevo inspeccionando el código) $2\cdot 12 + 6 + 4 \cdot 16 = 94$ multiplicaciones.

¿Podemos hacerlo mejor? ¿Podemos demostrar que no podemos?

Answer 1

Podemos invertir una matriz de 2x2 con 6 multiplicaciones y una inversión. Por el algoritmo de Strassen, podemos multiplicar matrices de 2x2 con 7 multiplicaciones.

Participe en su matriz de 4x4 como

$$\left( \begin{matrix} A & B \\ C & D \end{matrix} \right) $$

Lo reduciremos a la identidad.

Calcular la inversa de $A$ .

Realizar la eliminación gaussiana

$$\left( \begin{matrix} I & A^{-1} B \\ 0 & D - CA^{-1}B \end{matrix} \right) $$

Dejemos que $E = D - C A^{-1} B$ . Ahora calcule $E^{-1}$ . Ahora podemos terminar la eliminación gaussiana.

Repitiendo estas operaciones sobre una matriz identidad nos dice que la inversa es

$$ \left( \begin{matrix} A^{-1} + A^{-1} B E^{-1} C A^{-1} & -A^{-1} B E^{-1} \\ -E^{-1} C A^{-1} & E^{-1} \end{matrix} \right) $$

El cálculo de esta inversa requiere dos inversiones de matriz (12 multiplicaciones y 2 inversiones reales), y seis multiplicaciones 2x2:

• $C A^{-1}$
• $(C A^{-1}) B$
• $E^{-1} (C A^{-1})$
• $A^{-1} B$
• $(A^{-1} B) E^{-1}$
• $(A^{-1} B)(E^{-1} C A^{-1})$

para 54 multiplicaciones y 2 inversiones reales en total.

Por supuesto, utilizar el algoritmo de Strassen para matrices de 2x2 es una idea terrible. No sé si la organización anterior del cálculo es razonable o no incluso si no se utiliza el algoritmo de Strasses; sospecho que es poco probable.

Si $A$ resulta ser singular, hay que particionar la matriz de otra manera para hacer el cálculo.

Answer 2

En su documento La eliminación gaussiana no es óptima , Volker Strassen declaró lo siguiente:

Un tratamiento más reciente de la inversión de matrices lo proporciona Intel . Sin embargo, su objetivo es la velocidad y no el número mínimo de multiplicaciones.