matrix_multiply_quadratic

Algoritmo de tempo quadrático para multiplicação de matrizes com números inteiros positivos

Esse código-fonte (em Python) é uma implementação preliminar da minha multiplicação de matriz inteira positiva em tempo quadrático que foi teoricamente comprovada de sua complexidade de tempo e espaço em uma das minhas preistas [1]. Houve várias propostas nas otimizações de algoritmo subcúbico desde a improvisação da versão recursiva por Strassen (em execução em O (n^log2 (7)) = O (n^2.807)) [2], como o de Bini et al. (em execução em O (n^2,78)) [3], outro de StraSsen (em execução em O (n^2,479)) [4], por Coppersmith e Winograd (em execução em O (n^2,375)) [5], por Williams (Running em (N^2,3729) [6] e mais Francyis. [7]. Mas todos eles são teoricamente sólidos, mas não praticamente implementáveis ​​devido às estruturas de dados pesadas, como poderes de tensor. O fundo teórico foi demonstrado e comprovado sobre sua correção com base nos métodos teóricos do número [1]. O arquivo 'matrix_multiply_test.py' é basicamente um arquivo de teste de unidade que praticamente prova a correção do meu método. Mas o método foi projetado e testado apenas para números inteiros positivos, que podem ser apropriadamente modificados para se adequar aos casos com números inteiros negativos, números flutuantes e números complexos também. A implementação real do algoritmo foi mostrada no arquivo 'matrix_multiply_quadratic.py'. Junto com tudo isso, incluí uma implementação baseada em multi-threading que é um bom exemplo de autômato celular. A versão testada da implementação baseada em CA é mostrada em 'Camatrix_mult_test.py'. A análise de complexidade do tempo foi mostrada em 'Camatrix_mult.py'.

Referências

[1] S. Mohapatra, "Método Teórico de Números Convolucionais para otimizar a multiplicação da matriz inteira", [Arxiv: 1806.03701], 2018

[2] V. Straassen, "A eliminação gaussiana não é ideal", numer. Matemática. 13, p. 354-356, 1969

[3] D. Bini, M. Capovani, F. Romani e G. Lotti. "O (n^2,7799) Complexidade para n × n Multiplicação de matriz aproximada" Inf. Processo. Lett., Pp. 234–235, 1979

[4] V. Straassen, "O espectro assintótico dos tensores e o expoente da multiplicação da matriz", Proc. 27ª Ann. IEEE Symp. Sobre Fundamentos da Ciência da Computação, pp. 49-54, 1984

[5] D. Coppersmith, S. Winograd, "Multiplicação da matriz por meio de progressões aritméticas". J. Comput Symbolic. pp. 251–280, 1980

[6] V. Williams, "Multiplicando matrizes mais rapidamente que Coppersmith-Winograd". ACM: pp.887-898, 2012

[7] F. Le Gall, "Poderes de tensores e multiplicação de matriz rápida", Proc. 39th int. Symp. em computação simbólica e algébrica, 2014