Cách nhân 2 ma trận

Ma trận cùng những phxay toán liên quan tới nó là một trong những phần rất quan trọng đặc biệt vào số đông đầy đủ thuật toán thù liên quan mang lại số học.

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

Ở bài xích trước, bọn họ gồm đề cùa đến việc áp dụng phnghiền nhân ma trận nhằm tính số Fibonacci một cách kết quả. Vậy thuật toán thù nhân ma trận mà chúng ta áp dụng sống trong bài viết sẽ đích thực hiệu quả hay chưa?


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

Định nghĩa phxay 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ề cách thức nhân 2 ma trận $A$ cùng $B$, điều kiện thứ nhất nhằm hoàn toàn có thể triển khai phxay nhân này là lúc số cột của ma trận $A$ ngay số mặt hàng của ma trận $B$.

Với $A$ là 1 trong ma trận có kích 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à một ma trận $n imes p$ được tính 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 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 những phần tử trong một hàng của ma trận $A$ với các phần tử trong 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 cho gọn gàng hơ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$ tê là gì vậy???

Chửi trước: Ôi ttách, đây là loại vết tính tổng mà cũng trù trừ à? Về học tập lại toán thù cấp 3 tốt năm tốt nhất ĐH nào đấy đi nhé! Tốn thời gian bm!!Đáp sau: Cái vết zích zắc chính là kí hiệu phnghiền tính tổng, hoàn toàn có thể tưởng tượng kí hiệu này y như một vòng lặp for trong tiến hành phxay tính cộng, số $n$ sống 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 mang lại ta biết giá trị nào bắt buộc chạy trong khoảng lặp for và bắt đầu chạy trường đoản cú giá trị bao nhiêu. Biểu thức đi liền sau kí hiệu $sum$ mang đến ta biết phxay cùng các giá trị nào sẽ tiến hành triển khai bên phía trong vòng lặp đó.
Tiếp theo, hãy cùng coi họ có các phương pháp nào nhằm implement thuật tân oán này bên trên máy tính.

The naive algorithm

Naive Algorithm là từ bỏ dùng làm có một thuật toán thù đơn giản tuyệt nhất được tư duy một bí quyết "nkhiến thơ" bằng cách xử trí thông thường, ví dụ như search kiếm tuần tự (sequential/linear search)

Trong trường hợp này, chúng ta hay implement thuật toán nhân ma trận bằng phương pháp áp dụng chính xác bí quyết từ định nghĩa tân oán học của nó, thực hiện vòng lặp, như sau:


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

1: Khởi sinh sản ma trận C gồm kích thước $n imes p$ 2: For i trường đoản cú $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 sầu algorithm (ntạo thơ)? kia bởi vì nó rất đơn giản implement, chỉ việc theo lối lưu ý đến thông thường, làm lơ hết hồ hết nguyên tố nlỗi độ phức tạp, sự buổi tối ưu...

Độ tinh vi của thuật tân oán trên là $mathcalO(nmp)$, vào ngôi trường vừa lòng toàn bộ những ma trận các là ma trận vuông $n imes n$ thì độ phức tạp của thuật toá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 kia đã là sinc viên trên MIT - nhận định rằng $mathcalO(n^3)$ không hẳn là con số về tối ưu được cho phép nhân ma trận, và đề xuất một thuật tân oán bắt đầu tất cả thời gian chạy chỉ nkhô nóng hơn một chút mà lại sau này đã nâng theo không hề ít nhà khoa học dấn thân liên tục phân tích với cho tới thời điểm bây giờ, vẫn có nhiều phương thức new được đưa ra như là thuật tân oán Coppersmith-Winograd (đang nói ở đoạn sau), hoặc những phương án tiếp cận bởi lập trình song tuy vậy bên trên các thiết bị tính/những core,... Điểm thú vị là Strassen suy nghĩ ra thuật tân oán này vị nó là bài tập trong một tờ mà lại ông sẽ học tập <2>.

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

Ý tưởng thuật tân oán của Strassen <3> là áp dụng chia nhằm trị để giải quyết bài xích tân oán theo hướng của giải thuật cơ phiên bản trên. Cụ thể là: với mỗi ma trận vuông A, B, C tất cả size $n imes n$, bọn họ chia 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 bé đó:

*

Trong đó:

$$eginalignC_1,1 & = A_1,1B_1,1 + A_1,2B_2,1 \C_1,2 và = 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 cách so với này thì bọn họ vẫn buộc phải 8 phép nhân để tính ra ma trận $C$. Đây là phần đặc biệt độc nhất vô nhị của sự việc.

Xem thêm: Khám Phá Cách Nhồi Bột Làm Bánh Bột Lọc Huế Bằng Bột Lọc Tươi

Chúng ta quan niệm ra các ma trận $M$ mới như 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 và = A_2,2 (B_2,1 - B_1,1) \M_5 & = (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 thành phần 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, chúng ta chỉ cần 7 phxay nhân (mỗi $M$ một phép nhân) cầm bởi vì 8 nlỗi phương thức cũ.

Thực hiện đệ quy quy trình bên trên cho đến khi ma trận tất cả cấp hai.

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

Đồ thị sau so sánh sự không giống nhau về độ phức tạp của nhì thuật toán vừa bàn:

*

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

Dựa bên trên phát minh của Strassen, hồi tháng 5/1987, nhì bên khoa học Don Coppersmith cùng Shmuel Winograd ra mắt bài xích báo Matrix Multiplication via Arithmetic Progression <4> reviews một phương pháp bắt đầu nhằm tăng vận tốc nhân ma trận cùng cho biết thêm độ tinh vi của thuật tân oán mà họ phát triển là $mathcalO(n^2.376)$ cùng được reviews là thuật tân oán nhân ma trận nhanh nhất tính cho tới thời đ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 thấy thêm bọn họ đặt được con số $mathcalO(n^2.37369)$ Lúc đổi mới và khảo sát thuật toán của Coppersmith-Winograd.

Tháng 1/năm trước, François Le Gall chào làng bài báo Powers of Tensors và Fast Matrix Multiplication <6> thường xuyên so sánh thuật tân oán của nhị bên kỹ thuật này cùng đã đạt được con số $mathcalO(n^2.3728639)$.

Vào tháng 7/2014, Virginia Vassilevska Williams nằm trong ĐH Standford công bố bài báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> chỉ dẫn cách thức cải tiến thuật tân oán của Coppersmith-Winograd với chào làng độ phức tạp là $mathcalO(n^2.372873)$.

Kết luận

Tổng kết lại, với những thuật toán bây giờ, họ đúc rút được bảng so sánh 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 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 nhà khoa học vẫn đã mải mê phân tích để đưa 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ì các thuật tân oán của Strassen cùng Coppersmith-Winograd chỉ với quý giá định hướng là thiết yếu, vào thực tế không nhiều người sử dụng cho những ma trận béo vị hidden-constant quá rộng với implement tinh vi, dễ dẫn đến lỗi <8>.

Xem thêm: Hướng Dẫn Cách Thay Đổi Địa Chỉ Ip Trên Windows 10 Và Macos, Cách Đổi Địa Chỉ Ip Cho Điện Thoại


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


Chuyên mục: Kiến thức