Bagaimana Strassen menemukan metode multiplikasi matriksnya?

Yang terkenal Algoritma perkalian matriks Strassen yang adalah suguhan yang nyata bagi kita, karena mengurangi kompleksitas waktu dari O tradisional (n ³ ) menjadi O (n ^2.8 ).

Tetapi dari semua sumber daya yang telah saya lalui, bahkan buku Cormen dan Steven Skienna, mereka jelas tidak menyatakan bagaimana Strassen memikirkannya.

Apa dasar pemikiran dari algoritma penggandaan matriks Strassen? Apakah ini kecelakaan beruntung atau ada sesuatu yang lebih dalam di dalamnya?

Selain Strassen, tidak ada yang bisa memberi tahu Anda bagaimana Strassen mendapatkan idenya. Howeber¹, saya dapat memberitahu Anda, bagaimana Anda bisa menemukan formula itu sendiri — asalkan Anda tertarik pada geometri aljabar dan teori representasi. Ini juga memberi Anda alat untuk menunjukkan bahwa formula Strassen sebagus mungkin, atau lebih tepatnya, itu tidak ada formula yang menghitung produk dari dua matriks 2 × 2 yang menggunakan kurang dari 7 perkalian .

Karena Anda tertarik oleh matriks saya menganggap Anda tahu aljabar linier dasar dan akan sedikit buram untuk detail yang lebih maju.

Pertama biarkan E himpunan semua peta linier dari pesawat ke pesawat. Ini pada dasarnya adalah himpunan semua matriks 2 × 2, tetapi kita lupa tentang sistem koordinat tertentu — karena, jika ada sistem koordinat yang lebih baik daripada "standar" kita bisa tertarik menggunakannya untuk perkalian matriks. Kami juga menyatakan dengan E space ruang ganda E dan oleh X = P (E⊗E † ⊗E †) ruang proyektif yang terkait dengan produk tensor E⊗E † ⊗E † .

Unsur X = P (E⊗E † ⊗E †) dari bentuk khusus [c⊗α⊗β] dapat diartikan sebagai operasi dasar pada matriks, yang, dalam beberapa sistem koordinat yang tepat, membaca koefisien matriks sebuah dan koefisien dari matriks B dan menulis produk dari koefisien ini dalam beberapa matriks C . Unsur umum X adalah kombinasi dari operasi-operasi dasar, sehingga produk π dari dua matriks, dipahami sebagai peta dari P (E) × P (E) ke P (E), adalah titik di X .

Rumus produk matriks biasa dan formula Strassen dapat dinyatakan sebagai kombinasi dari operasi linier ini, jadi izinkan saya menyatakan oleh W₁ himpunan operasi elementer ini [c⊗α⊗β] dan biarkan saya menggambarkan secara geometris kombinasi mereka.

Biarkan W₂ menjadi berbagai secants dari W₁ di X. Hal ini diperoleh dengan mengambil (penutupan) gabungan dari semua lini akan melalui dua titik (generik) dari W₁ . Kita dapat menganggapnya sebagai himpunan semua kombinasi dari dua operasi elemetary.

Biarkan W₃ menjadi berbagai pesawat sekan dari W₁ di X. Hal ini diperoleh dengan mengambil (penutupan) persatuan semua pesawat akan melalui tiga poin (generik) dari W₁ . Kita dapat menganggapnya sebagai himpunan semua kombinasi dari tiga operasi elemetary.

Demikian pula, kami mendefinisikan varietas garis potong untuk indeks yang lebih besar. Perhatikan bahwa varietas ini tumbuh lebih besar dan lebih besar, yaitu W₁⊂W₂⊂W₃⊂ ⋯ Karenanya formula produk matriks klasik menunjukkan bahwa produk dari matriks adalah titik W₈ . Sebenarnya

PROPOSISI (Strassen) - Produk dari matriks π terletak di W₇.

Sejauh yang saya tahu, Strassen tidak menempatkan hal-hal seperti itu, namun ini adalah sudut pandang geometris pada pertanyaan ini. Sudut pandang ini sangat berguna, karena juga memungkinkan Anda membuktikan bahwa formula Strassen adalah yang terbaik, yaitu, bahwa π tidak terletak pada W₆ . Metode geometris yang dikembangkan di sini juga dapat digunakan untuk berbagai masalah yang lebih luas.

Saya harap, saya menangkap rasa ingin tahu Anda. Anda dapat melangkah lebih jauh dengan membaca artikel ini oleh Landsberg dan Manivel:

http://arxiv.org/abs/math/0601097

¹ Saya tidak akan memperbaiki kesalahan ketik ini, karena saya masuk angin.

Saya baru saja ditugaskan mengerjakan ini untuk pekerjaan rumah, dan saya pikir saya memiliki pencerahan yang rapi: Algoritma Strassen mengorbankan "luasnya" komponen pra-penjumlahannya untuk menggunakan lebih sedikit operasi dengan imbalan komponen pra-penjumlahan "lebih dalam" yang masih bisa digunakan untuk mengekstrak jawaban akhir. (Ini bukan cara terbaik untuk mengatakannya, tetapi sulit bagi saya untuk menjelaskannya).

Saya akan menggunakan contoh mengalikan dua bilangan kompleks bersama-sama untuk menggambarkan keseimbangan " operasi vs. komponen ":

Perhatikan bahwa kami menggunakan 4 perkalian, yang menghasilkan 4 komponen produk :

Perhatikan bahwa 2 komponen akhir yang kita inginkan: bagian nyata dan imajiner dari bilangan kompleks, sebenarnya adalah persamaan linier: mereka adalah jumlah produk skala. Jadi kita berurusan dengan dua operasi di sini: penjumlahan dan perkalian.

Faktanya adalah bahwa 4 komponen produk kami dapat mewakili 2 komponen akhir kami jika kami hanya menambah atau mengurangi komponen kami:

Namun, 2 komponen akhir kami dapat direpresentasikan sebagai jumlah produk. Inilah yang saya pikirkan:

Jika Anda dapat melihat, kami sebenarnya hanya membutuhkan 3 komponen produk yang berbeda untuk membuat dua komponen terakhir kami:

Tapi tunggu! Setiap huruf kapital ada di dalam produk mereka sendiri! Tetapi tangkapannya adalah bahwa kita tahu bahwa kita dapat menghasilkan (A + B + C + D) dari (a + b) (c + d), yang hanya 1 kali perkalian.

Jadi pada akhirnya, algoritma kami dioptimalkan untuk menggunakan lebih sedikit, tetapi komponen "lebih gemuk", tempat kami menukar jumlah penggandaan untuk operasi penjumlahan yang lebih banyak.

Bagian dari apa yang memungkinkan ini adalah properti distributif, yang memungkinkan A (B + C) setara dengan (AB + AC). Perhatikan bagaimana yang pertama dapat dihitung menggunakan operasi 1 add dan 1 multiply, sedangkan yang kedua membutuhkan 2 multiply dan 1 sum.

Algoritma Strassen adalah perpanjangan dari optimasi yang kami terapkan pada produk bilangan kompleks, kecuali ada lebih banyak istilah target produk dan kemungkinan lebih banyak komponen produk yang dapat kita gunakan untuk mendapatkan persyaratan tersebut. Untuk matriks 2x2, algoritma Strassen mengubah algoritma yang membutuhkan 8 perkalian menjadi satu yang membutuhkan 7 perkalian, dan memanfaatkan properti distributif untuk "menggabungkan" dua perkalian menjadi satu operasi, dan alih-alih mengambil dari simpul "lebih gemuk" untuk mengekstraksi satu istilah produk atau yang lain, dll.

Contoh yang baik: untuk mendapatkan (-1) dan (2) dan (5), Anda dapat menganggapnya hanya (-1), (2), (5), atau Anda dapat menganggapnya sebagai (2-3) ), (2), (2 + 3). Namun, operasi kedua menggunakan angka yang tidak terlalu berbeda. Tangkapannya adalah bahwa jumlah angka yang berbeda setara dengan jumlah komponen produk yang Anda perlukan untuk perkalian matriks. Kami hanya mengoptimalkan ini untuk menemukan pandangan tertentu dari operasi yang mendasari yang memanfaatkan output isomorfik menggunakan variasi yang berbeda melalui properti distributif.

Mungkin ini bisa dikaitkan dengan topologi dalam beberapa cara? Ini hanya cara awam saya memahaminya.

Sunting: Ini adalah gambar catatan saya yang saya gambar dalam proses membuat penjelasan bilangan kompleks: