เทคนิคจำสูตร Strassen's Matrix Multiplication ใน C++

Strassen's Algorithm

อัลกอริธึมคูณเมทริกซ์แบบ Divide and Conquer ลดการคูณจาก 8 ครั้งเหลือ 7 ครั้ง

สูตร M1-M7

M1 = a × (f - h)
M2 = (a + b) × h
M3 = (c + d) × e
M4 = d × (g - e)
M5 = (a + d) × (e + h)      // Diagonal
M6 = (b - d) × (g + h)      // Last Column × Last Row
M7 = (a - c) × (e + f)      // First Column × First Row

กฎจำง่าย (AHED Rule)

1. ใช้ AHED สำหรับ M1-M4 (A,H,E,D คือตำแหน่งในเมทริกซ์)
2. M5: Diagonal multiplication (a+d)×(e+h)
3. M6: Last CR (Last Column of A × Last Row of B)
4. M7: First CR (First Column of A × First Row of B)
5. แถว: บวกกัน, คอลัมน์: ลบกัน
6. อัปเดตค่าโดยใช้ค่าที่อยู่ติดกัน