DAA - Phép nhân ma trận Strassen

Trong chương này, đầu tiên chúng ta sẽ thảo luận về phương pháp tổng quát của phép nhân ma trận và sau đó chúng ta sẽ thảo luận về thuật toán nhân ma trận của Strassen.

Báo cáo vấn đề

Chúng ta hãy xem xét hai ma trận X và Y. Chúng tôi muốn tính toán ma trận kết quảZ bằng cách nhân X và Y.

Phương pháp ngây thơ

Đầu tiên, chúng ta sẽ thảo luận về phương pháp ngây thơ và sự phức tạp của nó. Ở đây, chúng tôi đang tính toánZ = X × Y. Sử dụng phương pháp Naïve, hai ma trận (X và Y) có thể được nhân lên nếu thứ tự của các ma trận này là p × q và q × r. Sau đây là thuật toán.

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]

Phức tạp

Ở đây, chúng tôi giả định rằng các phép toán số nguyên có O(1)thời gian. Có baforvòng lặp trong thuật toán này và một vòng lặp được lồng trong thuật toán khác. Do đó, thuật toán mấtO(n³) thời gian để thực hiện.

Thuật toán nhân ma trận của Strassen

Trong bối cảnh này, sử dụng thuật toán nhân Ma trận của Strassen, mức tiêu thụ thời gian có thể được cải thiện một chút.

Phép nhân Ma trận Strassen chỉ có thể được thực hiện trên square matrices Ở đâu n là một power of 2. Thứ tự của cả hai ma trận làn × n.

Chia X, Y và Z thành bốn (n / 2) × (n / 2) ma trận như được biểu diễn dưới đây -

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

Sử dụng Thuật toán Strassen tính toán những điều sau:

$$ M_ {1} \: \ dấu hai chấm = (A + C) \ times (E + F) $$

$$ M_ {2} \: \ dấu hai chấm = (B + D) \ times (G + H) $$

$$ M_ {3} \: \ dấu hai chấm = (AD) \ times (E + H) $$

$$ M_ {4} \: \ dấu hai chấm = A \ times (FH) $$

$$ M_ {5} \: \ dấu hai chấm = (C + D) \ times (E) $$

$$ M_ {6} \: \ dấu hai chấm = (A + B) \ times (H) $$

$$ M_ {7} \: \ dấu hai chấm = D \ times (GE) $$

Sau đó,

$$ I \: \ dấu hai chấm = M_ {2} + M_ {3} - M_ {6} - M_ {7} $$

$$ J \: \ dấu hai chấm = M_ {4} + M_ {6} $$

$$ K \: \ dấu hai chấm = M_ {5} + M_ {7} $$