DAA - Perkalian Matriks Strassen

Pada bab ini, pertama kita akan membahas metode umum perkalian matriks dan selanjutnya kita akan membahas algoritma perkalian matriks Strassen.

Pernyataan masalah

Mari kita bahas dua matriks X dan Y. Kami ingin menghitung matriks resultanZ dengan mengalikan X dan Y.

Metode Naif

Pertama, kita akan membahas metode naif dan kompleksitasnya. Di sini, kami menghitungZ = X × Y. Menggunakan metode Naïve, dua matriks (X dan Y) dapat dikalikan jika urutan matriks ini adalah p × q dan q × r. Berikut algoritmanya.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Kompleksitas

Di sini, kami berasumsi bahwa operasi integer mengambil O(1)waktu. Ada tigaforloop dalam algoritma ini dan satu bersarang di yang lain. Karenanya, algoritme mengambilO(n³) waktu untuk mengeksekusi.

Algoritma Perkalian Matriks Strassen

Dalam konteks ini, dengan menggunakan algoritma perkalian Matriks Strassen, konsumsi waktu dapat sedikit ditingkatkan.

Perkalian Matriks Strassen hanya dapat dilakukan pada square matrices dimana n adalah power of 2. Urutan kedua matriks tersebut adalahn × n.

Membagi X, Y dan Z menjadi empat (n / 2) × (n / 2) matriks seperti yang ditunjukkan di bawah ini -

$ Z = \ begin {bmatrix} I & J \\ K & L \ end {bmatrix} $ $ X = \ begin {bmatrix} A & B \\ C & D \ end {bmatrix} $ dan $ Y = \ begin {bmatrix} E & F \\ G & H \ end {bmatrix} $

Menggunakan Algoritma Strassen menghitung yang berikut -

$$ M_ {1} \: \ titik dua = (A + C) \ times (E + F) $$

$$ M_ {2} \: \ titik dua = (B + D) \ kali (G + H) $$

$$ M_ {3} \: \ titik dua = (AD) \ kali (E + H) $$

$$ M_ {4} \: \ titik dua = A \ times (FH) $$

$$ M_ {5} \: \ titik dua = (C + D) \ times (E) $$

$$ M_ {6} \: \ titik dua = (A + B) \ times (H) $$

$$ M_ {7} \: \ titik dua = D \ times (GE) $$

Kemudian,

$$ I \: \ titik dua = M_ {2} + M_ {3} - M_ {6} - M_ {7} $$

$$ J \: \ titik dua = M_ {4} + M_ {6} $$

$$ K \: \ titik dua = M_ {5} + M_ {7} $$

$$ L \: \ titik dua = M_ {1} - M_ {3} - M_ {4} - M_ {5} $$

Analisis

$ T (n) = \ mulai {kasus} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & sebaliknya \ end {cases} $ di mana c dan d adalah konstanta

Menggunakan relasi perulangan ini, kita mendapatkan $ T (n) = O (n ^ {log7}) $

Oleh karena itu, kompleksitas algoritma perkalian matriks Strassen adalah $ O (n ^ {log7}) $.