¿Qué algoritmo es eficaz para la multiplicación de matrices de 4×4 matrices de transformaciones afines?

Wikipedia enumera cuatro algoritmos para multiplicación matricial de dos matrices nxn .

El clásico que escribiría un programador es O (n ³ ) y aparece como «Multiplicación de matrices de libros escolares». Sí. O (n ³ ) es un éxito. Veamos el siguiente mejor.

El algoritmo de Strassen es O (n ^2.807 ). Este funcionaría: tiene algunas restricciones (como que el tamaño es una potencia de dos) y tiene una advertencia en la descripción:

En comparación con la multiplicación de matrices convencional, el algoritmo agrega una carga de trabajo considerable O (n ² ) en sumas / restas; por lo que por debajo de cierto tamaño, será mejor utilizar la multiplicación convencional.

Para aquellos que estén interesados en este algoritmo y sus orígenes, mirar ¿Cómo se le ocurrió a Strassen su método de multiplicación de matrices? puede ser una buena lectura. Da una pista sobre la complejidad de esa carga de trabajo inicial O (n ² ) que se agrega y por qué esto sería más costoso que simplemente hacer la multiplicación clásica.

Así que realmente es O (n ² + n ^2.807 ) con ese bit sobre el exponente menor n que se ignora al escribir una O grande. Parece que si están trabajando en una bonita matriz de 2048×2048, esto podría ser útil. Para una matriz 4×4, probablemente la encontrará más lenta, ya que la sobrecarga consume todo el resto del tiempo.

Y luego está el Coppersmith – Winograd algoritmo que es O (n ^2.373 ) con bastantes mejoras. También viene con una advertencia:

El algoritmo Coppersmith-Winograd se usa con frecuencia como un bloque de construcción en otros algoritmos para probar límites de tiempo teóricos. Sin embargo, a diferencia del algoritmo Strassen, no se usa en la práctica porque solo brinda una ventaja para matrices tan grandes que no pueden ser procesado por hardware moderno.

Por lo tanto, es mejor cuando se trabaja en matrices súper grandes, pero nuevamente, no es útil para una matriz 4×4.

Esto se refleja nuevamente en la página de wikipedia en Multiplicación de matrices: algoritmos subcúbicos que explica por qué las cosas funcionan más rápido:

Existen algoritmos que pr Proporciona mejores tiempos de ejecución que los sencillos. El primero en ser descubierto fue el algoritmo de Strassen, ideado por Volker Strassen en 1969 y a menudo denominado «multiplicación rápida de matrices». Se basa en una forma de multiplicar dos matrices 2 × 2 que requiere solo 7 multiplicaciones (en lugar de el habitual 8), a expensas de varias operaciones adicionales de suma y resta. Al aplicar esto de forma recursiva, se obtiene un algoritmo con un costo multiplicativo de O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). El algoritmo de Strassen es más complejo y la estabilidad numérica se reduce en comparación con el algoritmo ingenuo, pero es más rápido en los casos en que n> 100 más o menos y aparece en varias bibliotecas, como BLAS.

Y eso llega al núcleo de por qué los algoritmos son más rápidos: intercambia algo de estabilidad numérica y alguna configuración adicional. Esa configuración adicional para una matriz 4×4 es mucho más que el costo de hacer más multiplicaciones.

Y ahora, para responder a su pregunta:

¿Pero existen algunos algoritmos que son especialmente eficientes para matrices tan pequeñas?

No, no hay algoritmos que estén optimizados para la multiplicación de matrices 4×4 porque el O (n ³ ) uno funciona de manera bastante razonable hasta que empiece a darse cuenta de que está dispuesto a recibir un gran golpe por sobrecarga. Para su situación específica, puede haber algunos gastos generales en los que podría incurrir al saber cosas específicas de antemano sobre sus matrices (como la cantidad de datos que se reutilizarán), pero realmente lo más fácil es escribir un buen código para O (n ³ ), deje que el compilador lo maneje y perfílelo más adelante para ver si realmente tiene el código siendo el punto lento en la multiplicación de matrices.

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

A menudo, los algoritmos simples son los más rápidos para conjuntos muy pequeños, porque los algoritmos más complejos generalmente usan alguna transformación que agrega algo de sobrecarga. Creo que su mejor opción no es un algoritmo más eficiente (creo que la mayoría de las bibliotecas usan métodos sencillos), sino una implementación más eficiente, por ejemplo, una que use extensiones SIMD (asumiendo código x86 o amd64), o escrita a mano en ensamblador . Además, el diseño de la memoria debe estar bien pensado. Debería poder encontrar suficientes recursos sobre esto.

Para la multiplicación 4×4 mat / mat, las mejoras algorítmicas a menudo están descartadas . El algoritmo básico de complejidad de tiempo cúbico tiende a funcionar bastante bien, y cualquier cosa más elegante que eso tiene más probabilidades de degradar en lugar de mejorar los tiempos. Solo en general, los algoritmos sofisticados no son adecuados si no hay un factor de escalabilidad involucrado (por ejemplo, tratando de ordenar rápidamente una matriz que siempre tiene 6 elementos en lugar de una simple inserción o clasificación de burbujas). cosas como la transposición de matrices aquí para mejorar la localidad de referencia tampoco ayudan realmente a la localidad de referencia cuando una matriz completa puede caber en una o dos líneas de caché. En este tipo de escala en miniatura, si está haciendo una multiplicación de tapete / tapete 4×4 en masa, las mejoras generalmente provendrán de optimizaciones de micro-nivel de instrucciones y memoria, como una alineación adecuada de la línea de caché.

Comentarios

• ¡Excelente respuesta! ‘ nunca he oído hablar del acrónimo de SoA (al menos, en holandés es un acrónimo de ‘ seksueel overdraagbare aandoening ‘ que significa ‘ enfermedad de transmisión sexual ‘ … pero eso ‘ s con suerte no es lo que quiere decir aquí). La técnica parece clara, ‘ incluso me sorprende bastante que haya un nombre para ella. ¿Qué significa SoA?
• @Ruben Structure of Arrays en contraposición a Arrays of Structures. Los SoA también pueden ser PITA: se guardan mejor para las rutas más críticas. Aquí ‘ un pequeño enlace que encontré sobre el tema: stackoverflow.com/questions/17924705/…
• Es posible que desee mencionar C ++ 11 / C11 alignas .

Si está seguro de que solo necesitará multiplicar 4×4 matrices, entonces no necesita preocuparse por un algoritmo general en absoluto. Puede tomar dos punteros y usar esto:

(Recomiendo encarecidamente traducir esto de manera automatizada).

El compilador sería entonces en una posición óptima para optimizar este código (para reutilizar sumas parciales, reordenar las matemáticas, etc.) ya que puede ver todo, no hay bucles dinámicos ni flujo de control.

Es difícil imaginar que esto se pueda superar sin usando intrínsecos.

No puede comparar directamente la complejidad asintótica si define n de manera diferente. Está acostumbrado a comparar la complejidad de los algoritmos en estructuras de datos planas como listas, donde n se define como el número total de elementos en la lista, pero los algoritmos matriciales definen n como solo la longitud de un lado .

Según esta definición de n, algo tan simple como mirar cada elemento una vez para imprimirlo, lo que normalmente pensaría como O (n), es O (n ² ) . Si define n como el número total de elementos en la matriz, es decir, n = 16 para una matriz de 4×4, entonces la multiplicación de matriz ingenua es solo O (n ^1.5 ), que es bastante bueno.

Su mejor opción es aprovechar el paralelismo mediante el uso de instrucciones SIMD o una GPU, en lugar de intentar mejorar el algoritmo basado en la creencia errónea de que O (n ³ ) es tan malo como sería si n se definiera de manera comparable a una estructura de datos plana.