Cách nhân 2 ma trận

      29

Ma trận cùng những phnghiền toán liên quan cho tới nó là một phần cực kỳ quan trọng trong số đông rất nhiều thuật toán thù liên quan mang lại số học tập.

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

Ở bài bác trước, chúng ta có đề cùa đến việc ứng dụng phép nhân ma trận nhằm tính số Fibonacci một cách hiệu quả. Vậy thuật toán thù nhân ma trận nhưng mà họ áp dụng làm việc vào nội dung bài viết vẫn thực sự tác dụng xuất xắc chưa?


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

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

Nhắc lại một ít kiến thức tân oán học tập về cách thức nhân 2 ma trận $A$ và $B$, ĐK thứ nhất nhằm có thể tiến hành phép nhân này là Lúc số cột của ma trận $A$ thông qua 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$ và $B$ là 1 trong những ma trận size $m imes p$ thì tích của $A imes B$ đã là 1 trong ma trận $n imes p$ được xem bằng phương pháp sau:

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

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

Chửi trước: Ôi ttránh, đó là loại dấu tính tổng mà lại cũng lần chần à? Về học lại toán thù cấp 3 hay năm tuyệt nhất ĐH nào đấy đi nhé! Tốn thời hạn bm!!Đáp sau: Cái lốt zích zắc đó là kí hiệu phép tính tổng, có thể tưởng tượng kí hiệu này giống như một vòng lặp for trong triển khai phép tính cộng, số $n$ sống bên trên đỉnh chỉ tổng chu kỳ lặp cần thiết, số $r = 1$ ở dưới cho ta biết giá trị nào phải chạy trong khoảng lặp for và bước đầu chạy trường đoản cú cực hiếm bao nhiêu. Biểu thức kèm theo sau kí hiệu $sum$ cho ta biết phxay cộng những quý hiếm như thế nào sẽ tiến hành triển khai phía bên trong vòng lặp đó.
Tiếp theo, hãy cùng xem họ gồm các phương pháp như thế nào để implement thuật toán thù này bên trên máy tính.

The naive sầu algorithm

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

Trong ngôi trường hòa hợp này, bọn họ thường xuyên implement thuật toán thù nhân ma trận bằng phương pháp áp dụng đúng chuẩn công thức tự tư tưởng toán thù học của nó, áp dụng vòng lặp, như sau:


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

1: Khởi chế tác ma trận C bao gồm kích thước $n imes p$ 2: For i trường đoản cú $1 ightarrow n$:3:  For j trường đoản cú $1 ightarrow p$:4:   Gán $sum = 0$5:   For r từ bỏ $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 gọi là naive sầu algorithm (ntạo thơ)? đó là do nó rất giản đơn implement, chỉ việc theo lối cân nhắc thường thì, bỏ qua mất không còn hầu hết nhân tố như độ phức hợp, sự về tối ưu...

Độ tinh vi của thuật toán bên trên là $mathcalO(nmp)$, vào trường đúng theo toàn bộ những ma trận phần đa là ma trận vuông $n imes n$ thì độ phức hợp của thuật tân oán vẫn là $mathcalO(n^3)$

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

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

Xét lại thuật toán naive sầu tại phầ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 bắt buộc tiến hành nhị phép nhân với một phép cùng. Suy ra trường hợp $C$ là 1 ma trận vuông tất cả form size $2 imes 2$, thì để tính tứ phần tử của $C$, yên cầu nên tiến hành $2 imes 2^2 = 2^3 = 8$ phxay nhân và $(2 - 1) imes 2^2 = 4$ phép cùng. Nếu $A$ và $B$ là hầu như ma trận cấp cho $n$ (Có nghĩa là các ma trận $n imes n$) thì họ cần phải thực hiện $n^3$ phép nhân với $(n - 1) imes n^2$ phnghiền cùng.

Ý tưởng thuật tân oán của Strassen <3> là vận dụng phân tách nhằm trị để giải quyết bài bác tân oán theo hướng của giải mã cơ bản trên. Cụ thể là: cùng với mỗi 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ới biểu diễn tích $A imes B = C$ theo những ma trận con đó:

*

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 và = 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 biện pháp phân tích này thì bọn họ vẫn buộc phải 8 phép nhân nhằm tính ra ma trận $C$. Đây là phần đặc biệt quan trọng độc nhất vô nhị của vụ việc.

Xem thêm: Cách Từ Bỏ Facebook Chỉ Mất 10 Giây, 8 Lợi Ích Có Được Ngay Khi Bạn Từ Bỏ Facebook

Chúng ta tư tưởng ra những ma trận $M$ bắt đầu như 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 & = 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à biểu diễn lại những bộ phận của $C$ theo $M$ nhỏng sau:

$$eginalignC_1,1 và = M_1 + M_4 - M_5 + M_7 \C_1,2 & = M_3 + M_5 \ C_2,1 và = M_2 + M_4 \C_2,2 & = M_1 - M_2 + M_3 + M_6endalign$$Bằng cách này, bọn họ chỉ việc 7 phép nhân (từng $M$ một phnghiền nhân) ráng bởi 8 nhỏng phương thức cũ.

Thực hiện đệ quy quá trình trên cho tới khi ma trận bao gồm trung học cơ sở.

Độ tinh vi của thuật tân oá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 cùng các thuật toán thù cải tiến

Dựa bên trên sáng tạo của Strassen, trong thời điểm tháng 5/1987, nhì đơn vị khoa học Don Coppersmith và Shmuel Winograd ra mắt bài báo Matrix Multiplication via Arithmetic Progression <4> giới thiệu một phương thức bắt đầu nhằm tăng tốc độ nhân ma trận với cho biết độ phức tạp của thuật toán mà người ta cải tiến và phát triển là $mathcalO(n^2.376)$ với được Đánh Giá là thuật toán nhân ma trận nhanh khô duy nhất tính cho tới thời đặc điểm này.

*

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

Tháng 1/2014, François Le Gall ra mắt bài xích báo Powers of Tensors & Fast Matrix Multiplication <6> tiếp tục phân tích thuật tân oán của nhì đơn vị công nghệ này với dành được con số $mathcalO(n^2.3728639)$.

Vào mon 7/2014, Virginia Vassilevska Williams nằm trong đại học Standford ra mắt bài báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> chỉ dẫn phương thức cách tân thuật toán của Coppersmith-Winograd cùng chào làng độ phức hợp là $mathcalO(n^2.372873)$.

Kết luận

Tổng đặc lại, với những thuật tân oán hiện tại, chúng ta đú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 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à những bên khoa học vẫn đã mải mê 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ì những thuật tân oán của Strassen với Coppersmith-Winograd chỉ với cực hiếm định hướng là thiết yếu, trong thực tiễn ít ai sử dụng cho những ma trận Khủng bởi vì hidden-constant quá rộng cùng implement phức tạp, dễ dẫn đến lỗi <8>.

Xem thêm: Sun Ht Và Phở Cao Bao Nhiêu, Tiểu Sử Diễn Viên Ngọc Thảo, Phở Cao Vân Ở Quận 1, Tp


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


Chuyên mục: Kiến thức thú vị