matrix_multiply_quadratic

Algoritma waktu kuadratik untuk multiplikasi matriks dengan bilangan bulat positif

Kode sumber ini (dalam Python) adalah implementasi awal dari multiplikasi matriks integer positif-kuadratik saya yang secara teoritis terbukti secara teoritis waktu dan kompleksitas ruang di salah satu pracetak saya [1]. Telah ada beberapa proposal tentang optimasi algoritma sub-kubik sejak perbaikan versi rekursif oleh Strassen (berjalan dalam O (N^log2 (7)) = O (n^2.807)) [2], seperti itu oleh Bini et al. (Berjalan di O (n^2.78)) [3], satu lagi oleh Strassen (berjalan di O (n^2.479)) [4], oleh Coppersmith dan Winograd (berjalan di O (n^2.375)) [5], oleh Williams (berjalan di O (n^2.3729)) [6] dan baru-baru ini oleh Francois. Tetapi semuanya secara teoritis sehat tetapi tidak dapat diterapkan secara praktis karena struktur data yang berat seperti kekuatan tensor. Latar belakang teoritis telah ditunjukkan dan dibuktikan pada kebenarannya berdasarkan metode teoretik angka [1]. File 'matrix_multiply_test.py' pada dasarnya adalah file pengujian unit yang secara praktis membuktikan kebenaran metode saya. Tetapi metode ini telah dirancang dan diuji hanya untuk bilangan bulat positif, yang dapat dimodifikasi dengan tepat agar sesuai dengan kasus dengan bilangan bulat negatif, angka mengambang, dan bilangan kompleks juga. Implementasi aktual dari algoritma telah ditampilkan dalam file 'matrix_multiply_quadratic.py'. Seiring dengan semua ini, saya telah memasukkan implementasi berbasis multi-threading yang merupakan contoh yang sangat baik dari otomat seluler. Versi yang diuji dari implementasi berbasis CA ditampilkan dalam 'CAMATRIX_MULT_TEST.PY'. Analisis kompleksitas waktu telah ditunjukkan dalam 'CAMATRIX_MULT.py'.

Referensi

[1] S. Mohapatra, "Metode Nomor-Teori Konvolusional untuk Mengoptimalkan Perhimpunan Matriks Integer", [Arxiv: 1806.03701], 2018

[2] V. Strassen, "Eliminasi Gaussian tidak optimal", numer. Matematika. 13, hlm. 354-356, 1969

[3] D. Bini, M. Capovani, F. Romani, dan G. Lotti. "O (N^2.7799) Kompleksitas untuk N × N Perkiraan Matriks Perkiraan" Inf. Proses. Lett., Hlm. 234–235, 1979

[4] V. Strassen, "Spektrum asimptotik tensor dan eksponen multiplikasi matriks", Proc. 27th Ann. IEEE Symp. On Foundations of Computer Science, hlm. 49-54, 1984

[5] D. Coppersmith, S. Winograd, "Multiplikasi Matrix melalui Progressions Aritmatika". J. Symbolic Comput. hlm. 251–280, 1980

[6] V. Williams, "Mengalikan Matriks lebih cepat dari Coppersmith-Winograd". ACM: pp.887–898, 2012

[7] F. Le Gall, "Kekuatan Tensor dan Perkalian Matriks Cepat", Proc. Int ke -39. Simp. Tentang Perhitungan Simbolik dan Aljabar, 2014