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(n3) 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} $$

$$ L \: \ iki nokta = M_ {1} - M_ {3} - M_ {4} - M_ {5} $$

Analiz

$ T (n) = \ begin {case} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & aksi \ end {case} $ burada c ve d sabitler

Bu tekrarlama ilişkisini kullanarak $ T (n) = O (n ^ {log7}) $ elde ederiz

Dolayısıyla, Strassen'in matris çarpım algoritmasının karmaşıklığı $ O (n ^ {log7}) $ şeklindedir.