Dado $A,B\in SO(3)$, calcula la multiplicación de la matriz directa multiplica $C=AB$ con 27. Es del grupo $SO(3)$ $3$-múltiple dimensional. Esto sugiere que la multiplicación de la matriz directa, que piensa de los elementos de $SO(3)$ como 9 dimensiones, no es óptimo. ¿Cuál es el mínimo número de multiplica necesario calcular $C$?
Respuestas
¿Demasiados anuncios?
La parte superior de mi cabeza, si representan elementos de $SO(3)$ a través de la elevación a los elementos de $SU(2)$, un producto puede ser calculada con 8 multiplica. Pero son multiplica de los números complejos, que son 4 multiplica cada uno de 32 en total.
Pero, podemos utilizar el algoritmo de Strassen para calcular la matriz producto en 7 multiplica, y Karatsuba para calcular un producto complejo, en 3 se multiplica por 21 en total.
Por supuesto, los elementos de $SU(2)$ no son matrices generales, tienen una forma especial. Si escribir fuera de las cuatro entradas, es claro que usted puede calcular los términos con 4 complejos multiplica junto con algunas adiciones y conjugaciones, así que 12 real se multiplica en todos si hacemos uso de Karatsuba o 16 lo contrario.
El uso de Euler-Rodrigues forma, podemos representar la rotación como 4 números reales. El declaró la composición de la fórmula requiere 16 productos. Pero podemos salir con sólo 10 productos. Primer lugar, calcular $a_1 a_2$, $b_1 b_2$, $c_1 c_2$, y $d_1 d_2$, a continuación, utilizar la idea de Karatsuba para conseguir el resto de los términos en los pares. Por ejemplo, usted puede conseguir $a_1b_2 + a_2b_1$ por el único producto $(a_1 + b_1)(a_2 + b_2)$ y sustrae los términos no deseados.
Hay más representaciones aparece en la wikipedia, pero no he mirado en la cantidad de un producto, el costo sería en esas representaciones.
Tenga en cuenta que menos de los productos no siempre es lo mejor: la suma y otras cosas toman tiempo, y los diferentes algoritmos se comportan de manera diferente con respecto a la estabilidad numérica.
Marcel Janus
Puntos
419
Yo estaba interesado en la misma pregunta, y encontré este hilo. Claramente, cuaterniones o SU(2) la multiplicación se lleva a no más de 12 real multiplicaciones, desde el complejo de la multiplicación no toma más de 3 reales multiplicaciones
http://mathworld.wolfram.com/ComplexMultiplication.html
La pregunta es si hay trucos similares que se pueden hacer para reducir el número de multiplicaciones de matrices de rotación, sin necesidad de convertir a otra representación. En el 2x2 matriz de rotación caso, de nuevo, no lleva más de 3 multiplica, por el mismo razonamiento que en el complejo de la multiplicación. Es posible, en el 3x3 caso, para utilizar el producto cruzado para obtener la última columna de C a partir de los dos primeros. Esto ahorra 3 multiplicaciones, y utiliza el hecho de que C es ortogonal. No use la ortogonalidad de a o B, aunque. Puede algo mejor que hacer?
