Sunday . 25 July . 2021

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

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

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


Trong quy trình mày mò để viết bài này thì bản thân phát hiển thị một điều khá là độc đáo, chính là có rất nhiều thuật toán nhằm triển khai nhân ma trận, tuy vậy ngành công nghệ máy tính xách tay vẫn chưa đưa ra được câu vấn đáp cho 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 phép Nhân ma trận

Nhắc lại một chút ít kỹ năng toán thù học về cách thức nhân 2 ma trận $A$ với $B$, điều kiện đầu tiên nhằm rất có thể triển khai phnghiền 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 ma trận gồm kích thước $n imes m$ cùng $B$ là một trong những ma trận form size $m imes p$ thì tích của $A imes B$ đang 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 và 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 một trong những phần tử AB của ma trận tích:

*

Một thành phần là tổng của phép nhân những bộ phận vào một sản phẩm của ma trận $A$ cùng với những bộ phận trong cột tương ứ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 hơn hẳn như 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$ tê là gì vậy???

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

The naive sầu algorithm

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

Trong ngôi trường phù hợp này, bọn họ thường implement thuật toán thù nhân ma trận bằng cách vận dụng đúng đắn bí quyết từ khái niệm toán thù học của nó, áp dụng vòng lặp, nhỏng sau:


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

1: Khởi chế tạo ra ma trận C bao gồm form size $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 kích thước $n imes p$


Tại sao lại Call là naive sầu algorithm (ntạo thơ)? đó bởi vì nó rất đơn giản implement, chỉ việc đi theo lối Để ý đến thông thường, làm lơ hết đều yếu tố nhỏng độ tinh vi, sự về tối ưu...

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

Chia để trị - Thuật toán thù Strassen

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

Xét lại thuật toán thù naive sầu ở trong phần trước, nhằm tính 1 phần tử $C_i,j$ của ma trận tích $C$, ta bắt buộc thực hiện hai phnghiền nhân cùng một phnghiền cộng. Suy ra ví như $C$ là một ma trận vuông có kích thước $2 imes 2$, thì để tính tứ thành phần của $C$, đòi hỏi nên thực hiện $2 imes 2^2 = 2^3 = 8$ phép nhân và $(2 - 1) imes 2^2 = 4$ phxay cộng. Nếu $A$ với $B$ là đông đảo ma trận cấp cho $n$ (Có nghĩa là các ma trận $n imes n$) thì bọn họ cần phải thực hiện $n^3$ phxay nhân với $(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 chia nhằm trị nhằm giải quyết và xử lý bài xích tân oán theo vị trí hướng của lời giải cơ phiên bản bên trên. Cụ thể là: với mỗi ma trận vuông A, B, C gồm kích cỡ $n imes n$, bọn họ phân chia chúng thành 4 ma trận bé, và trình diễn tích $A imes B = C$ theo các ma trận con đó:

*

Trong đó:

$$eginalignC_1,1 và = 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 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 giải pháp đối chiếu này thì họ vẫn đề xuất 8 phnghiền nhân để tính ra ma trận $C$. Đây là phần đặc biệt độc nhất vô nhị của vấn đề.

Xem thêm: Hướng Dẫn Bật Remote Desktop Trên Windows 10 Và Cách Remote Desktop Win 10

Chúng ta quan niệm ra các ma trận $M$ new nlỗi 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 & = 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à màn trình diễn lại các phần tử của $C$ theo $M$ nhỏng 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 & = M_1 - M_2 + M_3 + M_6endalign$$Bằng bí quyết này, họ chỉ cần 7 phép nhân (mỗi $M$ một phnghiền nhân) chũm vì 8 như phương thức cũ.

Thực hiện tại đệ quy quá trình bên trên cho đến Lúc ma trận gồm cấp hai.

Độ phức hợ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 nhị thuật tân oán vừa bàn:

*

Coppersmith-Winograd Algorithm và những thuật tân oá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, nhì công ty khoa học Don Coppersmith cùng Shmuel Winograd chào làng bài bác báo Matrix Multiplication via Arithmetic Progression <4> reviews một cách thức bắt đầu để tăng vận tốc nhân ma trận cùng cho thấy độ tinh vi của thuật tân oán mà người ta phát triển là $mathcalO(n^2.376)$ với được nhận xét là thuật toán nhân ma trận nkhô nóng tuyệt nhất tính tới thời đặc điểm đó.

*

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

Tháng 1/2014, François Le Gall công bố bài bác báo Powers of Tensors và Fast Matrix Multiplication <6> liên tục phân tích thuật toán của hai đơn vị công nghệ này cùng có được số lượng $mathcalO(n^2.3728639)$.

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

Kết luận

Tổng sệt lại, với các thuật toán ngày nay, bọn họ đúc rút được bảng đối chiếu về độ phức hợp nlỗi sau:

Thuật toánInputĐộ phức tạp
Naive sầu 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 công ty khoa học vẫn đã miệt mài phân tích để lấy con số này về $mathcalO(n^2)$

*

Theo một phản hồi của giáo sư Ngô Quang Hưng bên trên Procul, thì các thuật toán thù của Strassen và Coppersmith-Winograd chỉ có cực hiếm kim chỉ nan là chủ yếu, vào thực tiễn ít ai sử dụng cho các ma trận bự do hidden-constant quá to với implement phức tạp, dễ bị lỗi <8>.

Xem thêm: Top 10 Game Tam Quốc Chiến Thuật Hấp Dẫn Trên Android, Ios, Tam Quốc Công Thành


Cảm ơn chúng ta vẫn theo dõi bài xích viết! những chúng ta có thể follow mình bên trên Facebook để tại vị thắc mắc, hoặc dìm đọc tin về những nội dung bài viết bắt đầu.


Chuyên mục: Cách làm