c++ - ¿Por qué la multiplicación de matrices de Strassen es mucho más lenta que la multiplicación de matrices estándar?

strassen java

Question

He escrito programas en C ++, Python y Java para la multiplicación de matrices y he probado su velocidad para multiplicar dos matrices de 2000 x 2000 (ver post ). El estándar ikj-implentation - que está en - tomó:

• C ++ : 15 segundos ( Source )
• Python : 6 minutos 13 segundos ( Source )

Ahora he implementado el algoritmo de Strassen para la multiplicación de matrices , que está en - en Python y C ++ como estaba en wikipedia. Estos son los tiempos que tengo:

• C ++ : 45 minutos ( Source )
• Python : Muerto después de 10 horas ( Source )

¿Por qué la multiplicación de matrices de Strassen es mucho más lenta que la multiplicación de matrices estándar?

Ideas:

• Algunos efectos de caché
• Implementación:
  • error (la matriz resultante 2000 x 2000 es correcta)
  • multiplicación nula (no debería ser tan importante para 2000 x 2000 -> 2048 x 2048)

Esto es especialmente sorprendente, ya que parece contradecir las experiencias de otros:

• ¿Por qué mi multiplicador Strassen Matrix es tan rápido?
• Multiplicación matricial: Strassen vs. Estándar : Strassen también fue más lento para él, pero fue al menos en el mismo orden de magnitud.

Edición: la razón por la que la multiplicación de la matriz de Strassen fue más lenta en mi caso fue:

• Lo hice completamente recursivo (ver tam)
• Tenía dos funciones strassen y strassenRecursive . El primero redimensionó la matriz a una potencia de dos, si es necesario y llamó al segundo. Pero strassenRecursive no se llamaba a sí mismo recursivamente, sino strassen .

Answer 1

Bueno, las "operaciones aritméticas" no son las únicas cosas que cuentan. No es que todo lo demás sea gratis.

Mi ingenua suposición sería que toda esta asignación y copia de memoria supera la ganancia de tener menos operaciones aritméticas ...

El acceso a la memoria, en particular, puede ser bastante costoso cuando sale de la memoria caché. En comparación, las operaciones matemáticas pueden considerarse libres :-)

Answer 2

El problema básico es que estás recurriendo a un tamaño de hoja de 1 con tu implementación strassen. El algoritmo de Strassen tiene una mejor complejidad de Big O, pero las constantes sí importan en la realidad, lo que significa que en realidad estás mejor con una multiplicación de matrices estándar n ^ 3 para problemas más pequeños.

Así que para mejorar mucho tu programa en lugar de hacerlo:

if (tam == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}

use if (tam == LEAF_SIZE) // iterative solution here . LEAF_SIZE debe ser una constante que debes determinar experimentalmente para tu arquitectura dada. Dependiendo de la arquitectura, puede ser más grande o más pequeño: hay arquitecturas donde los factores constantes para strassen son tan grandes que, básicamente, son siempre peores que una implementación n ^ 3 más simple para tamaños de matriz sensibles. Todo depende.

Answer 3

Si bien el algoritmo de Strassen tiene una notación Big O más pequeña, para aprovechar esto necesitaría multiplicar a las matrices que son demasiado grandes para resolverlas en la mayoría de las máquinas estándar e incluso en las súper computadoras.

Piénsalo de esta manera

un problema es x ^ 3, el otro es X ^ 1.6734 + 8x ^ (1/2) + x .....