Thuật toán nhân 2 ma trận

Cho hai ma trận A, B với kích thước n*n, ta có ma trận C chứa kết quả của phép nhân hai ma trận A và B. Thuật toán nhân ma trận cổ điển như công thức dưới đây:

Với mảng một chiều (kích thước n phần tử), ma trận C được tính trong thời gian (n), giả sử rằng phép cộng vô hướng và phép nhân là các phép tính cơ bản (có thời gian tính là hằng số). Với mảng hai chiểu (kích thước n*n) thì thời gian để tính phép nhân ma trận AB là (n).

Đến cuối những năm 1960, Strassen đưa ra một giải pháp cải tiến thuật toán trên, nó có tính đột phá trong lịch sử của thuật toán chia để trị, thậm chí gây ngạc nhiên không kém thuật toán nhân số nguyên lớn được phát minh ở thập kỷ trước. ý tưởng cơ bản của thuật toán Strassen cũng tương tự như thuật toán trên. Ứng dụng thiết kế chia để trị, mỗi ma trận A, B, C ta chia thành 4 ma trận con và biểu diễn tích 2 ma trận AxB = C theo các ma trận con đó:

Trong đó :

C₁₁ = A₁₁B₁₁ + A₁₂B₂₁

C₁₂ = A₁₁B₁₂ + A₁₂B₂₂

C₂₁ = A₂₁B₁₁ + A₂₂B₂₁

C₂₂ = A₂₁B₁₂ + A₂₂B₂₂

Nếu theo cách nhân thông thường, thì cách chia để trị này dẫn đến công hưc truy hồi : T(n) = 8T(n/2) + O(n²). Đáng tiếc là kết quả này cho lời giải T(n) thuộc O(n³)

Nhưng theo khám phá của Strassen, chỉ cần 7 phép nhân đệ qui n/2x n/2 ma trận và O(n²) phép cộng trừ vô hướng theo công thức truy hồi :

T(n) = 7T(n/2) + 18 (n/2)² € O(n^lg7 ) = O(n^2.81)

Cụ thể, để nhân 2 ma trận vuông cấp 2 , theo Strassen chỉ cần 7 phép nhân và 18 phép cộng (trừ) các sô. Để tính :

- Đầu tiên tính 7 tích :

m₁ = (a₁₂ - a₂₂ ) (b₂₁ + b₂₂ )

m₂ = (a₁₁ + a₂₂ ) (b₁₁ + b₂₂ )

m₃ = (a₁₁ - a₂₁ ) (b₁₁ + b₁₂ )

m₄ = (a₁₁ + a₁₂ ) b₂₂

m₅ = a₁₁ (b₁₂ – b₂₂ )

m₆ = a₂₂ (b₂₁ – b₁₁ )

m₇ = (a₂₁ + a₂₂ ) b₁₁

- sau đó tính c_ij theo công thức :

c₁₁ = m₁ + m₂ – m₄ + m₆

c₁₂ = m₄ + m₅

c₂₁ = m₆ + m₇

c₂₂ = m₂ – m₃ + m₅ – m₇

Mô tả thuật toán:

strass(a, b, c, n)

if ( n == 2 ) nhan2(a,b,c);

else

{

tach(a,a11,a12,a21,a22,n);

tach(b,b11,b12,b21,b22,n);

tach(c,c11,c12,c21,c22,n);

strass(a11,b11,d1,n/2);

strass(a12,b21,d2,n/2);

cong(d1,d2,c11,n/2);

strass(a11,b12,d1,n/2);

strass(a12,b22,d2,n/2);

cong(d1,d2,c12,n/2);

strass(a21,b11,d1,n/2);

strass(a22,b21,d2,n/2);

cong(d1,d2,c21,n/2);

strass(a21,b12,d1,n/2);

strass(a22,b22,d2,n/2);

cong(d1,d2,c22,n/2);

Hop(c11,c12,c21,c22,c,n);

}

Cùng với phát minh của Strassen, có một số nhà nghiên cứu cố gắng tìm kiếm thuật toán để xác định được hằng số ω, khi đó độ phức tạp tính toán phép nhân hai ma trận kích thước n*n là O(n^w). Để thực hiện được điều này, việc đầu tiên phải tiến hành là nhân hai ma trận kích thước 2*2 với 6 phép nhân cơ bản. Nhưng vào năm 1971 Hopcroft và Kerr đã chứng minh điều này là không thể vì phép nhân hai ma trận không có tính chất giao hoán. Việc tiếp theo phải thực hiện là tìm cách nào để nhân hai ma trận 3*3 với nhiều nhất chỉ 21 phép nhân cơ bản. Nếu thực hiện được việc này có thể sử dụng thuật toán này để suy ra thuật toán đệ quy nhân hai ma trận n*n với thời gian là O(n^log₃²¹) nhanh hơn thuật toán của Strassen vì log₃21<log₂7. Không may mắn là điều này không thể thực hiện. Trong suốt một thập kỷ trước khi Pan phát hiện ra cách để nhân hai ma trân kích thước 70*70 vớI 143640 phép nhân cơ bản – so sánh với 343000 phép nhân nếu sử dụng thuật toán cổ điển và quả thực là log₇₀143640 bé hơn một chút so vớI lg7. Phát hiện này được gọi là cuộc chiến tranh của số thập phân (decimal war). Nhiều thuật toán, mà trong đó hiệu suất tiệm cận cao, được tìm ra sau đó. Ví dụ như ta đã biết cuốI năm 1979, phép nhân ma trận có thời gian tính toán là O(n^2525813). Hãy tưởng tượng rằng, ngay sau đó tháng 1 năm 1980 thờI gian tính của phép nhân ma trận là O(n^2525813). Biểu thức tiệm cận thời gian tính toán tồi nhất của thuật toán nhân ma trận kích thước n*n được Coppersmith và Winograd phát minh ra năm 1986 là O(n²³⁷⁶). Tại vì các hằng số liên quan bị ẩn nên không một thuật toán nào được tìm ra sau thuật toán của Strassen được nghiên cứu và sử dụng.