DAA - Strassen'in Matris Çarpımı

Bu bölümde önce genel matris çarpma yöntemini, daha sonra Strassen'in matris çarpım algoritmasını tartışacağız.

Sorun bildirimi

İki matrisi düşünelim X ve Y. Ortaya çıkan matrisi hesaplamak istiyoruzZ çarparak X ve Y.

Naif Yöntem

İlk olarak, naif yöntemi ve karmaşıklığını tartışacağız. Burada hesaplıyoruzZ = X × Y. Naif yöntemini kullanarak, iki matris (X ve Y) bu matrislerin sırası p × q ve q × r. Algoritma aşağıdadır.

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]

Karmaşıklık

Burada, tamsayı işlemlerinin O(1)zaman. Üç vardırfordöngüler bu algoritmada ve biri diğerinin içindedir. Dolayısıyla, algoritmaO(n³) yürütme zamanı.

Strassen'in Matris Çarpma Algoritması

Bu bağlamda Strassen'in Matrix çarpma algoritması kullanılarak zaman tüketimi biraz iyileştirilebilir.

Strassen'in Matrix çarpımı yalnızca şu cihazlarda yapılabilir: square matrices nerede n bir power of 2. Her iki matrisin sırasın × n.

Böl X, Y ve Z aşağıda gösterildiği gibi dört (n / 2) × (n / 2) matrise -

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

Strassen Algoritmasını kullanarak aşağıdakileri hesaplayın -

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

$$ M_ {2} \: \ iki nokta = (B + D) \ times (G + H) $$

$$ M_ {3} \: \ iki nokta = (AD) \ times (E + H) $$

$$ M_ {4} \: \ iki nokta = A \ times (FH) $$

$$ M_ {5} \: \ iki nokta = (C + D) \ times (E) $$

$$ M_ {6} \: \ iki nokta = (A + B) \ times (H) $$

$$ M_ {7} \: \ iki nokta = D \ times (GE) $$

Sonra,

$$ I \: \ iki nokta üst üste = M_ {2} + M_ {3} - M_ {6} - M_ {7} $$

$$ J \: \ iki nokta = M_ {4} + M_ {6} $$

$$ K \: \ iki nokta = M_ {5} + M_ {7} $$