Nhân 2 ma trận c++

Ma trận với các phnghiền tân oán tương quan tới nó là một trong những phần siêu quan trọng trong phần đông hầu hết thuật toán tương quan mang lại số học tập.

You watching: Nhân 2 ma trận c++

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


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

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

Nhắc lại một chút kỹ năng và kiến thức toán thù học về phương pháp nhân 2 ma trận $A$ với $B$, ĐK đầu tiên để hoàn toàn có thể triển khai phép nhân này là Lúc số cột của ma trận $A$ bằng số mặt hàng của ma trận $B$.

Với $A$ là 1 ma trận bao gồm form size $n imes m$ với $B$ là một ma trận form size $m imes p$ thì tích của $A imes B$ đang là 1 trong ma trận $n imes p$ được tính 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 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 các thành phần vào một hàng của ma trận $A$ với những bộ phận vào cột tương xứ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ư 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$ kia là gì vậy???

Chửi trước: Ôi ttách, đấy là cái vết tính tổng nhưng mà cũng lần khần à? Về học lại tân oán cung cấp 3 tuyệt năm độc nhất vô nhị ĐH gì đấy đi nhé! Tốn thời gian bm!!Đáp sau: Cái vệt zích zắc sẽ là kí hiệu phnghiền tính tổng, rất có thể tưởng tượng kí hiệu này giống như một vòng lặp for vào thực hiện phép tính cùng, số $n$ sinh sống bên trên đỉnh chỉ tổng tần số lặp quan trọng, số $r = 1$ nghỉ ngơi dưới mang lại ta biết quý giá nào cần chạy trong tầm lặp for cùng ban đầu chạy trường đoản cú cực hiếm từng nào. Biểu thức kèm theo sau kí hiệu $sum$ đến ta biết phxay cộng những cực hiếm như thế nào sẽ tiến hành triển khai bên trong vòng lặp kia.
Tiếp theo, hãy cùng coi chúng ta bao gồm các cách nào nhằm implement thuật toán thù này trên máy vi tính.

The naive algorithm

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

Trong ngôi trường hợp này, chúng ta hay implement thuật tân oán nhân ma trận bằng phương pháp áp dụng đúng chuẩn phương pháp từ khái niệm tân oán học của chính nó, áp dụng vòng lặp, như sau:


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

1: Khởi sản xuất ma trận C có kích 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 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 form size $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 dễ dàng implement, chỉ cần theo lối lưu ý đến thường thì, bỏ lỡ hết đều yếu tố như độ phức tạp, sự tối ưu...

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

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

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

Xét lại thuật tân oán naive ở chỗ trước, nhằm tính một phần tử $C_i,j$ của ma trận tích $C$, ta buộc phải tiến hành nhì phnghiền nhân với một phnghiền cộng. Suy ra trường hợp $C$ là 1 trong những ma trận vuông có form size $2 imes 2$, thì nhằm tính tứ bộ phận của $C$, yên cầu nên triển khai $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à phần nhiều ma trận cung cấp $n$ (Tức là các ma trận $n imes n$) thì bọn họ cần phải tiến hành $n^3$ phép nhân cùng $(n - 1) imes n^2$ phxay cộng.

Ý tưởng thuật tân oán của Strassen <3> là vận dụng chia để trị nhằm giải quyết bài toán 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 có kích thước $n imes n$, chúng ta phân tách chúng thành 4 ma trận nhỏ, với biểu diễn tích $A imes B = C$ theo những ma trận bé đó:

*

Trong đó:

$$eginalignC_1,1 và = 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 & = A_2,1B_1,2 + A_2,2B_2,2 endalign$$Tuy nhiên với giải pháp so với này thì bọn họ vẫn đề nghị 8 phxay nhân để tính ra ma trận $C$. Đây là phần đặc trưng độc nhất của vụ việc.

See more: What Is The Meaning Of " Touché Là Gì, Touche Nghĩa Là Gì

Chúng ta khái niệm ra những ma trận $M$ mới nhỏng sau:

$$eginalignM_1 và = (A_1,1 + A_2,2)(B_1,1 + B_2,2) \M_2 và = (A_2,1 + A_2,2) B_1,1 \M_3 và = A_1,1 (B_1,2 - B_2,2) \M_4 và = 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 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ư sau:

$$eginalignC_1,1 và = M_1 + M_4 - M_5 + M_7 \C_1,2 & = 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 biện pháp này, bọn họ chỉ việc 7 phép nhân (từng $M$ một phép nhân) cầm bởi 8 nlỗi phương pháp cũ.

Thực hiện tại đệ quy quy trình trên cho tới lúc ma trận có cấp ba.

Độ phức hợp 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ông giống nhau về độ tinh vi của nhì thuật toán vừa bàn:

*

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

Dựa trên phát minh sáng tạo của Strassen, vào thời điểm tháng 5/1987, hai công ty công nghệ Don Coppersmith với Shmuel Winograd công bố bài bác báo Matrix Multiplication via Arithmetic Progression <4> ra mắt một phương pháp new nhằm tăng tốc độ nhân ma trận và cho thấy thêm độ phức hợp của thuật toán thù mà người ta phát triển là $mathcalO(n^2.376)$ và được Review là thuật tân oán nhân ma trận nhanh hao tuyệt nhất tính cho tới thời đặc điểm đó.

*

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

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

Vào mon 7/2014, Virginia Vassilevska Williams trực thuộc ĐH Standford công bố bài xích báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> chỉ dẫn phương pháp đổi mới 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 sệt lại, cùng với những thuật toán thù hiện thời, họ đúc kết được bảng so sánh về độ tinh vi nlỗi 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 CW cải tiếnMa trận vuông$O(n^2.373)$

Và những nhà công nghệ vẫn đã mài miệt nghiên cứu và phân tích để lấy số lượng 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ỉ có cực hiếm định hướng là chính, vào thực tế không nhiều người sử dụng cho các ma trận to vị hidden-constant quá lớn với implement phức tạp, dễ bị lỗi <8>.

See more: " Perfume Là Gì ? Nghĩa Của Từ Perfume Trong Tiếng Việt Eau De Cologne Là Gì


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


Chuyên mục: Chia sẻ