Cách nhân hai ma trận

  -  

Ma trận và những phxay toán thù tương quan tới nó là một phần rất đặc biệt quan trọng vào hầu hết hầu như thuật toán thù tương quan mang đến số học tập.

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

Ở bài trước, họ tất cả đề cập đến câu hỏi vận dụng phxay nhân ma trận để tính số Fibonacci một cách kết quả. Vậy thuật toán thù nhân ma trận nhưng chúng ta sử dụng sinh sống vào nội dung bài viết vẫn thực thụ kết quả tuyệt chưa?


Trong quy trình tò mò để viết bài này thì bản thân phân phát hiển thị một điều khá là thú vui, sẽ là có tương đối nhiều thuật toán để thực hiện nhân ma trận, mặc dù ngành công nghệ laptop vẫn chưa tìm ra được câu vấn đáp mang đến câu hỏi: Đâu là thuật toán buổi tối ưu để thực hiện phxay 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 và kỹ năng toán học về phương thức nhân 2 ma trận $A$ và $B$, ĐK đầu tiên nhằm hoàn toàn có thể thực hiện phnghiền 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 bao gồm kích cỡ $n imes m$ với $B$ là một trong ma trận form size $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 & d endarray ight) imesleft( eginarraycccx \yendarray ight)=left( eginarraycccax + by \cx + dyendarray ight)$$Hình sau mô tả phương pháp tính một trong những phần tử AB của ma trận tích:

*

Một phần tử là tổng của phnghiền nhân những thành phần vào một hàng của ma trận $A$ với các thành phần vào cột khớp ứ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 hoàn toàn như 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 trời, đó là cái dấu tính tổng nhưng mà cũng băn khoăn à? Về học tập lại toán thù cấp 3 giỏi năm độc nhất vô nhị ĐH gì đấy đi nhé! Tốn thời hạn bm!!Đáp sau: Cái vệt zích zắc chính là kí hiệu phép tính tổng, rất có thể hình dung kí hiệu này hệt như một vòng lặp for vào triển khai phnghiền tính cộng, số $n$ ở bên trên đỉnh chỉ tổng chu kỳ lặp quan trọng, số $r = 1$ nghỉ ngơi bên dưới cho ta biết quý giá nào đề nghị chạy trong tầm lặp for và ban đầu chạy trường đoản cú giá trị bao nhiêu. Biểu thức kèm theo sau kí hiệu $sum$ mang đến ta biết phép cùng các cực hiếm làm sao sẽ được tiến hành phía bên trong vòng lặp đó.
Tiếp theo, hãy cùng coi chúng ta gồm những phương pháp làm sao nhằm implement thuật toán này trên máy tính xách tay.

The naive sầu algorithm

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

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


Input: Hai ma trận A kích cỡ $n imes m$ cùng B kích cỡ $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ừ bỏ $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 cỡ $n imes p$


Tại sao lại Điện thoại tư vấn là naive algorithm (nkhiến thơ)? đó là do nó rất dễ implement, chỉ cần đi theo lối cân nhắc thường thì, bỏ lỡ hết rất nhiều yếu tố nlỗi độ phức hợp, sự tối ưu...

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

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

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

Xét lại thuật toán thù naive sầu ở chỗ trước, để tính một trong những phần tử $C_i,j$ của ma trận tích $C$, ta yêu cầu thực hiện hai phnghiền nhân cùng một phép cộng. Suy ra giả dụ $C$ là một ma trận vuông bao gồm kích thước $2 imes 2$, thì nhằm tính tứ thành phần của $C$, yên cầu bắt buộc thực hiện $2 imes 2^2 = 2^3 = 8$ phxay nhân cùng $(2 - 1) imes 2^2 = 4$ phnghiền cộng. Nếu $A$ với $B$ là đầy đủ ma trận cấp cho $n$ (Tức là những ma trận $n imes n$) thì chúng ta cần phải triển khai $n^3$ phnghiền nhân và $(n - 1) imes n^2$ phxay cùng.

Ý tưởng thuật toán của Strassen <3> là vận dụng phân chia để trị để giải quyết bài toán thù theo vị trí hướng của lời giải cơ bạn dạng trên. Cụ thể là: cùng với mỗi ma trận vuông A, B, C bao gồm size $n imes n$, họ chia chúng thành 4 ma trận con, cùng màn biểu diễn tích $A imes B = C$ theo các 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 phương pháp đối chiếu này thì chúng ta vẫn phải 8 phép nhân nhằm tính ra ma trận $C$. Đây là phần quan trọng tuyệt nhất của vấn đề.

Xem thêm: Thông Tin Tuyển Sinh Trường Đại Học Điện Lực Tp Hcm, Trường Đại Học Điện Lực

Chúng ta tư tưởng ra những ma trận $M$ new nlỗi sau:

$$eginalignM_1 & = (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 & = (A_1,2 - A_2,2)(B_2,1 + B_2,2)endalign$$Và màn trình diễn lại các phần tử 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 bí quyết này, họ chỉ cần 7 phnghiền nhân (từng $M$ một phnghiền nhân) rứa bởi 8 nhỏng phương pháp cũ.

Thực hiện tại đệ quy quy trình bên trên cho tới lúc ma trận gồm trung học phổ thông.

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

Đồ thị sau đối chiếu sự không giống nhau về độ phức hợp của nhì thuật tân oán vừa bàn:

*

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

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

*

Vào mon 3/2013, A. M. Davie và A. J. Stothers chào làng bài xích báo Improved bound for complexity of matrix multiplication <5> cùng cho biết thêm chúng ta đặt được số lượng $mathcalO(n^2.37369)$ lúc cải tiến cùng khảo sát đ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 và Fast Matrix Multiplication <6> tiếp tục so với thuật tân oán của nhì bên công nghệ này cùng dành được số lượng $mathcalO(n^2.3728639)$.

Vào tháng 7/năm trước, Virginia Vassilevska Williams nằm trong đại học Standford ra mắt bài bác 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 thù của Coppersmith-Winograd với ra mắt độ tinh vi là $mathcalO(n^2.372873)$.

Kết luận

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

Thuật toánInputĐộ phức tạp
Naive sầu 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à những bên công nghệ vẫn sẽ mài miệt nghiên cứu để đưa con số này về $mathcalO(n^2)$

*

Theo một phản hồi của GS Ngô Quang 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 tế ít ai cần sử dụng cho các ma trận béo vày hidden-constant quá to và implement phức tạp, dễ dẫn đến lỗi <8>.

Xem thêm: Reading Unit 2 Lớp 11: Reading, Unit 2 Lớp 11: Reading


Cảm ơn chúng ta vẫn quan sát và theo dõi bài bác viết! những bạn cũng có thể follow mình trên Facebook để đặt thắc mắc, hoặc dìm công bố về những bài viết new.