Bagaimana membuktikan bahwa perkalian matriks dua matriks 2x2 tidak dapat dilakukan dalam kurang dari 7 perkalian?

Dalam perkalian matriks Strassen, kami menyatakan satu fakta aneh (setidaknya bagi saya) bahwa perkalian matriks dua 2 x 2 membutuhkan 7 perkalian.

Pertanyaan: Bagaimana cara membuktikan bahwa tidak mungkin untuk menggandakan dua matriks 2 x 2 dalam 6 perkalian?

Harap dicatat bahwa matriks melebihi bilangan bulat.

algorithms complexity-theory lower-bounds Kompleksitas
sumber

Ada algoritma penggandaan matriks lain yang bisa lebih cepat. Artikel web ini dari kelas Stanford CME 323 memberikan rincian tentang algoritma Strassen, perkalian Matriks: Algoritma Strassen . Ada topik Wikipedia, algoritma Strassen yang masuk ke detail dan memiliki tautan ke informasi tambahan.

Richard Chambers

@RichardChambers Perhatikan bahwa algoritma Strassen memiliki perkalian. Tampaknya masuk akal bagi saya bahwa batas bawah ini benar.

7

$7$

Stella Biderman

Seperti kata pertanyaan ini salah. Ada banyak matriks yang bisa dikalikan dengan perkalian. Anda bermaksud meminta bukti bahwa, dalam kasus terburuk, dibutuhkan 7 alias ada beberapa matriks yang membutuhkan 7

6

$6$

Stella Biderman

@StellaBiderman ya saya melihat bahwa Strassen memiliki 7 perkalian. Saya tidak melihat yang lain, lebih cepat dan algoritma dengan kompleksitas yang lebih rendah. Dari apa yang saya tahu mereka menggunakan pendekatan sub-matriks yang sama dengan Strassen tetapi saya tidak yakin. Saya baru saja menambahkan beberapa informasi tambahan tentang Strassen secara khusus.

Richard Chambers

Tampaknya ada sesuatu yang hilang dari pertanyaan Anda. Saya dapat dengan mudah memberikan algoritma yang dapat melipatgandakan setidaknya beberapa matriks dengan 0 perkalian. Mungkin ada kendala yang tidak Anda sebutkan.

Jörg W Mittag

Jawaban:

Ini adalah hasil klasik dari Winograd: Pada perkalian dari matriks 2x2 .

Strassen menunjukkan bahwa eksponen perkalian matriks adalah sama dengan eksponen pangkat tensor tensor perkalian matriks: kompleksitas aljabar perkalian matriks adalah jika pangkat pangkat tensor dari (tensor perkalian matriks yang sesuai dengan perkalian dua matriks) adalah . Algoritma Strassen menggunakan arah mudah untuk menyimpulkan dari batas atas . $n\times n$ $O(n^\alpha)$ $\langle n,n,n \rangle$ $n\times n$ $O(n^\alpha)$ $O(n^{\log_27})$ $R(\langle 2,2,2 \rangle) \leq 7$

Hasil Winograd menyiratkan bahwa . Landsberg menunjukkan bahwa peringkat perbatasan juga 7, dan Bläser et al. baru-baru ini diperluas untuk mendukung pangkat dan pangkat dukungan perbatasan. Peringkat perbatasan dan peringkat dukungan adalah gagasan peringkat yang lebih lemah (= lebih kecil) yang telah digunakan (dalam kasus peringkat perbatasan) atau diusulkan (dalam kasus peringkat dukungan) dalam algoritma multiplikasi matriks cepat. $R(\langle 2,2,2 \rangle)=7$ $\langle 2,2,2 \rangle$

Yuval Filmus
sumber

Anda dapat menemukan hasilnya di:

S.Winograd, Pada penggandaan 2 × 2 matriks , Aljabar Linier dan Appl. 4 (1971), 381–388, MR0297115 (45: 6173).

Stella Biderman
sumber