Ma trận cùng các phnghiền toán tương quan tới nó là một phần khôn xiết đặc trưng trong phần lớn đa số thuật toán thù liên quan cho số học tập.

Bạn đang xem: Cách nhân 2 ma trận vuông cấp 3

Ở bài trước, chúng ta tất cả đề cập tới việc vận dụng phnghiền nhân ma trận nhằm tính số Fibonacci một biện pháp công dụng. Vậy thuật tân oán nhân ma trận cơ mà họ thực hiện ngơi nghỉ trong nội dung bài viết đang đích thực tác dụng tốt chưa?


Trong quá trình khám phá để viết bài này thì bản thân phạt hiện ra một điều khá là thú vui, đó là có nhiều thuật tân oán để thực hiện nhân ma trận, tuy nhiên ngành công nghệ máy vi tính vẫn không tìm ra được câu trả lời mang đến câu hỏi: Đâu là thuật toán thù về tối ưu để thực hiện phép nhân ma trận? <1>

Định nghĩa phnghiền Nhân ma trận

Nhắc lại một ít kỹ năng và kiến thức tân oán học tập về phương pháp nhân 2 ma trận $A$ với $B$, điều kiện trước tiên để rất có thể triển khai phxay nhân này là Lúc số cột của ma trận $A$ bằng số sản phẩm của ma trận $B$.

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

$$left( eginarrayccca & b \c và d endarray ight) imesleft( eginarraycccx \yendarray ight)=left( eginarraycccax + by \cx + dyendarray ight)$$Hình sau diễn đạt phương pháp tính 1 phần tử AB của ma trận tích:

*

Một bộ phận là tổng của phnghiền nhân các phần tử trong một hàng của ma trận $A$ cùng với những thành phần vào cột tương xứng vào 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 đến gọn gàng hơn như sau:

$$_i,j = displaystylesum_r=1^n A_i,rB_r,j$$
Noob Question: Cái lốt 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 nhưng cũng không biết à? Về học tập lại toán cấp 3 tuyệt năm duy nhất ĐH nào đấy đi nhé! Tốn thời gian bm!!Đáp sau: Cái vệt zích zắc đó là kí hiệu phép tính tổng, rất có thể hình dung kí hiệu này y như một vòng lặp for vào thực hiện phxay tính cùng, số $n$ ở trên đỉnh chỉ tổng mốc giới hạn lặp quan trọng, số $r = 1$ sinh sống dưới mang lại ta biết quý giá làm sao bắt buộc chạy trong tầm lặp for với ban đầu chạy từ cực hiếm từng nào. Biểu thức kèm theo sau kí hiệu $sum$ mang lại ta biết phxay cùng những cực hiếm như thế nào sẽ được thực hiện bên phía trong vòng lặp đó.
Tiếp theo, hãy cùng xem chúng ta tất cả các cách làm sao để implement thuật tân oán này trên máy vi tính.

The naive algorithm

Naive sầu Algorithm là tự dùng để có một thuật tân oán đơn giản duy nhất được tư duy một biện pháp "ntạo thơ" bằng cách giải pháp xử lý thông thường, ví dụ như kiếm tìm tìm tuần tự (sequential/linear search)

Trong ngôi trường thích hợp này, chúng ta hay implement thuật toán thù nhân ma trận bằng cách áp dụng đúng chuẩn phương pháp trường đoản cú định nghĩa toán thù học của chính nó, áp dụng vòng lặp, nhỏng sau:


Input: Hai ma trận A kích cỡ $n imes m$ cùng B size $m imes p$

1: Khởi tạo nên ma trận C tất cả form size $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 kích thước $n imes p$


Tại sao lại Gọi là naive algorithm (ngây thơ)? đó nguyên nhân là nó rất dễ dàng implement, chỉ việc theo lối quan tâm đến thường thì, bỏ qua không còn hồ hết nhân tố như độ tinh vi, sự buổi tối ưu...

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

Chia để trị - Thuật toán thù Strassen

Vào năm 1969, Volker Strassen - cơ hội đó đang là sinc viên tại MIT - cho rằng $mathcalO(n^3)$ chưa phải là số lượng tối ưu chất nhận được nhân ma trận, và khuyến cáo một thuật tân oán mới bao gồm thời gian chạy chỉ nkhô hanh rộng một chút tuy vậy sau đây đã nâng theo không ít công ty kỹ thuật lao vào liên tiếp nghiên cứu và phân tích với cho tới thời khắc bây giờ, vẫn có khá nhiều cách thức bắt đầu được đưa ra như thể thuật toán Coppersmith-Winograd (vẫn nói ở chỗ sau), hoặc các chiến thuật tiếp cận bằng lập trình tuy nhiên tuy vậy trên nhiều sản phẩm tính/những core,... Điểm thú vui là Strassen nghĩ ra thuật tân oán này do nó là bài xích tập trong một tấm nhưng ông vẫn học <2>.

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

Ý tưởng thuật toán thù của Strassen <3> là áp dụng phân chia nhằm trị nhằm giải quyết bài toán thù theo hướng của giải thuật cơ bạn dạng trên. Cụ thể là: với mỗi ma trận vuông A, B, C gồm kích cỡ $n imes n$, họ phân chia bọn chúng thành 4 ma trận bé, cùng màn trình diễn tích $A imes B = C$ theo các ma trận nhỏ đó:

*

Trong đó:

$$eginalignC_1,1 & = A_1,1B_1,1 + A_1,2B_2,1 \C_1,2 & = A_1,1B_1,2 + A_1,2B_2,2 \C_2,1 & = A_2,1B_1,1 + A_2,2B_2,1 \C_2,2 và = A_2,1B_1,2 + A_2,2B_2,2 endalign$$Tuy nhiên cùng với bí quyết so sánh này thì chúng ta vẫn nên 8 phép nhân nhằm tính ra ma trận $C$. Đây là phần đặc trưng độc nhất vô nhị của vấn đề.

Xem thêm: 10/10 Là Ngày 10 Tháng 10 Là Ngày Gì ? Ngày 10/10 Là Ngày Gì

Chúng ta có mang ra những ma trận $M$ new nlỗi sau:

$$eginalignM_1 và = (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 và = 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à màn trình diễn lại những bộ phận của $C$ theo $M$ nlỗi sau:

$$eginalignC_1,1 & = M_1 + M_4 - M_5 + M_7 \C_1,2 & = M_3 + M_5 \ C_2,1 & = M_2 + M_4 \C_2,2 & = M_1 - M_2 + M_3 + M_6endalign$$Bằng cách này, chúng ta chỉ cần 7 phép nhân (mỗi $M$ một phxay nhân) cố kỉnh bởi 8 như phương pháp cũ.

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

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

Đồ thị sau so sánh sự khác biệt về độ phức hợp của nhị thuật toán vừa bàn:

*

Coppersmith-Winograd Algorithm cùng những thuật toán cải tiến

Dựa bên trên phát minh của Strassen, trong thời điểm tháng 5/1987, hai nhà kỹ thuật Don Coppersmith và Shmuel Winograd công bố bài xích báo Matrix Multiplication via Arithmetic Progression <4> ra mắt một phương thức mới nhằm tăng tốc độ nhân ma trận và cho thấy độ phức hợp của thuật toán thù mà họ phát triển là $mathcalO(n^2.376)$ với được reviews là thuật toán nhân ma trận nkhô hanh tốt nhất tính cho tới thời đặc điểm đó.

*

Vào mon 3/2013, A. M. Davie và A. J. Stothers ra mắt bài bác báo Improved bound for complexity of matrix multiplication <5> và cho biết thêm bọn họ đặt được số lượng $mathcalO(n^2.37369)$ Khi đổi mới với khảo sát thuật tân oán của Coppersmith-Winograd.

Tháng 1/năm trước, François Le Gall ra mắt bài bác báo Powers of Tensors and Fast Matrix Multiplication <6> liên tiếp phân tích thuật toán thù của nhị công ty công nghệ này và đã đạt được số lượng $mathcalO(n^2.3728639)$.

Vào mon 7/2014, Virginia Vassilevska Williams trực thuộc đại học Standford ra mắt bài bác báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> đưa ra phương thức cách tân thuật tân oán của Coppersmith-Winograd với công bố độ tinh vi là $mathcalO(n^2.372873)$.

Kết luận

Tổng đặc lại, với các thuật toán hiện thời, họ rút ra được bảng so sánh về độ tinh vi nhỏng sau:

Thuật toánInputĐộ phức tạp
Naive sầu 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 tân oán CW cải tiếnMa trận vuông$O(n^2.373)$

Và các bên công nghệ vẫn đang mải mê phân tích để lấy số lượng này về $mathcalO(n^2)$

*

Theo một comment của GS Ngô Quang Hưng trên Procul, thì những thuật toán của Strassen và Coppersmith-Winograd chỉ có giá trị lý thuyết là chính, vào thực tế không nhiều người cần sử dụng cho những ma trận béo vì chưng hidden-constant quá to với implement phức hợp, dễ dẫn đến lỗi <8>.


Cảm ơn bạn đang quan sát và theo dõi bài xích viết! những bạn cũng có thể follow mình trên Facebook để tại vị câu hỏi, hoặc dấn công bố về các bài viết mới.