La hipótesis de Strassen

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de marzo de 2020; la verificación requiere 1 edición .

En la teoría de la complejidad computacional y el álgebra lineal , la hipótesis de Strassen establece que para las matrices cuadradas se pueden especificar dimensiones suficientemente grandes , para lo cual existe un algoritmo que permite multiplicarlas a una velocidad arbitrariamente cercana a . A pesar de los esfuerzos de muchos matemáticos, la conjetura planteada en 1969 aún no ha sido demostrada y es uno de los problemas sin resolver del álgebra lineal . $norte$ $O(n^{2})$

Hipótesis

Para n arbitrariamente pequeños , existe un algoritmo que, para números naturales n suficientemente grandes, garantiza la multiplicación de dos matrices de tamaño en operaciones. $\varepsilon >0$ $n\veces n$ ${O}(n^{{2+\varepsilon}})$

Discusión

La tarea de multiplicar dos matrices cuadradas grandes es laboriosa y se encuentra a menudo en las aplicaciones. Así, la aceleración de esta operación es de gran importancia práctica. Dado que al multiplicar matrices es necesario calcular valores nuevos, generalmente diferentes, de los elementos de la matriz, esto no se puede hacer en menos de operaciones. El algoritmo estándar según la definición de multiplicación de matrices requiere operaciones. En 1969, el matemático alemán Volker Strassen propuso el primer algoritmo más rápido [1] que requería multiplicaciones. También planteó la hipótesis de que es posible multiplicar matrices aún más rápido. En 1990, se demostró que hay suficientes operaciones ( algoritmo Coppersmith-Winograd ) [2] . Este algoritmo es de importancia teórica y no se puede usar en la práctica, ya que en realidad acelera la multiplicación solo para matrices astronómicamente grandes. Posteriormente, se realizaron varias mejoras menores a la última estimación basada en el mismo método [3] . Esto nos permite hablar de la existencia de la "barrera de Coppersmith-Winograd" en estimaciones teóricas de la complejidad de este problema, aunque la mayoría de los investigadores creen que la hipótesis de Strassen es correcta. El exponente en los algoritmos prácticos se ha mejorado ligeramente en comparación con el exponente del algoritmo de Strassen, pero hasta ahora sigue siendo significativamente mayor que el exponente del algoritmo de Coppersmith-Winograd. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\aprox {O}(n^{{2.81)))$ ${O}(n^{{2376}})$

Véase también

Notas

↑ Strassen, Volker, La eliminación gaussiana no es óptima , Numer. Matemáticas. 13, pág. 354-356, 1969
↑ Don Coppersmith y Shmuel Winograd. Multiplicación de matrices mediante progresiones aritméticas. Revista de Computación Simbólica , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier . Archivado el 20 de enero de 2013 en Wayback Machine .

Enlaces

Strassen V. La eliminación gaussiana no es óptima // Numer . Matemáticas / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, edición. 4.- Pág. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411