DAA - การคูณเมทริกซ์ของ Strassen

ในบทนี้ก่อนอื่นเราจะพูดถึงวิธีการทั่วไปของการคูณเมทริกซ์และต่อไปเราจะพูดถึงอัลกอริธึมการคูณเมทริกซ์ของ Strassen

คำชี้แจงปัญหา

ให้เราพิจารณาสองเมทริกซ์ X และ Y. เราต้องการคำนวณเมทริกซ์ผลลัพธ์Z โดยการคูณ X และ Y.

วิธีไร้เดียงสา

ขั้นแรกเราจะพูดถึงวิธีการที่ไร้เดียงสาและความซับซ้อนของมัน ที่นี่เรากำลังคำนวณZ = X × Y. ใช้วิธีNaïveสองเมทริกซ์ (X และ Y) สามารถคูณได้หากลำดับของเมทริกซ์เหล่านี้เป็น p × q และ q × 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]

ความซับซ้อน

ในที่นี้เราถือว่าการดำเนินการจำนวนเต็มใช้เวลา O(1)เวลา. มีสามตัวforลูปในอัลกอริทึมนี้และอีกอันหนึ่งซ้อนอยู่ ดังนั้นอัลกอริทึมจึงใช้เวลาO(n³) ถึงเวลาดำเนินการ

อัลกอริทึมการคูณเมทริกซ์ของ Strassen

ในบริบทนี้การใช้อัลกอริทึมการคูณเมทริกซ์ของ Strassen สามารถปรับปรุงการใช้เวลาได้เล็กน้อย

การคูณเมทริกซ์ของ Strassen สามารถทำได้เฉพาะบน square matrices ที่ไหน n คือ power of 2. ลำดับของเมทริกซ์ทั้งสองคือn × n.

การแบ่ง X, Y และ Z เป็นสี่ (n / 2) × (n / 2) เมทริกซ์ดังแสดงด้านล่าง -

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

การใช้อัลกอริทึมของ Strassen คำนวณดังต่อไปนี้ -

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

$$ M_ {2} \: \ โคลอน = (B + D) \ times (G + H) $$

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

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

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

$$ M_ {6} \: \ โคลอน = (A + B) \ times (H) $$

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

จากนั้น

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

$$ J \: \ colon = M_ {4} + M_ {6} $$

$$ K \: \ colon = M_ {5} + M_ {7} $$