HƯỚNG DẪN CÁCH NHÂN 2 MA TRẬN

Ma trận và các phép toán liên quan cho tới nó là một trong những phần khôn cùng quan trọng vào phần nhiều hồ hết thuật toán tương quan mang đến số học tập.

Bạn đang xem: Hướng dẫn cách nhân 2 ma trận

Tại bài bác trước, bọn họ có đề cùa tới việc ứng dụng phép nhân ma trận nhằm tính số Fibonacci một bí quyết hiệu quả. Vậy thuật tân oán nhân ma trận nhưng chúng ta thực hiện nghỉ ngơi trong bài viết vẫn đích thực công dụng tuyệt chưa?


Trong quá trình tìm hiểu nhằm viết bài này thì bản thân phân phát chỉ ra một điều khá là thú vui, đó là có nhiều thuật toán thù để tiến hành nhân ma trận, tuy vậy ngành kỹ thuật máy tính xách tay vẫn không tìm ra được câu trả lời đến câu hỏi: Đâu là thuật toán về tối ưu để triển khai phép nhân ma trận? <1>

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

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

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

$$left( eginarrayccca và b \c & d endarray ight) imesleft( eginarraycccx \yendarray ight)=left( eginarraycccax + by \cx + dyendarray ight)$$Hình sau diễn tả cách tính một trong những 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 những phần tử vào một sản phẩm của ma trận $A$ với các bộ phận vào 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 mang lại gọn gàng hơn như là sau:

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

Chửi trước: Ôi ttách, đây là dòng dấu tính tổng nhưng mà cũng phân vân à? Về học lại tân oán cung cấp 3 giỏi năm độc nhất vô nhị ĐH gì đấy đi nhé! Tốn thời gian bm!!Đáp sau: Cái vệt zích zắc sẽ là kí hiệu phép tính tổng, có thể hình dung kí hiệu này giống như một vòng lặp for vào tiến hành phnghiền tính cộng, số $n$ sống trên đỉnh chỉ tổng số lần lặp cần thiết, số $r = 1$ ở dưới cho ta biết cực hiếm làm sao bắt buộc chạy trong vòng lặp for với bước đầu chạy từ cực hiếm bao nhiêu. Biểu thức kèm theo sau kí hiệu $sum$ đến ta biết phnghiền cộng những cực hiếm làm sao sẽ tiến hành tiến hành phía bên trong vòng lặp kia.
Tiếp theo, hãy thuộc xem chúng ta bao gồm những cách nào nhằm implement thuật tân oán này trên laptop.

The naive sầu algorithm

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

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


Input: Hai ma trận A size $n imes m$ và B form size $m imes p$

1: Khởi chế tạo ma trận C có form size $n imes p$ 2: For i từ $1 ightarrow n$:3:  For j tự $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 call là naive algorithm (ntạo thơ)? kia là vì nó rất giản đơn implement, chỉ cần theo lối xem xét thường thì, bỏ qua mất không còn rất nhiều nguyên tố như độ tinh vi, sự buổi tối ưu...

Độ phức tạp của thuật toán thù bên trên là $mathcalO(nmp)$, trong ngôi trường đúng theo tất cả những ma trận đa số là ma trận vuông $n imes n$ thì độ phức tạp của thuật tân oán đã là $mathcalO(n^3)$

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

Vào năm 1969, Volker Strassen - lúc đó đang là sinc viên tại MIT - nhận định rằng $mathcalO(n^3)$ chưa phải là số lượng buổi tối ưu được cho phép nhân ma trận, cùng đề xuất một thuật tân oán mới bao gồm thời hạn chạy chỉ nhanh khô hơn một chút nhưng trong tương lai đã nâng theo tương đối nhiều đơn vị khoa học dấn thân tiếp tục nghiên cứu và cho tới thời khắc bây chừ, sẽ có nhiều phương thức bắt đầu được giới thiệu như là thuật toán Coppersmith-Winograd (đã nói tại vị trí sau), hoặc các phương án tiếp cận bởi xây dựng tuy vậy song bên trên các sản phẩm tính/các core,... Điểm thú vui là Strassen nghĩ về ra thuật tân oán này vì chưng nó là bài bác tập vào một lớp nhưng mà ông sẽ học tập <2>.

Xét lại thuật tân oán naive ở chỗ trước, nhằm tính một trong những phần tử $C_i,j$ của ma trận tích $C$, ta đề nghị triển khai hai phép nhân với một phép cùng. Suy ra ví như $C$ là 1 ma trận vuông gồm form size $2 imes 2$, thì để tính tư thành 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$ phxay cộng. Nếu $A$ với $B$ là những ma trận cung cấp $n$ (có nghĩa là các ma trận $n imes n$) thì họ cần phải tiến hành $n^3$ phxay nhân và $(n - 1) imes n^2$ phép cùng.

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

*

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 phân tích này thì họ vẫn phải 8 phxay nhân để tính ra ma trận $C$. Đây là phần đặc biệt quan trọng tốt nhất của vấn đề.

Xem thêm: Gói Nạp Tiền Lên Steam Bằng Thẻ Ngân Hàng Tại Việt Nam, Cách Nạp Tiền Vào Tài Khoản Steam Wallet Mới Nhất

Chúng ta khái niệm ra các ma trận $M$ mới nhỏng sau:

$$eginalignM_1 và = (A_1,1 + A_2,2)(B_1,1 + B_2,2) \M_2 & = (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 & = (A_1,1 + A_1,2) B_2,2 \M_6 & = (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 phần tử của $C$ theo $M$ nlỗi sau:

$$eginalignC_1,1 và = M_1 + M_4 - M_5 + M_7 \C_1,2 và = M_3 + M_5 \ C_2,1 và = M_2 + M_4 \C_2,2 và = M_1 - M_2 + M_3 + M_6endalign$$Bằng biện pháp này, chúng ta chỉ việc 7 phxay nhân (từng $M$ một phnghiền nhân) gắng vị 8 nlỗi cách thức cũ.

Thực hiện nay đệ quy quy trình trên cho đến khi ma trận gồm trung học phổ thông.

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

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

*

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

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

*

Vào tháng 3/2013, A. M. Davie cùng A. J. Stothers chào làng bài báo Improved bound for complexity of matrix multiplication <5> cùng cho thấy bọn họ đặt được con số $mathcalO(n^2.37369)$ khi cải tiến và 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 & Fast Matrix Multiplication <6> thường xuyên so sánh thuật toán của hai nhà khoa học này cùng đã có được số lượng $mathcalO(n^2.3728639)$.

Vào tháng 7/2014, Virginia Vassilevska Williams nằm trong ĐH Standford ra mắt bài báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> đưa ra phương thức cải tiến thuật toán của Coppersmith-Winograd và công bố độ tinh vi là $mathcalO(n^2.372873)$.

Kết luận

Tổng đặc lại, cùng với các thuật tân oán hiện tại, bọn họ đúc rút được bảng đối chiếu về độ tinh vi nhỏng sau:

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

Và các bên công nghệ vẫn vẫn mài miệt phân tích để mang 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 tân oán của Strassen cùng Coppersmith-Winograd chỉ mang giá trị triết lý là thiết yếu, trong thực tế không nhiều người cần sử dụng cho những ma trận Khủng do hidden-constant quá to với implement tinh vi, dễ dẫn đến lỗi <8>.


Cảm ơn các bạn vẫn theo dõi và quan sát bài bác viết! các bạn cũng có thể follow mình bên trên Facebook để tại vị câu hỏi, hoặc thừa nhận thông tin về những bài viết bắt đầu.