Thuật toán nhân 2 ma trận

     

Ma trận với những phép tân oán liên quan cho tới nó là 1 phần vô cùng đặc biệt quan trọng trong phần lớn đều thuật toán thù liên quan đến số học tập.

Bạn đang xem: Thuật toán nhân 2 ma trận

Tại bài trước, bọn họ có đề cập đến Việc vận dụng phnghiền nhân ma trận nhằm tính số Fibonacci một bí quyết kết quả. Vậy thuật toán nhân ma trận cơ mà bọn họ sử dụng sống vào bài viết vẫn thực sự tác dụng tuyệt chưa?


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

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

Nhắc lại một chút ít kiến thức toán học về cách thức nhân 2 ma trận $A$ và $B$, ĐK thứ nhất để rất 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ố sản phẩm của ma trận $B$.

Với $A$ là 1 ma trận có kích thước $n imes m$ và $B$ là 1 ma trận kích thước $m imes p$ thì tích của $A imes B$ đã là một trong ma trận $n imes p$ được tính 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 bộc lộ phương pháp tính một phần tử AB của ma trận tích:

*

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

The naive algorithm

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

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


Input: Hai ma trận A size $n imes m$ với B size $m imes p$

1: Khởi tạo nên ma trận C tất cả size $n imes p$ 2: For i từ $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 Gọi là naive algorithm (ngây thơ)? kia bởi vì nó rất dễ implement, chỉ việc theo lối suy xét thường thì, bỏ lỡ hết đều yếu tố nlỗi độ phức hợp, sự tối ưu...

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

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

Vào năm 1969, Volker Strassen - thời điểm đó vẫn là sinch viên tại MIT - cho rằng $mathcalO(n^3)$ không hẳn là số lượng về 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ù mới có thời hạn chạy chỉ nhanh hao hơn một ít tuy vậy về sau đã kéo theo không ít công ty khoa học lao vào liên tiếp nghiên cứu với cho đến thời điểm bây giờ, đang có rất nhiều cách thức new được chỉ dẫn như là thuật toán thù Coppersmith-Winograd (đã nói tại phần sau), hoặc các phương án tiếp cận bằng xây dựng song tuy vậy trên nhiều thiết bị tính/nhiều core,... Điểm độc đáo là Strassen suy nghĩ ra thuật tân oán này vày nó là bài tập vào một tờ cơ mà ông vẫn học <2>.

Xét lại thuật toán thù naive ở vị trí 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 triển khai nhị phxay nhân cùng một phnghiền cùng. Suy ra nếu $C$ là 1 trong những ma trận vuông tất cả kích cỡ $2 imes 2$, thì để tính tứ bộ phận của $C$, đòi hỏi phải triển khai $2 imes 2^2 = 2^3 = 8$ phxay nhân và $(2 - 1) imes 2^2 = 4$ phnghiền cùng. Nếu $A$ cùng $B$ là mọi ma trận cấp cho $n$ (Tức là những ma trận $n imes n$) thì chúng ta rất 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 toán thù của Strassen <3> là vận dụng phân tách để trị nhằm giải quyết bài bác toán thù 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 từng ma trận vuông A, B, C gồm form size $n imes n$, chúng ta phân tách bọn chúng thành 4 ma trận con, cùng biểu diễn tích $A imes B = C$ theo những ma trận nhỏ đó:

*

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 và = A_2,1B_1,2 + A_2,2B_2,2 endalign$$Tuy nhiên với cách phân tích này thì chúng ta vẫn buộc phải 8 phnghiền nhân nhằm tính ra ma trận $C$. Đây là phần đặc trưng độc nhất vô nhị của vấn đề.

Xem thêm: Cách Chơi Game Thám Hiểm Ngôi Nhà Ma 1, Top 8 Game Co, Đồ Vật Bị Giấu Bệnh Viện Bị Ám

Chúng ta có mang ra những ma trận $M$ mới 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 & = 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 và = (A_1,2 - A_2,2)(B_2,1 + B_2,2)endalign$$Và trình diễn lại những phần tử của $C$ theo $M$ nlỗi sau:

$$eginalignC_1,1 & = 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 cách này, bọn họ chỉ việc 7 phép nhân (mỗi $M$ một phxay nhân) thế vì 8 nhỏng phương thức cũ.

Thực hiện đệ quy quá trình bên trên cho đến khi ma trận có trung học cơ sở.

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

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

*

Coppersmith-Winograd Algorithm cùng các thuật tân oán cải tiến

Dựa bên trên sáng tạo của Strassen, hồi tháng 5/1987, nhì đơn vị công nghệ Don Coppersmith với Shmuel Winograd ra mắt bài xích báo Matrix Multiplication via Arithmetic Progression <4> giới thiệu một phương thức bắt đầu để tăng vận tốc nhân ma trận và cho thấy thêm độ phức hợp của thuật tân oán mà họ cải tiến và phát triển là $mathcalO(n^2.376)$ với được review là thuật tân oán nhân ma trận nhanh 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 báo Improved bound for complexity of matrix multiplication <5> cùng cho biết họ đặt được con số $mathcalO(n^2.37369)$ lúc cải tiến với điều tra khảo sát thuật toán của Coppersmith-Winograd.

Tháng 1/2014, François Le Gall công bố bài báo Powers of Tensors và Fast Matrix Multiplication <6> thường xuyên phân tích thuật tân oán của hai bên khoa học này và giành được con số $mathcalO(n^2.3728639)$.

Vào tháng 7/2014, Virginia Vassilevska Williams trực thuộc đại học Standford chào làng bài bác báo Multiplying matrices in $mathcalO(n^2.373)$ time <7> chỉ dẫn phương pháp cách tân thuật toán thù của Coppersmith-Winograd và ra mắt độ 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 hiện tại, bọn họ đúc rút được bảng đối chiếu về độ phức tạp nhỏng 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 bên công nghệ vẫn vẫn mê mải nghiên cứu và phân tích để mang con số này về $mathcalO(n^2)$

*

Theo một comment 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 và 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 dùng cho những ma trận phệ vị hidden-constant quá lớn cùng implement phức tạp, dễ dẫn đến lỗi <8>.

Xem thêm: Api - Free Download


Cảm ơn các bạn đã theo dõi bài xích viết! những chúng ta cũng có thể follow mình bên trên Facebook để tại vị thắc mắc, hoặc thừa nhận lên tiếng về những nội dung bài viết mới.


Chuyên mục: Công nghệ