Nivel de recursividad óptimo para el algoritmo de Strassen

Ponente(s): Laura Monica Fernandez Najera, Amilcar Meneses Viveros

La multiplicación de matrices es una operación básica dentro de las matemáticas y su uso se extiende a diversas disciplinas. El algoritmo secuencial tiene complejidad O(n^3). El algoritmo de Strassen reduce la complejidad de la multiplicación a O(n^log2(7)), además se puede utilizar de forma recursiva. En este trabajo se analiza el nivel de recursividad óptimo para disminuir el tiempo de ejecución de la multiplicación de matrices, se encuentra una relación entre el nivel de recursividad óptimo y el tamaño de la matriz menos una constante que depende de cada dispositivo donde se ejecuta. Se analizan tres casos para tres procesadores diferentes. Se concluye que existe un nivel de recursividad, i, para el cual el tiempo de ejecución es mínimo y es i=log2(n)-alpha, donde 0