Pengantar Komputasi Matrik
Komputasi Matrik telah menjadi dasar dalam berbagai komputasi sains. Salah satu komputasi matrik yang sangat penting adalah perkalian matrik. Beberapa bahasan komputasi matrik dalam kaitan dengan algoritma paralel akan kita bahas cukup banyak disini, diantaranya akan meliputi matrik transpos, perkalian matrik-vektor dan masalah konvolusi.
Algoritma perkalian matrik telah banyak digunakan diberbagai aplikasi sebagai salah satu komponen komputasinya, baik pada masalah numerik maupun non-numerik. Contoh non masalah non-numerik misalnya pada Teori Graph. Pada teori ini banyak menggunakan Perkalian Matrik Boolean.
Produk dari matrik A (p x q) dan matrik B (q x r) adalah matrik C (p x r) yang elemen-elemen nya didefinisikan sebagai berikut :
Untuk \( 0 \leq i \leq p-1 \) dan \( 0 \leq j \leq r-1 \) dimana \( \vee \) berarti operasi exclusice-OR dan \( \wedge \) adalah operasi AND bitwise.
Jika A dan B adalah matrik Boolean, maka matrik produk C juga akan berupa boolean matrik
Dalam komputasi serial, batas bawah dari kompleksitas perkalian matrik dengan dua matrik n x n diketahui sebesar Ω(n2), karena ada n2 elemen yang terlibat dalam menghasilkan matrik perkalian ini dan diperlukan waktu selama O(n2).
Dalam algoritma perkalian serial baik matrik pada umumnya maupun matrik boolean, akan membutuhkan O(n3) jika semua matrik yang terlibat berukuran n x n
Informasi ini bagus