Algoritma Strassen

Algoritma Strassen

Algoritma Strassen merupakan sebuah algoritma yang digunakan untuk perkalian matriks yang secara asimtot lebih cepat dari pada algoritma perkalian matriks standar dan sangat berguna untuk penggunaan matriks berukuran besar.

Perkalian matriks standar melakukan n3=nlog28 sedangkan Algoritma Strassen nlog27.

Misal kita memiliki

 

dimana C = AB

maka proses perkalian matriks standar adalah

C1,1 = A1,1 * B1,1 + A1,2 * B2,1

C1,2 = A1,1 * B1,2 + A1,2 * B2,2

C2,1 = A2,1 * B1,1 + A2,2 * B2,1

C2,2 = A2,1 * B1,2 + A2,2 * B2,2

Sedangkan dengan menggunakan Algoritma Strassen dilakukan perhitungan berikut

P1 = (A1,1 + A2,2) * (B1,1 + B2,2)

P2 = (A2,1 + A2,2) * B1,1

P3 = A1,1 * (B1,2 – B2,2)

P4 = A2,2 * (B2,1 – B1,1)

P5 = (A1,1 + A1,2) * B2,2

P6 = (A2,1 – A1,1) * (B1,1 + B1,2)

P7 = (A1,2 – A2,2) * (B2,1 + B2,2)

C1,1 = P1 + P4 – P5 + P7

C1,2 = P3 + P5

C2,1 = P2 + P4

C2,2 = P1 – P2 + P3 + P6

Download