Bukti bahwa perkalian matriks tidak dalam

39

Hal ini umumnya percaya bahwa untuk semua ϵ>0 , adalah mungkin untuk kalikan dua n×n matriks di O(n2+ϵ) waktu. Beberapa diskusi ada di sini .

Saya telah bertanya kepada beberapa orang yang lebih akrab dengan penelitian apakah mereka berpikir bahwa ada k>0 independen dari n sehingga ada algoritma O(n2logkn) untuk perkalian matriks dan mereka tampaknya memiliki intuisi yang jawabannya adalah "tidak" tetapi tidak bisa menjelaskan alasannya. Yaitu, mereka percaya bahwa kita dapat melakukannya dalam waktu O(n2.001) , tetapi bukan waktu O(n2log100n) .

Apa alasan di sana untuk percaya bahwa tidak ada algoritma O(n2logkn) pada k>0 tetap > 0 ?

Brian
sumber

Jawaban:

29

Ada sebuah algoritma untuk mengalikan sebuah N×N0.172 matriks dengan N0.172×N matriks di N2polylog(N) operasi aritmatika. Identitas utama yang digunakan untuk itu berasal dari makalah Coppersmith "Multiplikasi cepat dari matriks persegi panjang", tetapi penjelasan mengapa itu mengarah ke N2polylog(N) bukannya N2+ϵ ada dalam lampiran kertas Williams , "Algoritma baru dan batas bawah untuk sirkuit dengan gerbang ambang batas linier ".

Ini hanya berfungsi karena identitas Coppersmith memiliki beberapa struktur tambahan yang dapat Anda manfaatkan, dan algoritma MM yang lebih baru tampaknya tidak memiliki struktur ini. Yang mengatakan, aku tidak yakin mengapa seseorang tidak bisa berharap untuk memperluas pendekatan ini untuk N×N×N perkalian matriks.

Josh Alman
sumber
11

Nah, satu hal adalah saya berpikir bahwa semua konstruksi yang kita ketahui - dan bahkan keluarga konstruksi potensial yang telah diusulkan orang (misalnya, pendekatan Cohn-Umans, generalisasi Coppersmith-Winograd) - "hanya" akan menghasilkan keluarga algoritma Aϵ berjalan dalam waktu O(n2+ϵ) . Jadi untuk memiliki algoritma tunggal yang berjalan di O(n2poly(logn)) , itu tidak hanya harus menjadi gila asimptotik lebih baik daripada pendekatan saat ini, tetapi harus terlihat sangat berbeda.

Peringatan besar: saya pikir. Saya tidak pernah benar-benar berpikir terlalu keras tentang berapa banyak orang harus memodifikasi / menambah pendekatan yang ada sehingga mereka dapat menghasilkan algoritma tunggal yang berjalan pada waktu O(n2poly(logn)) .

Joshua Grochow
sumber
3
Saya tidak yakin bagaimana memiliki keluarga tidak masuk akal menuju O (n ^ 2poly (log n)) karena jika seseorang dapat menggambarkan keluarga dengan cukup baik maka seseorang dapat memilih anggota keluarga yang lebih dan lebih efisien untuk n yang lebih besar. Satu-satunya alasan kemudian bahwa ini tidak masuk akal O (n ^ 2poly (log N)) adalah bahwa konstanta yang terlibat mungkin akan sangat besar, tetapi tidak jelas bahwa itulah yang terjadi.
JoshuaZ
1
O(n2+x)ε>0O(n2+ε)
1
@ JoshuaZ Saya kira cara lain yang lebih aneh lagi bisa gagal adalah jika entah bagaimana memilih / membangun anggota keluarga mengambil lebih dari O (n ^ 2 poly (log n)) waktu - misalnya mungkin O (1 / e) kode diperlukan untuk mengimplementasikan algoritma O (n ^ (2 + e)) atau sesuatu. Bukankah itu liar ??
Daniel Wagner