Thuật toán **Strassen** nhân ma trận 2x2 chỉ dùng **7 phép nhân** thay vì 8 phép nhân thông thường, dựa trên kỹ thuật **Chia để trị (Divide and Conquer)**.
Cho 2 ma trận 2x2:
A = [a b] B = [e f]
[c d] [g h]
7 tích trung gian (M1..M7) được tính như sau:
M1 = a * (f - h) M2 = (a + b) * h M3 = (c + d) * e M4 = d * (g - e) M5 = (a + d) * (e + h) // Nhân đường chéo chính M6 = (b - d) * (g + h) // Cột cuối A, hàng cuối B M7 = (a - c) * (e + f) // Cột đầu A, hàng đầu B
Kết quả ma trận C = A x B:
C11 = M5 + M4 - M2 + M6 C12 = M1 + M2 C21 = M3 + M4 C22 = M5 + M1 - M3 - M7
Kỹ thuật ghi nhớ "AHED" (Mnemonic)
Để nhớ 7 công thức M1..M7, hãy nhớ từ khóa: **AHED** (A Head - Đầu A) + **Đường chéo** + **CR (Column-Row)**.
- A H E D (4 công thức đầu dùng A, H, E, D làm "chân" chính):
- M1 = A * (F - H) <-- Chứa A, H
- M2 = (A + B) * H <-- Chứa H
- M3 = (C + D) * E <-- Chứa E
- M4 = D * (G - E) <-- Chứa D, E
- M5 (Đường chéo chính): (A + D) * (E + H). Cộng 2 đường chéo chính của A và B.
- M6 (Last CR - Cột cuối, Hàng cuối): (B - D) * (G + H). Cột 2 của A (B, D), Hàng 2 của B (G, H). Dấu trừ ở A, cộng ở B.
- M7 (First CR - Cột đầu, Hàng đầu): (A - C) * (E + F). Cột 1 của A (A, C), Hàng 1 của B (E, F). Dấu trừ ở A, cộng ở B.
Quy tắc dấu "Hàng Cộng, Cột Trừ"
- Khi cộng các phần tử cùng **hàng** (Row): Dùng dấu + (Ví dụ: A+B, C+D, E+F, G+H).
- Khi trừ các phần tử cùng **cột** (Column): Dùng dấu - (Ví dụ: F-H, G-E, B-D, A-C).
Chương trình minh họa nhân ma trận Strassen (Đệ quy)
#include <bits/stdc++.h>
using namespace std;
using Matrix = vector<vector<long long>>;
Matrix add(const Matrix &A, const Matrix &B) {
int n = A.size(); Matrix C(n, vector<long long>(n));
for(int i=0;i
Đầu ra
19 22
43 50