Kompleksitas ruang algoritma Coppersmith – Winograd

24

Algoritma Coppersmith-Winograd adalah algoritma yang diketahui paling cepat secara asimptot untuk mengalikan dua matriks persegi. Waktu berjalan dari algoritma mereka adalah yang merupakan yang paling dikenal sejauh ini. Apa kompleksitas ruang dari algoritma ini? Apakah itu di ?n×nO(n2.376)Θ(n2)

Siwa Kintali
sumber

Jawaban:

30

Ya, semua algoritma yang berasal dari algoritma asli Strassen (ini termasuk algoritma paling dikenal untuk perkalian matriks, tetapi tidak semua - lihat komentar) memiliki kompleksitas ruang . Jika Anda dapat menemukan algoritma waktu dengan kompleksitas ruang , ini akan menjadi kemajuan besar. Satu aplikasi akan berupa algoritma ruang , untuk masalah Subset-Sum.n3εΘ(n2)n3εpoly(logn)2(1ε)npoly(n)

Namun ada beberapa kendala untuk hasil seperti itu. Untuk beberapa model komputasi, ada batas bawah yang cukup kuat untuk produk ruang-waktu multiplikasi matriks. Referensi seperti Yesha dan Abrahamson akan memberi Anda informasi lebih lanjut.

Ryan Williams
sumber
Hai Ryan, Luar Biasa. Bagaimana dengan algoritma kelompok-teoretis oleh Cohn-Umans [FOCS2003] dan Cohn-Kleinberg-Szegedy-Umans [FOCS2005]?
Shiva Kintali
1
Ya, itu juga. Pemahaman saya adalah bahwa mereka sedang melakukan semacam konvolusi khusus (FFT di atas grup khusus), tetapi konvolusi tersebut adalah objek ukuran . Tidak ada algoritma ruang kecil (dengan kompleksitas waktu lebih baik daripada algoritma yang jelas) yang dikenal untuk konvolusi vektor di atas bilangan bulat, dan saya membayangkan itu hanya lebih sulit untuk mendapatkan konvolusi ruang kecil atas kelompok-kelompok ini. Θ(n2)
Ryan Williams
Bagaimana seseorang dapat memiliki ruang ketika dibutuhkan 2 n 2 ruang untuk menyimpan entri dari matriks? poly(logn)2n2
T ....
O(logn)O(n3)
1
Saya tidak tahu apa yang ada dalam pikiran Anda, tetapi pasti ada "kombinatorial" (table look-up) algs untuk Boolean matrix mult yang mengalahkan n ^ 3 kali oleh faktor log dan menggunakan jauh lebih sedikit dari n ^ 2 ruang ...
Ryan Williams