Perkalian matriks dalam

13

Saya searching tentang Matrix perkalian, Jadi saya kunjungan pertama wiki perkalian matriks algoritma, Dalam referensi saya menemukan kertas yang mengklaim bahwa penggunaan algoritmaHAI(n2lHaig(n)) , aku akan membaca artikel tetapi rumit dan akan terlalu banyak waktu untuk membacanya, tetapi jika ada orang yang membaca artikel ini atau mengetahui tentang algoritma ini, apakah ini benar? dan apakah Anda tahu tentang Ide dasar ini untuk menjelaskannya sedikit.

Terima kasih sebelumnya, saya tahu ini adalah pertanyaan umum tetapi, jika saya temukan itu pendekatan yang bagus saya akan mempelajari detailnya.

ds.algorithms linear-algebra matrix-product Saeed
sumber
5
Saya pikir berguna untuk memahami pertanyaan Anda sendiri dengan lebih baik. Apakah Anda mencari algoritma sekuensial atau algoritma paralel? Tidak ada algoritma berurutan untuk perkalian matriks dengan waktu O (n ^ 2 log n) yang diketahui, dan kertas oleh Hawa adalah hasil parsial terhadap algoritma tersebut (saya tidak membaca kertas, saya hanya membaca skim). Jika Anda peduli dengan waktu paralel, maka waktu paralel O (log n) (dengan asumsi penambahan skalar dan perkalian skalar dalam waktu konstan) adalah standar dan Anda dapat menemukan penjelasan dalam misal buku Komputasi Kompleksitas oleh Papadimitriou.
Tsuyoshi Ito
2
(1) Harap edit pertanyaan Anda sehingga jelas bahwa Anda bertanya tentang algoritma berurutan. (2) Saya menyadari bahwa Anda menambahkan tag [komputasi kuantum]. Harap edit pertanyaan Anda untuk menjelaskan hubungannya dengan komputasi kuantum. (Dugaan saya adalah bahwa pertanyaan Anda dimotivasi oleh komputasi kuantum, tetapi penjelasan Anda sendiri jauh lebih berguna daripada dugaan apa pun.)
Tsuyoshi Ito
2
Saya sarankan Anda menghapus pertanyaan ini terlebih dahulu, dan kemudian mengirim ulang nanti jika Anda memiliki pertanyaan.
Suresh Venkat
3
@ Saeed: Masalah ini telah dibahas tentang meta dan saat ini ini adalah kebijakan situs, jika Anda ingin membahas kebijakan tersebut gunakan meta. Di sisi lain, Anda dapat memodifikasi pertanyaan dan menghindari menyebutkan makalah untuk membuatnya sesuai topik, misalnya memodifikasi pertanyaan menjadi "apa algoritma yang paling dikenal untuk perkalian matriks dalam model X?" dan itu akan menjadi topik. (catatan: jika Anda sendiri tidak dapat memverifikasi kebenaran makalah yang tidak diterbitkan dan ingin mengutipnya, Anda harus menunggu sampai ditinjau dan diterbitkan oleh rekan sejawat.)
Kaveh
3
Diskusi terkait Meta: Apakah boleh bertanya tentang kebenaran pracetak pada topik ramah-engkol? Saya tidak mengklaim bahwa semua yang tertulis pada halaman itu akan berlaku untuk pertanyaan ini, tetapi setidaknya terkait erat.
Tsuyoshi Ito

Jawaban:

34

Saya menemukan makalah ini sekitar setahun yang lalu, tetapi belum sempat membacanya dengan cermat. Saya dapat memberitahu Anda bahwa pendekatannya tidak diyakini benar. Pada halaman 36 dari makalah yang sama, ada komentar terlampir oleh Don Knuth, yang menunjukkan apa yang tampaknya merupakan kelemahan serius dari pendekatan tersebut.

Untuk memahami makalah ini, Anda perlu belajar tentang aljabar kelompok dan teori representasi. Ini akan sulit jika Anda belum pernah melihat materi semacam itu sebelumnya.

Ryan Williams
sumber