Bukti bahwa multiplikasi matriks dapat dilakukan dalam waktu kuadratik?

59

Secara luas diduga bahwa , eksponen optimal untuk perkalian matriks, sebenarnya sama dengan 2. Pertanyaan saya sederhana: $\omega$

Apa alasan yang kita miliki untuk meyakini bahwa ? $\omega = 2$

Saya mengetahui algoritma cepat seperti Coppersmith-Winograd, tapi saya tidak tahu mengapa ini dianggap bukti untuk . $\omega = 2$

Secara naif, menurut saya seperti contoh klasik di mana sebuah komunitas hanya berharap bahwa hasilnya benar-benar murni untuk alasan estetika. Saya ingin tahu apakah pada dasarnya itulah yang terjadi di sini.

ds.algorithms linear-algebra matrix-product Steve Flammia
sumber

12

Saya menduga jawabannya sebagian besar adalah estetika, dan kurangnya alasan yang baik untuk menjadi lebih besar dari 2. Ada sebuah makalah di FOCS '05 yang memberikan beberapa konstruksi teori kelompok untuk matriks mult yang cocok dengan eksponen yang dikenal saat ini dan juga memberi 2 kelompok dugaan teori yang menyiratkan

. PDF

ω = 2

$\omega=2$

Mark Reitblatt

5

Beberapa tahun yang lalu, saya berbicara dengan Strassen di mana dia mengatakan dia percaya

. Saya tidak yakin apa alasannya.

ω > 2

$\omega > 2$

Ryan Williams

2

@Ryan, semoga Strassen membaca cstheory.stackexchange. :)

Steve Flammia

3

Ada

batas bawah (di bawah beberapa batasan) karena Ran Raz, jadi dugaan yang lebih baik adalah bahwa

tidak tercapai (tapi infimumnya memang

).

Ω (n \log n)

$\Omega(n\log n)$

ω = 2

$\omega = 2$

2

$2$

Yuval Filmus

5

@Yuval, @Steve: 1)

biasanya didefinisikan sebagai batas. 2) Kita sudah tahu bahwa apa pun

itu, itu tidak tercapai (itu adalah inf dan bukan min). Lihat makalah Coppersmith-Winograd ini: dx.doi.org/10.1137/0211038 . Dari abstrak: "eksponen untuk perkalian matriks adalah titik batas, yaitu, tidak dapat diwujudkan dengan algoritma tunggal." (Mengingat perincian hasil mereka, saya pikir pernyataan ini tidak bisa diterima secara naif pada nilai nominalnya, tetapi ini sebagian besar merupakan masalah teknis.)

ω

$\omega$

ω

$\omega$

Joshua Grochow

20

Saya ingin menambahkan komentar Mark Reitblatt dan jawaban Amir Shpilka. Pertama, salah satu dugaan yang diajukan oleh Cohn, Kleinberg, Szegedy, dan Umans bukan teori kelompok tetapi murni kombinatorial (Konj. 3.4 dalam makalah FOCS '05 mereka ). Dugaan ini mengatakan bahwa "kapasitas USP yang kuat adalah "Coppersmith dan Winograd, dalam menunjukkan algoritma terbaik mereka saat ini untuk perkalian matriks, menunjukkan bahwa kapasitas USP adalah nomor yang sama ini $\frac{3}{2^{2/3}}$ (meskipun mereka tidak frase itu cukup dengan cara ini). Meskipun ada perbedaan antara USP yang kuat dan USP, ini adalah beberapa bukti bahwa dugaan mereka setidaknya masuk akal. $\frac{3}{2^{2/3}}$

(Untuk dugaan 4.7 mereka yang lain, yang merupakan teori kelompok, saya tidak tahu adanya bukti yang masuk akal yang serupa, di luar sekadar intuisi.)

Kedua, saya setuju dengan Amir Shpilka bahwa rangkaian algoritma masa lalu memiliki nuansa ad-hoc. Namun, salah satu hal yang menyenangkan tentang pendekatan kelompok-teori adalah bahwa hampir semua (tidak semua) dari algoritma sebelumnya dapat diungkapkan dalam pendekatan ini. Meskipun berbagai konstruksi teori-kelompok dalam [CKSU] mungkin tampak sedikit ad-hoc di luar, dalam konteks kerangka teori-kelompok mereka terlihat secara signifikan lebih alami dan lebih sedikit ad-hoc (setidaknya bagi saya) daripada banyak dari algoritma sebelumnya.

Joshua Grochow
sumber

Ketika saya berpikir tentang Kapasitas, saya berpikir tentang set dan klik independen. Apa kamus antara USP dan konstruksi eksplisit dari grafik yang mendasarinya dan apakah ada struktur untuk grafik ini?

T ....

28

$\omega=2$ $\omega=2$

Amir Shpilka
sumber

20

$\omega = 2$

$A$ $B$ $n$ $n$ $C = AB$ $C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$ $A$ $B$ $n$ $C = A*B$ $C(i) = \sum_{k=1}^n A(k)B(i-k)$ $\tilde{O}(n)$ $O(n^2)$ $\tilde{O}(n^2)$ algoritma waktu untuk perkalian matriks. Pertanyaannya adalah: apa analog dari transformasi Fourier yang dapat membantu untuk perkalian matriks?

arnab
sumber

-1

$O(n^{2} log(n^2))$ $\omega = 2$

Chad Brewbaker
sumber

1

ω

$\omega$

c

$c$

O (n^{c})

$O(n^c)$

O (n^{2} \log^{10} n)

$O(n^2 \log^{10} n)$

2

$2$

Ω (n^{2} \log n)

$\Omega(n^2\log n)$

@SashoNikolov Terima kasih telah menunjukkan itu. Adakah yang pernah mencoba melatih jaring saraf untuk boolean matmul A * B = C? [Entri A, entri B, entri C] -> Bool (kalikan benar atau salah). Ingin tahu sirkuit apa yang layak / dropout gradien datang dengan; jika sirkuit terlatih memiliki penarik dekat dekomposisi prima. Pada 3x3, 4x4, 5x5, 6x6 sepertinya satu jam GPU akan memberikan beberapa hasil menarik.

Chad Brewbaker

Bukti bahwa multiplikasi matriks dapat dilakukan dalam waktu kuadratik?

Jawaban: