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年
