matrix_multiply_quadratic
1.0.0
このソースコード（Python）は、私のプリプリントの1つでその時間と空間の複雑さについて理論的に証明された私の2次陽性整数マトリックス増殖の予備的な実装です[1]。 Strassen（o（n^log2（7））= o（n^2.807）で実行されている再帰バージョンの即興以来、サブキュービックアルゴリズムの最適化に関するいくつかの提案がありました。 （o（n^2.78）で実行）[3]、もう1つはstrassen（o（n^2.479）で実行されている）[4]、coppersmith and winograd（o（n^2.375）で実行されている）[5]、ウィリアムズ（O（n^2.3729）での実行）[6）[6]、および最近のO [6]しかし、それらはすべて理論的に健全ですが、テンソルパワーなどの重いデータ構造のために実際には実装できません。理論的背景は、数の理論的方法に基づいてその正しさに基づいて示され、証明されています[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、p。 354-356、1969
[3] D.ビニ、M。カポヴァニ、F。ロマニ、およびG.ロッティ。 "o（n^2.7799）n×n近似マトリックス増殖の複雑さ" inf。プロセス。 Lett。、pp。234–235、1979
[4] V. Strassen、「テンソルの漸近スペクトルとマトリックス増殖の指数」、Proc。 27番目のアン。 IEEE Symp。 Computer Scienceの基礎、pp。49-54、1984
[5] D. Coppersmith、S。Winograd、「算術的進行によるマトリックス増殖」。 J.シンボリックコンピューター。 pp。251–280、1980
[6] V. Williams、「Coppersmith-Winogradよりも速くマトリックスを掛ける」。 ACM：pp.887–898、2012
[7] F. Le Gall、「テンソルの力と高速行列乗算」、Proc。 39th int。 symp。 Symbolic and Algebraic Computation、2014年
