matrix_multiply_quadratic
1.0.0
Ce code source (dans Python) est une implémentation préliminaire de ma multiplication de matrice entière positive en temps quadratique qui a été théoriquement prouvé de sa complexité de temps et d'espace dans l'un de mes préparations [1]. Il y a eu plusieurs propositions sur les optimisations des algorithmes sous-cubiques depuis l'amélioration de la version récursive par Strassen (fonctionnant dans O (n ^ log2 (7)) = O (n ^ 2.807)) [2], comme celle de Bini et al. (exécutant O (n ^ 2,78)) [3], un autre par Strassen (en cours d'exécution dans O (n ^ 2.479)) [4], par Coppersmith et Winograd (exécutant O (n ^ 2.375)) [5], par Williams (exécutant O (N ^ 2.3729)) [6] et le plus récemment par François Le-Gall (exécutant dans O (n ^ 2.372639). Mais tous sont théoriquement solides mais pas pratiquement implémentables en raison des fortes structures de données telles que les pouvoirs du tenseur. Le contexte théorique a été démontré et prouvé sur son exactitude en fonction des méthodes théoriques du nombre [1]. Le fichier 'matrix_multiply_test.py' est essentiellement un fichier de test unitaire qui prouve pratiquement l'exactitude de ma méthode. Mais la méthode a été conçue et testée uniquement pour des entiers positifs, qui peuvent être modifiés bien pour s'adapter aux cas avec des entiers négatifs, des nombres flottants et des nombres complexes. L'implémentation réelle de l'algorithme a été affichée dans le fichier 'matrix_multiply_quadratic.py'. Parallèlement à tout cela, j'ai inclus une implémentation basée sur le threading qui est un très bon exemple d'automate cellulaire. La version testée de la mise en œuvre basée sur CA est indiquée dans 'CAMATRIX_MULT_TEST.PY'. L'analyse de complexité temporelle a été montrée dans «Camatrix_mult.py».
[1] S. Mohapatra, "Méthode théorique de nombre convolutionnel pour optimiser la multiplication de la matrice entière", [Arxiv: 1806.03701], 2018
[2] V. Strassen, "L'élimination gaussienne n'est pas optimale", numérique. Mathématiques. 13, p. 354-356, 1969
[3] D. Bini, M. Capovani, F. Romani et G. Lotti. "O (n ^ 2,7799) Complexité pour n × n multiplication matricielle approximative" inf. Processus. Lett., Pp. 234-235, 1979
[4] V. Strassen, "Le spectre asymptotique des tenseurs et l'exposant de la multiplication matricielle", Proc. 27th Ann. IEEE Symp. Sur les fondations de l'informatique, pp. 49-54, 1984
[5] D. Coppersmith, S. Winograd, "Matrix Multiplication via des progressions arithmétiques". J. Symbolic Comput. pp. 251–280, 1980
[6] V. Williams, "Multiplying Matrices plus rapidement que Coppersmith-Winograd". ACM: pp.887–898, 2012
[7] F. le Gall, "Pouvoirs des tenseurs et multiplication de la matrice rapide", Proc. 39th Int. Symp. Sur le calcul symbolique et algébrique, 2014
