CÁCH NHÂN HAI MA TRẬN

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

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

Trong vượt trình tìm hiểu để viết bài xích này thì mình phát chỉ ra một điều khá là thú vị, đó là có tương đối nhiều thuật toán để triển khai 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 vấn đáp cho câu hỏi: Đâu là thuật toán buổi tối ưu để thực hiện 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 kiến thức và kỹ năng toán học về cách thức nhân 2 ma trận $A$ với $B$, điều kiện thứ nhất để 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$ thông qua số hàng của ma trận $B$.

Bạn đang xem: Cách nhân hai ma trận

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

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


*

Một phần tử là tổng của phép nhân các bộ phận trong một hàng của ma trận $A$ cùng với các thành phần trong cột khớp ứ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 mang lại gọn hơn như sau:

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

Chửi trước: Ôi trời, đó là cái vết tính tổng cơ mà cũng không biết à? Về học tập lại toán cấp 3 xuất xắc năm duy nhất ĐH gì đó đi nhé! Tốn thời gian bm!!Đáp sau: chiếc dấu zích zắc chính là kí hiệu phép tính tổng, hoàn toàn có thể hình dung kí hiệu này giống hệt như một vòng lặp for trong triển khai phép tính cộng, số $n$ ngơi nghỉ trên đỉnh chỉ tổng chu kỳ lặp đề xuất thiết, số $r = 1$ ở dưới đến ta biết cực hiếm nào buộc phải chạy trong khoảng lặp for và bước đầu chạy từ cực hiếm bao nhiêu. Biểu thức đi liền sau kí hiệu $sum$ mang lại ta biết phép cộng những giá trị nào sẽ được thực hiện bên phía 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 đồ vật tính.

The naive algorithm

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

Trong trường vừa lòng này, chúng ta thường implement thuật toán nhân ma trận bằng cách áp dụng đúng mực công thức từ tư tưởng toán học tập của nó, sử dụng vòng lặp, như sau:

Input: nhị ma trận A size $n imes m$ cùng B size $m imes p$

1: Khởi chế tác ma trận C có size $n imes p$ 2: For i từ $1 ightarrow n$:3: For j trường đoản cú $1 ightarrow p$:4: Gán $sum = 0$5: For r từ $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ơ)? đó bởi vì nó rất dễ implement, chỉ việc đi theo lối để ý đến thông thường, làm lơ hết phần nhiều yếu tố như độ phức tạp, sự về 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 hầu như là ma trận vuông $n imes n$ thì độ phức tạp của thuật toán đang là $mathcalO(n^3)$

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

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

Xét lại thuật toán naive tại đoạn trước, để tính một trong những 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 cùng một phép cộng. Suy ra trường hợp $C$ là một ma trận vuông có kích thước $2 imes 2$, thì nhằm tính bốn bộ phận của $C$, yên cầu phải tiến hành $2 imes 2^2 = 2^3 = 8$ phép nhân cùng $(2 - 1) imes 2^2 = 4$ phép cộng. Trường hợp $A$ cùng $B$ là đều ma trận cung cấp $n$ (tức là những ma trận $n imes n$) thì chúng ta cần phải thực hiện $n^3$ phép nhân và $(n - 1) imes n^2$ phép cộng.

Ý tưởng thuật toán của Strassen là vận dụng chia nhằm trị để giải quyết bài toán theo hướng 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ó size $n imes n$, chúng ta chia bọn chúng thành 4 ma trận con, và màn trình diễn tích $A imes B = C$ theo các ma trận con đó:


*

Trong đó:

Chúng ta có mang ra những 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 và = (A_1,2 - A_2,2)(B_2,1 + B_2,2)endalign$$Và màn trình diễn lại các bộ phận của $C$ theo $M$ như sau:

$$eginalignC_1,1 và = 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 phương pháp này, họ chỉ yêu cầu 7 phép nhân (mỗi $M$ một phép nhân) thay vày 8 như cách thức cũ.

Xem thêm: Tại Sao Phải Phát Triển Sản Phẩm Mới Tại Sao Cần Phải Phát Triển Sản Phẩm Mới?

Thực hiện đệ quy quy trình trên cho đến khi ma trận tất cả 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 biệt về độ phức hợp của nhị thuật toán vừa bàn:


*

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

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


*

Vào tháng 3/2013, A. M. Davie và A. J. Stothers công bố bài báo Improved bound for complexity of matrix multiplication và cho biết họ để được số lượng $mathcalO(n^2.37369)$ khi đổi mới và điều tra 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 and Fast Matrix Multiplication tiếp tục phân tích thuật toán của nhị nhà khoa học này và đạt được số lượng $mathcalO(n^2.3728639)$.

Vào mon 7/2014, Virginia Vassilevska Williams thuộc đại học Standford công bố bài báo Multiplying matrices in $mathcalO(n^2.373)$ time đưa ra phương pháp cách tân 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 các thuật toán hiện tại tại, bọn họ rút ra được bảng đối chiếu về độ phức hợp 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à các nhà kỹ thuật vẫn sẽ 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 gs Ngô quang quẻ Hưng trên Procul, thì những thuật toán của Strassen với Coppersmith-Winograd chỉ có giá trị định hướng là chính, trong thực tiễn ít ai dùng cho những ma trận bự vì hidden-constant quá lớn và implement phức tạp, dễ dẫn đến lỗi .

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