matrix_multiply_quadratic
1.0.0
该源代码（以Python为单位）是我的二次时间正整数矩阵乘法的初步实现，从理论上讲，它在我的一个预印象中是其时间和空间复杂性的[1]。自strassen（在O（n^log2（7）中运行）递归版本以来，已经提出了几项关于亚立方算法优化的建议，例如Bini等人。 （在O（n^2.78）中运行）[3]，另一个由Strassen（在O（n^2.479）中运行（由Coppersmith和Winograd运行（在O（N^2.375）中运行）[5] [5]），Williams（在O（n^2.3729）中运行（n^2.3729）[6] [6] [6] [6]和Francois le-le-le-le-le-le-le-gall（n^33）（^33）。但是所有这些都在理论上是合理的，但由于张张量诸如张量的强度，因此在实际上无法实现。基于数字理论方法[1]，已经显示了理论背景并根据其正确性证明了其正确性。文件“ matrix_multiply_test.py”基本上是一个单元测试文件，实际上证明了我方法的正确性。但是该方法仅针对正整数进行设计和测试，可以恰当地修改这些方法，以适应负整数，浮数量和复数数字的案例。该算法的实际实现已在“ matrix_multiply_quadratic.py”中显示。除此之外，我还包括了一个基于多线程的实现，这是蜂窝自动机的一个很好的例子。基于CA的实现的测试版本显示在“ Camatrix_mult_test.py”中。时间复杂性分析已在“ camatrix_mult.py”中显示。
[1] S. Mohapatra，“优化整数矩阵乘法的卷积数学理论方法”，[arxiv：1806.03701]，2018年
[2] V. Strassen，“高斯消除不是最佳的”，numer。数学。 13，第1页。 354-356，1969
[3] D. Bini，M。Capovani，F。Romani和G. Lotti。 n×n近似矩阵乘法的“ O（N^2.7799）复杂性” Inf。过程。 Lett。，第234–235页，1979年
[4] V. Strassen，“张量的渐近光谱和矩阵乘法的指数”，Proc。第27安。 IEEE SYMP。关于计算机科学基础，第49-54页，1984年
[5] D. Coppersmith，S。Winograd，“通过算术进程的矩阵乘法”。 J.符号计算。第251–280页，1980年
[6] V. Williams，“比Coppersmith-Winograd更快地乘坐矩阵”。 ACM：第887–898页，2012年
[7] F. Le Gall，“张量和快速矩阵乘法的功率”，Proc。第39 int。 SYMP。关于符号和代数计算，2014年
