Ma trận và các phép toán thù liên quan tới nó là một phần cực kỳ quan trọng trong phần nhiều đầy đủ thuật toán thù liên quan đến số học.

Bạn đang xem: Cách nhân 2 ma trận vuông cấp 3

Ở bài xích trước, chúng ta có đề cập tới bài toán vận dụng phnghiền nhân ma trận nhằm 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 bọn họ áp dụng sống trong nội dung bài viết đã thực thụ công dụng xuất xắc chưa?


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

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

Nhắc lại một chút 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 trước tiên để có thể thực hiện phxay nhân này là khi 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 tất cả size $n imes m$ và $B$ là một ma trận kích thước $m imes p$ thì tích của $A imes B$ sẽ là một trong những 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 biểu hiện 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 phép nhân những bộ phận trong một mặt hàng của ma trận $A$ cùng với các bộ phận 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 mang lại gọn 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, đây là loại vết tính tổng mà lại cũng chần chừ à? Về học tập lại toán thù cung cấp 3 giỏi năm tuyệt nhất ĐH gì đấ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 phép tính tổng, rất có thể hình dung kí hiệu này giống hệt như một vòng lặp for trong triển khai phép tính cùng, số $n$ nghỉ ngơi bên trên đỉnh chỉ tổng số lần lặp quan trọng, số $r = 1$ ở dưới mang lại ta biết giá trị nào đề xuất chạy trong tầm lặp for và ban đầ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 phnghiền cùng các cực hiếm như thế nào sẽ được triển khai phía bên trong vòng lặp kia.
Tiếp theo, hãy cùng coi bọn họ gồm những cách như thế nào để implement thuật toán thù này bên trên máy tính xách tay.

The naive sầu algorithm

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

Trong ngôi trường vừa lòng này, chúng ta thường xuyên implement thuật toán nhân ma trận bằng phương pháp vận dụng đúng đắn bí quyết trường đoản cú định nghĩa toán học tập của chính nó, sử dụng vòng lặp, như sau:


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

1: Khởi tạo nên ma trận C bao gồm kích cỡ $n imes p$ 2: For i từ bỏ $1 ightarrow n$:3:  For j từ bỏ $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 call là naive sầu algorithm (ntạo thơ)? đó bởi vì nó rất dễ implement, chỉ việc theo lối xem xét thường thì, bỏ qua không còn phần lớn nguyên tố nlỗi độ phức hợp, sự tối ưu...

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

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

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

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

*

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 & = A_2,1B_1,2 + A_2,2B_2,2 endalign$$Tuy nhiên cùng với phương pháp phân tích này thì họ vẫn buộc phải 8 phnghiền nhân nhằm tính ra ma trận $C$. Đây là phần quan trọng đặc biệt tốt nhất của sự việc.

Chúng ta định nghĩa ra các 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 & = (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à biểu diễn lại các thành phần của $C$ theo $M$ như 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 giải pháp này, bọn họ chỉ cần 7 phép nhân (mỗi $M$ một phép nhân) thế bởi 8 như cách thức cũ.

Thực hiện đệ quy quy trình bên trên cho tới Lúc ma trận có trung học cơ sở.

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

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

*

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

Dựa trên sáng tạo của Strassen, vào tháng 5/1987, hai nhà công nghệ Don Coppersmith cùng Shmuel Winograd công bố bài xích 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 với cho thấy thêm độ phức hợp của thuật toán thù mà họ cách tân và phát triển là $mathcalO(n^2.376)$ và được đánh giá là thuật toán nhân ma trận nhanh khô duy nhất tính tới thời đặc điểm này.

*

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 chúng ta đặt được con số $mathcalO(n^2.37369)$ Lúc đổi mới với điều tra khảo sát thuật toán của Coppersmith-Winograd.

Tháng 1/năm trước, 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 toán thù của nhì đơn vị khoa học này cùng đạt được số lượng $mathcalO(n^2.3728639)$.

Vào tháng 7/2014, Virginia Vassilevska Williams ở trong ĐH Standford chào làng bài bác báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> giới thiệu cách thức cải tiến thuật toán của Coppersmith-Winograd cùng ra mắt độ phức hợp là $mathcalO(n^2.372873)$.

Xem thêm: Hướng Dẫn Lập Và Nộp Mẫu Hóa Đơn Cho Cơ Quan Thuế, Hướng Dẫn Lập Và Nộp Thông Báo Phát Hành Hóa Đơn

Kết luận

Tổng đặc lại, cùng với các thuật toán thù bây chừ, chúng ta đúc kết được bảng so sánh 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 tân oán CW cải tiếnMa trận vuông$O(n^2.373)$

Và những nhà khoa học vẫn đang miệt mài nghiên cứu để mang số lượng này về $mathcalO(n^2)$

*

Theo một comment của giáo sư Ngô Quang Hưng trên Procul, thì các thuật toán của Strassen cùng Coppersmith-Winograd chỉ có cực hiếm kim chỉ nan là thiết yếu, trong thực tế không nhiều người cần sử dụng cho các ma trận Khủng bởi hidden-constant quá to cùng implement tinh vi, dễ dẫn đến lỗi <8>.