Algoritmo de multiplicación de matrices
Debido a que la multiplicación de matrices es una operación tan central en muchos algoritmos numéricos , se ha invertido mucho trabajo en hacer que los algoritmos de multiplicación de matrices sean eficientes. Las aplicaciones de la multiplicación de matrices en problemas computacionales se encuentran en muchos campos, incluida la computación científica y el reconocimiento de patrones, y en problemas aparentemente no relacionados, como contar las rutas a través de un gráfico . [1] Se han diseñado muchos algoritmos diferentes para multiplicar matrices en diferentes tipos de hardware, incluido el paralelo y el distribuidosistemas, donde el trabajo computacional se distribuye en múltiples procesadores (quizás en una red).
La aplicación directa de la definición matemática de multiplicación de matrices proporciona un algoritmo que toma tiempo del orden de n 3 operaciones de campo para multiplicar dos n × n matrices sobre ese campo ( Θ ( n 3 ) en notación O grande ). Se conocen mejores límites asintóticos en el tiempo requerido para multiplicar matrices desde el algoritmo de Strassen en la década de 1960, pero aún se desconoce cuál es el tiempo óptimo (es decir, cuál es la complejidad computacional de la multiplicación de matrices ). A diciembre de 2020 [actualizar], el algoritmo de multiplicación de matrices con la mejor complejidad asintótica se ejecuta enO ( n 2.3728596 ) tiempo, dado por Josh Alman y Virginia Vassilevska Williams , [2] [3] sin embargo, este algoritmo es un algoritmo galáctico debido a las grandes constantes y no se puede realizar en la práctica.
La definición de multiplicación de matrices es que si C = AB para una matriz A de n × m y una matriz B de m × p , entonces C es una matriz de n × p con entradas
De esto, un algoritmo simple se puede construir que los bucles a través de los índices i de 1 a n y j de 1 a p , el cálculo de la anterior usando un bucle anidado:
Este algoritmo toma tiempo Θ ( nmp ) (en notación asintótica ). [1] Una simplificación común para el propósito del análisis de algoritmos es asumir que las entradas son todas matrices cuadradas de tamaño n × n , en cuyo caso el tiempo de ejecución es Θ ( n 3 ) , es decir, cúbicos en el tamaño de la dimensión. . [4]
Los tres bucles en la multiplicación iterativa de matrices se pueden intercambiar arbitrariamente entre sí sin que ello afecte a la corrección o al tiempo de ejecución asintótico. Sin embargo, el orden puede tener un impacto considerable en el rendimiento práctico debido a los patrones de acceso a la memoria y al uso de caché del algoritmo; [1] cuál es el mejor orden también depende de si las matrices se almacenan en orden de fila principal , orden de columna principal o una combinación de ambos.
