Kompleksitas komputasi perkalian matriks

Saya mencari informasi tentang kompleksitas komputasi perkalian matriks matriks persegi panjang. Wikipedia menyatakan bahwa kompleksitas mengalikan oleh B ∈ R n × p adalah O ( m n p ) (buku sekolah perkalian).$A \in \mathbb{R}^{m \times n}$$B \in \mathbb{R}^{n \times p}$$O(mnp)$

Saya punya kasus di mana dan n jauh lebih kecil dari p , dan saya berharap untuk mendapatkan kompleksitas yang lebih baik daripada linear dalam p , dengan biaya membuat ketergantungan pada m dan n lebih buruk daripada linear.$m$$n$$p$$p$$m$$n$

Ada ide?

Terima kasih.

Catatan: alasan saya berharap hal itu dimungkinkan adalah karena hasil yang terkenal dari ketergantungan kurang dari kubik dalam jika m = n = p (ketika semua matriks adalah kotak).$p$$m=n=p$

Karya klasik Coppersmith menunjukkan bahwa untuk beberapa , seseorang dapat melipatgandakan matriks n × n α dengan matriks n α × n dalam$\alpha > 0$$n \times n^\alpha$$n^\alpha \times n$operasi aritmatika ˜ O (n2). Ini adalah unsur penting dari hasil baru-baru ini dirayakan oleh Ryan Williams.$\tilde{O}(n^2)$

François le Gall baru-baru ini memperbaiki karya Coppersmith, dan makalahnya baru saja diterima di FOCS 2012. Untuk memahami karya ini, Anda perlu pengetahuan tentang teori kompleksitas aljabar. Makalah Virginia Williams berisi beberapa petunjuk yang relevan. Secara khusus, karya Coppersmith sepenuhnya dijelaskan dalam Teori Kompleksitas Aljabar , buku itu.

Untaian pekerjaan yang berbeda berkonsentrasi pada mengalikan matriks kira-kira . Anda dapat memeriksa pekerjaan ini oleh Magen dan Zouzias. Ini berguna untuk menangani matriks yang sangat besar, katakanlah mengalikan sebuah matriks dan sebuah$n \times N$ , di mana N ≫ n .$N \times n$$N \gg n$

Pendekatan dasar adalah untuk mengambil sampel matriks (ini sesuai dengan pengurangan dimensi secara acak), dan mengalikan matriks sampel yang jauh lebih kecil. Kuncinya adalah mencari tahu kapan dan dalam arti apa ini memberikan perkiraan yang baik. Berbeda dengan alur kerja sebelumnya yang sama sekali tidak praktis, algoritma pengambilan sampel praktis dan bahkan diperlukan untuk menangani sejumlah besar data.