¿Ha habido un análisis riguroso del algoritmo de Strassen?

Question

Según la Wikipedia, Algoritmo de Strassen se ejecuta en $O(N^{2.807})$ tiempo. ¿Ha visto alguien un análisis más riguroso que muestre las constantes, posiblemente en un lenguaje específico como C o Java?

Soy consciente de que esto variará de un lenguaje a otro, de una máquina a otra, etc., pero ¿alguien conoce un tamaño de entrada aproximado en el que el algoritmo de Strassen empieza a superar a la multiplicación de matrices normal?

Creo que esto puede pertenecer al intercambio de pilas de informática, pero como es algo matemático pensé en publicarlo aquí.

Answer 1

Le sugiero que eche un vistazo al artículo original de fácil lectura aquí (probablemente necesite una suscripción universitaria), y la revisión de MR es aquí . Dado que el algoritmo de Strassen es bastante famoso, me sorprendería que fuera difícil encontrar un análisis detallado en varios dialectos buscando un poco en Google.

De hecho, lo más aproximado es precisamente $\log_{2}{7} \approx 2.807$ .

Para multiplicar dos $n \times n$ matrices de la forma habitual se necesita $n^{3}$ multiplicaciones y $n^{2}(n-1)$ adiciones, por lo que en total se necesita $n^2 (2n-1)$ operaciones aritméticas. El algoritmo de Strassen (en su propio análisis) se salva con menos de $4.7 n^{\log_{2} 7}$ operaciones aritméticas (siempre que $n \geq 16$ si no me equivoco del todo), y esto debería ser mejor para todos esos $n$ .

No veo otra cosa "costosa" que la suma y la multiplicación en una implementación. La cantidad de memoria necesaria también debería ser bastante fácil de averiguar a partir de la descripción de Strassen, pero debería ser del orden de $4 n^2$ .

Answer 2

A partir de una búsqueda en Google [multiplicación de matrices de strassen cruzadas], he encontrado que los experimentos han encontrado que el punto de cruce está entre n = 8 y n = 20.

Sin embargo, en algún momento del análisis de los algoritmos se pasa de manipular conceptos matemáticos directamente a ejecutar las cosas de forma experimental y registrar valores y tiempos. En ese punto no se llama realmente análisis de algoritmos, sino simple ingeniería en la que se manipulan cosas distintas del algoritmo básico (optimización agresiva de la compilación, estrategias de caché, la velocidad de los componentes de la memoria, la paralización del hardware, el sistema de refrigeración, etc.). Entonces las variables a tener en cuenta son demasiadas y poco especificadas para hacer un cálculo analítico (sobre el papel), y sólo hay que comparar utilizando datos en tiempo de ejecución.