matrix_multiply_quadratic

Algoritmo de tiempo cuadrático para la multiplicación matricial con enteros positivos

Este código fuente (en Python) es una implementación preliminar de mi multiplicación de matriz entera positiva de tiempo cuadrático que se probó teóricamente de su tiempo y complejidad espacial en una de mis preimpresiones [1]. Ha habido varias propuestas sobre las optimizaciones de algoritmos sub-cúbicos desde la improvisación de la versión recursiva por Strassen (en funcionamiento en O (n^log2 (7)) = O (n^2.807)) [2], como la de Bini et al. (Running in o (n^2.78)) [3], otro de Strassen (ejecutándose en o (n^2.479)) [4], por Coppersmith y Winograd (ejecutándose en o (n^2.375)) [5], por Williams (funcionando en o (n^2.3729)) [6] y más recientemente por Francois le-gall (en funcionamiento en o (n^2.3728). Pero todos ellos son teóricamente sólidos pero no son prácticamente implementables debido a las fuertes estructuras de datos, como las potencias tensoras. Los antecedentes teóricos se han demostrado y probado en su corrección en función de los métodos teóricos de números [1]. El archivo 'matrix_multiply_test.py' es básicamente un archivo de prueba unitario que prácticamente prueba la corrección de mi método. Pero el método ha sido diseñado y probado solo para enteros positivos, que pueden modificarse acertadamente para adaptarse a los casos con enteros negativos, números flotantes y números complejos también. La implementación real del algoritmo se ha mostrado en el archivo 'matrix_multiply_quadratic.py'. Junto con todo esto, he incluido una implementación basada en múltiples subprocesos que es un muy buen ejemplo de autómata celular. La versión probada de la implementación basada en CA se muestra en 'camatrix_mult_test.py'. El análisis de complejidad del tiempo se ha demostrado en 'camatrix_mult.py'.

Referencias

[1] S. Mohapatra, "Método teórico de número convolucional para optimizar la multiplicación de la matriz de enteros", [ARXIV: 1806.03701], 2018

[2] V. Strassen, "La eliminación gaussiana no es óptima", numer. Matemáticas. 13, p. 354-356, 1969

[3] D. Bini, M. Capovani, F. Romani y G. Lotti. "O (N^2.7799) Complejidad para N × N Multiplicación de matriz aproximada" Inf. Proceso. Lett., Pp. 234–235, 1979

[4] V. Strassen, "El espectro asintótico de los tensores y el exponente de la multiplicación matricial", Proc. 27th Ann. IEEE Symp. On Foundations of Computer Science, pp. 49-54, 1984

[5] D. Coppersmith, S. Winograd, "Multiplicación de matriz a través de progresiones aritméticas". J. Computación simbólica. pp. 251–280, 1980

[6] V. Williams, "Multrices multiplicadoras más rápido que Coppersmith-Winograd". ACM: pp.887–898, 2012

[7] F. Le Gall, "Potencias de tensores y multiplicación rápida de matriz", Proc. 39º int. Symp. Sobre el cálculo simbólico y algebraico, 2014