Ma trận và những phép toán liên quan tới nó là một phần rất đặc biệt quan trọng trong hầu hết mọi thuật toán tương quan đến số học.Bạn sẽ xem: bí quyết nhân 2 ma trận vuông cấp 3

Ở bài bác trước, họ có kể tới việc áp dụng phép nhân ma trận nhằm tính số Fibonacci một giải pháp hiệu quả. Vậy thuật toán nhân ma trận mà họ sử dụng sinh hoạt trong nội dung bài viết đã thực sự hiệu quả hay chưa?

Trong vượt trình khám phá để viết bài xích này thì mình phát hiển thị một điều hơi là thú vị, kia là có không ít thuật toán để tiến hành nhân ma trận, tuy nhiên ngành khoa học máy vi tính vẫn chưa tìm ra được câu trả lời cho câu hỏi: Đâu là thuật toán về tối ưu để triển khai phép nhân ma trận?

Định nghĩa phép Nhân ma trận

Nhắc lại một chút kỹ năng toán học tập về phương pháp nhân 2 ma trận $A$ cùng $B$, điều kiện đầu tiên để hoàn toàn có thể thực hiện nay phép nhân này là khi số cột của ma trận $A$ ngay số hàng của ma trận $B$.

Bạn đang xem: Thuật toán nhân 2 ma trận

Với $A$ là một trong ma trận có size $n imes m$ với $B$ là 1 trong ma trận kích cỡ $m imes p$ thì tích của $A imes B$ sẽ là một ma trận $n imes p$ được tính bằng phương pháp sau:

$$left( eginarrayccca và b \c và d endarray ight) imesleft( eginarraycccx \yendarray ight)=left( eginarraycccax + by \cx + dyendarray ight)$$Hình sau tế bào tả biện pháp tính một trong những phần tử AB của ma trận tích:


*

Một thành phần là tổng của phép nhân các phần tử trong một hàng của ma trận $A$ với các phần tử trong cột tương xứng trong ma trận $B$

$$_i,j = A_i,1B_1,j + A_i,2B_2,j + ldots + A_i,nB_n,j$$Hay viết cho gọn hơn hoàn toàn như sau:

$$_i,j = displaystylesum_r=1^n A_i,rB_r,j$$Noob Question: mẫu dấu hình zích zắc $sum$ tê là gì vậy???

Chửi trước: Ôi trời, đây là cái vết tính tổng mà lại cũng lần chần à? Về học tập lại toán cấp cho 3 tốt năm duy nhất ĐH nào đó đi nhé! Tốn thời gian bm!!Đáp sau: chiếc dấu zích zắc sẽ là kí hiệu phép tính tổng, hoàn toàn có thể hình dung kí hiệu này y hệt như một vòng lặp for trong thực hiện phép tính cộng, số $n$ làm việc trên đỉnh chỉ tổng số lần lặp đề xuất thiết, số $r = 1$ làm việc dưới mang đến ta biết giá trị nào nên chạy trong tầm lặp for và bước đầu chạy từ giá trị bao nhiêu. Biểu thức kèm theo sau kí hiệu $sum$ mang lại ta biết phép cộng các giá trị nào sẽ được thực hiện bên trong vòng lặp đó.Tiếp theo, hãy thuộc xem họ có các cách nào để implement thuật toán này trên trang bị tính.

The naive algorithm

Naive Algorithm là từ dùng làm chỉ một thuật toán đơn giản dễ dàng nhất được tư duy một phương pháp "ngây thơ" bằng phương pháp xử lý thông thường, ví như tìm kiếm tuần trường đoản cú (sequential/linear search)

Trong trường hợp này, bọn họ thường implement thuật toán nhân ma trận bằng phương pháp áp dụng đúng đắn công thức từ khái niệm toán học tập của nó, áp dụng vòng lặp, như sau:

Input: nhì ma trận A kích cỡ $n imes m$ và B kích thước $m imes p$

1: Khởi sinh sản ma trận C có kích cỡ $n imes p$ 2: For i từ $1 ightarrow n$:3: For j từ bỏ $1 ightarrow p$:4: Gán $sum = 0$5: For r trường đoản cú $1 ightarrow m$:6: Gán $sum = sum + A_i,r imes B_r,j$7: Gán $C_i,j = sum$

Output: Ma trận C size $n imes p$

Tại sao lại hotline là naive algorithm (ngây thơ)? đó nguyên nhân là nó rất giản đơn implement, chỉ việc đi theo lối quan tâm đến thông thường, bỏ lỡ hết đông đảo yếu tố như độ phức tạp, sự buổi tối ưu...

Độ tinh vi của thuật toán trên là $mathcalO(nmp)$, trong trường hợp tất cả các ma trận mọi là ma trận vuông $n imes n$ thì độ phức hợp của thuật toán đã là $mathcalO(n^3)$

Chia nhằm trị - Thuật toán Strassen

Vào năm 1969, Volker Strassen - dịp đó đang là sinh viên tại MIT - cho rằng $mathcalO(n^3)$ chưa phải là số lượng tối ưu cho phép nhân ma trận, và khuyến cáo một thuật toán new có thời gian chạy chỉ cấp tốc hơn một chút ít nhưng về sau đã kéo theo rất nhiều nhà khoa học xả thân tiếp tục phân tích và cho đến thời điểm bây giờ, đã gồm rất nhiều cách thức mới được đưa ra như là thuật toán Coppersmith-Winograd (sẽ nói tại vị trí sau), hoặc các phương án tiếp cận bởi lập trình tuy nhiên song trên những máy tính/nhiều core,... Điểm độc đáo là Strassen nghĩ ra thuật toán này vì chưng nó là bài tập trong một lớp mà ông sẽ học .

Xét lại thuật toán naive ở chỗ trước, để tính 1 phần tử $C_i,j$ của ma trận tích $C$, ta phải triển khai hai phép nhân với một phép cộng. Suy ra giả dụ $C$ là 1 ma trận vuông có kích thước $2 imes 2$, thì nhằm tính bốn phần tử của $C$, yên cầu phải triển khai $2 imes 2^2 = 2^3 = 8$ phép nhân với $(2 - 1) imes 2^2 = 4$ phép cộng. Nếu $A$ và $B$ là rất nhiều ma trận cấp cho $n$ (tức là những ma trận $n imes n$) thì họ cần phải tiến hành $n^3$ phép nhân với $(n - 1) imes n^2$ phép cộng.

Ý tưởng thuật toán của Strassen là áp dụng chia để trị để xử lý bài toán theo phía của giải thuật cơ bản trên. Ví dụ là: với từng ma trận vuông A, B, C có kích cỡ $n imes n$, họ chia bọn chúng thành 4 ma trận con, và biểu diễn tích $A imes B = C$ theo các ma trận nhỏ đó:


*

Trong đó:

Chúng ta có mang ra các ma trận $M$ new như sau:

$$eginalignM_1 & = (A_1,1 + A_2,2)(B_1,1 + B_2,2) \M_2 và = (A_2,1 + A_2,2) B_1,1 \M_3 và = A_1,1 (B_1,2 - B_2,2) \M_4 & = A_2,2 (B_2,1 - B_1,1) \M_5 và = (A_1,1 + A_1,2) B_2,2 \M_6 và = (A_2,1 - A_1,1)(B_1,1 + B_1,2) \M_7 & = (A_1,2 - A_2,2)(B_2,1 + B_2,2)endalign$$Và trình diễn lại các bộ phận của $C$ theo $M$ như sau:

$$eginalignC_1,1 & = M_1 + M_4 - M_5 + M_7 \C_1,2 và = M_3 + M_5 \ C_2,1 & = M_2 + M_4 \C_2,2 và = M_1 - M_2 + M_3 + M_6endalign$$Bằng biện pháp này, họ chỉ phải 7 phép nhân (mỗi $M$ một phép nhân) thay vì chưng 8 như phương pháp cũ.

Thực hiện tại đệ quy quá trình trên cho đến khi ma trận gồm cấp hai.

Độ phức hợp của thuật toán Strassen là $mathcalO(n^log7) approx mathcalO(n^2.807)$

Đồ thị sau đối chiếu sự khác nhau về độ phức tạp của hai thuật toán vừa bàn:


*

Coppersmith-Winograd Algorithm và các thuật toán cải tiến

Dựa trên phát minh của Strassen, trong thời điểm tháng 5/1987, nhị nhà công nghệ Don Coppersmith với Shmuel Winograd công bố bài báo Matrix Multiplication via Arithmetic Progression reviews một phương thức mới nhằm tăng vận tốc nhân ma trận và cho biết độ phức hợp của thuật toán mà họ phát triển là $mathcalO(n^2.376)$ cùng được review là thuật toán nhân ma trận nhanh nhất tính tới thời điểm đó.


*

Vào mon 3/2013, A. M. Davie và A. J. Stothers chào làng bài báo Improved bound for complexity of matrix multiplication và cho thấy thêm họ để được con số $mathcalO(n^2.37369)$ khi cách tân và khảo sát thuật toán của Coppersmith-Winograd.

Tháng 1/2014, François Le Gall chào làng bài báo Powers of Tensors và Fast Matrix Multiplication liên tục phân tích thuật toán của hai nhà khoa học này với đạt được con số $mathcalO(n^2.3728639)$.

Vào mon 7/2014, Virginia Vassilevska Williams thuộc đại học Standford chào làng bài báo Multiplying matrices in $mathcalO(n^2.373)$ time giới thiệu phương pháp đổi mới thuật toán của Coppersmith-Winograd và chào làng độ phức hợp là $mathcalO(n^2.372873)$.

Kết luận

Tổng kết lại, với những thuật toán hiện tại tại, chúng ta rút ra được bảng so sánh về độ tinh vi như sau:

Thuật toánInputĐộ phức tạp
Naive AlgorithmMa trận vuông$O(n^3)$
Naive AlgorithmMa trận bất kì$O(nmp)$
Strassen AlgorithmMa trận vuông$O(n^2.807)$
Coppersmith-Winograd AlgorithmMa trận vuông$O(n^2.376)$
Các thuật toán CW cải tiếnMa trận vuông$O(n^2.373)$

Và những nhà công nghệ vẫn đã miệt mài nghiên cứu để lấy con số này về $mathcalO(n^2)$


*

Theo một bình luận của giáo sư Ngô quang Hưng bên trên Procul, thì các thuật toán của Strassen và Coppersmith-Winograd chỉ với giá trị kim chỉ nan là chính, trong thực tế ít ai dùng cho các ma trận phệ vì hidden-constant quá lớn và implement phức tạp, dễ dẫn đến lỗi .

Xem thêm: Tuyển Tập 80+ Đề Thi Thử Tốt Nghiệp Thpt Môn Anh 2022 Có Đáp Án

Cảm ơn các bạn đã theo dõi bài xích viết! các chúng ta cũng có thể follow bản thân trên Facebook để đặt câu hỏi, hoặc nhận thông tin về các nội dung bài viết mới.