Cách Nhân 2 Ma Trận Và Ma Trận Nghịch Đảo, Lý Thuyết Sơ Cấp Về Ma Trận

Ở bài trước, chúng ta có đề cập tới việc ứng dụng phép nhân ma trận để tính số Fibonacci một cách hiệu quả. Vậy thuật toán nhân ma trận mà chúng ta sử dụng ở trong bài viết đã thực sự hiệu quả hay chưa?

Trong quá trình tìm hiểu để viết bài này thì mình phát hiện ra một điều khá là thú vị, đó là có rất nhiều thuật toán để thực hiện nhân ma trận, tuy nhiên ngành khoa học máy tính vẫn chưa tìm ra được câu trả lời cho câu hỏi: Đâu là thuật toán tối ưu để thực hiện phép nhân ma trận? <1>

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

Nhắc lại một chút kiến thức toán học về phương pháp nhân 2 ma trận $A$ và $B$, điều kiện đầu tiên để có thể thực hiện phép nhân này là khi số cột của ma trận $A$ bằng số hàng của ma trận $B$.

Với USD A $ là một ma trận có kích cỡ USD n \ times m USD và USD B USD là một ma trận size USD m \ times p USD thì tích của USD A \ times B USD sẽ là một ma trận USD n \ times p USD được tính bằng cách sau :

$$\left( \begin{array}{ccc}a & b \\c & d \end{array} \right) \times\left( \begin{array}{ccc}x \\y\end{array} \right)=\left( \begin{array}{ccc}ax + by \\cx + dy\end{array} \right)$$Hình sau mô tả cách tính một 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 thành phần trong một hàng của ma trận USD A $ với những thành phần trong cột tương ứng trong ma trận USD B USDUSD USD _ { i, j } = A_ { i, 1 } B_ { 1, j } + A_ { i, 2 } B_ { 2, j } + \ ldots + A_ { i, n } B_ { n, j } USD USD Hay viết cho gọn hơn như sau :

$$_{i,j} = \displaystyle\sum_{r=1}^{n} A_{i,r}B_{r,j}$$
Noob Question: Cái dấu hình zích zắc $\sum$ kia là gì vậy???

Chửi trước: Ôi trời, đây là cái dấu tính tổng mà cũng không biết à? Về học lại toán cấp 3 hay năm nhất ĐH gì đó đi nhé! Tốn thời gian bm!!Đáp sau: Cái dấu zích zắc đó là kí hiệu phép tính tổng, có thể hình dung kí hiệu này giống như một vòng lặp for trong thực hiện phép tính cộng, số $n$ ở trên đỉnh chỉ tổng số lần lặp cần thiết, số $r = 1$ ở dưới cho ta biết giá trị nào cần chạy trong vòng lặp for và bắt đầu chạy từ giá trị bao nhiêu. Biểu thức đi liền sau kí hiệu $\sum$ cho ta biết phép cộng các giá trị nào sẽ được thực hiện bên trong vòng lặp đó.
Tiếp theo, hãy cùng xem chúng ta có những cách nào để implement thuật toán này trên máy tính.

The naive algorithm

Naive Algorithm là từ dùng để chỉ một thuật toán đơn thuần nhất được suy luận một cách ” ngây thơ ” bằng cách giải quyết và xử lý thường thì, ví dụ như tìm kiếm tuần từ ( sequential / linear search )Trong trường hợp này, tất cả chúng ta thường implement thuật toán nhân ma trận bằng cách vận dụng đúng mực công thức từ định nghĩa toán học của nó, sử dụng vòng lặp, như sau :

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

1: Khởi tạo ma trận C có kích thước $n \times p$ 2: For i từ $1 \rightarrow n$:3:  For j từ $1 \rightarrow p$:4:   Gán $sum = 0$5:   For r từ $1 \rightarrow m$:6:    Gán $sum = sum + A_{i,r} \times B_{r,j}$7:   Gán $C_{i,j} = sum$

Output : Ma trận C kích cỡ USD n \ times p USD
Tại sao lại gọi là naive algorithm ( ngây thơ ) ? đó là vì nó rất dễ implement, chỉ cần đi theo lối tâm lý thường thì, bỏ lỡ hết mọi yếu tố như độ phức tạp, sự tối ưu …Độ phức tạp của thuật toán trên là USD \ mathcal { O } ( nmp ) USD, trong trường hợp tổng thể những ma trận đều là ma trận vuông USD n \ times n USD thì độ phức tạp của thuật toán sẽ là USD \ mathcal { O } ( n ^ { 3 } ) USD

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

Vào năm 1969, Volker Strassen – lúc đó đang là sinh viên tại MIT – cho rằng USD \ mathcal { O } ( n ^ { 3 } ) USD chưa phải là số lượng tối ưu cho phép nhân ma trận, và đề xuất kiến nghị một thuật toán mới có thời hạn chạy chỉ nhanh hơn một chút ít nhưng về sau đã kéo theo rất nhiều nhà khoa học lao vào liên tục điều tra và nghiên cứu và cho đến thời gian giờ đây, đã có rất nhiều chiêu thức mới được đưa ra như thể thuật toán Coppersmith-Winograd ( sẽ nói ở phần sau ), hoặc những giải pháp tiếp cận bằng lập trình song song trên nhiều máy tính / nhiều core, … Điểm mê hoặc là Strassen nghĩ ra thuật toán này vì nó là bài tập trong một lớp mà ông đang học < 2 > .Xét lại thuật toán naive ở phần trước, để tính một thành phần USD C_ { i, j } USD của ma trận tích USD C USD, ta phải triển khai hai phép nhân và một phép cộng. Suy ra nếu USD C USD là một ma trận vuông có size USD 2 \ times 2 USD, thì để tính bốn thành phần của USD C USD, yên cầu phải thực thi USD 2 \ times 2 ^ { 2 } = 2 ^ { 3 } = 8 USD phép nhân và USD ( 2 – 1 ) \ times 2 ^ { 2 } = 4 USD phép cộng. Nếu USD A $ và USD B USD là những ma trận cấp USD n USD ( tức là những ma trận USD n \ times n USD ) thì tất cả chúng ta cần phải triển khai USD n ^ { 3 } USD phép nhân và USD ( n – 1 ) \ times n ^ { 2 } USD phép cộng .

Ý tưởng thuật toán của Strassen <3> là áp dụng chia để trị để giải quyết bài toán theo hướng của giải thuật cơ bản trên. Cụ thể là: với mỗi ma trận vuông A, B, C có kích thước $n \times n$, chúng ta chia chúng thành 4 ma trận con, và biểu diễn tích $A \times B = C$ theo các ma trận con đó:

Trong đó :USD USD \ begin { align } C_ { 1,1 } và = A_ { 1,1 } B_ { 1,1 } + A_ { 1,2 } B_ { 2,1 } \ \ C_ { 1,2 } và = A_ { 1,1 } B_ { 1,2 } + A_ { 1,2 } B_ { 2,2 } \ \ C_ { 2,1 } và = A_ { 2,1 } B_ { 1,1 } + A_ { 2,2 } B_ { 2,1 } \ \ C_ { 2,2 } và = A_ { 2,1 } B_ { 1,2 } + A_ { 2,2 } B_ { 2,2 } \ end { align } USD USD Tuy nhiên với cách nghiên cứu và phân tích này thì tất cả chúng ta vẫn cần 8 phép nhân để tính ra ma trận USD C USD. Đây là phần quan trọng nhất của yếu tố .Xem thêm : Cách Từ Bỏ Facebook Chỉ Mất 10 Giây, 8 Lợi Ích Có Được Ngay Khi Bạn Từ Bỏ FacebookChúng ta định nghĩa ra những ma trận USD M USD mới như sau :USD USD \ begin { align } M_ { 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 } 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 } ) \ end { align } USD USD Và màn biểu diễn lại những thành phần của USD C USD theo USD M USD như sau :USD USD \ begin { align } C_ { 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_ { 6 } \ end { align } USD USD Bằng cách này, tất cả chúng ta chỉ cần 7 phép nhân ( mỗi USD M USD một phép nhân ) thay vì 8 như giải pháp cũ .Thực hiện đệ quy quy trình trên cho đến khi ma trận có cấp hai .Độ phức tạp của thuật toán Strassen là USD \ mathcal { O } ( n ^ { \ log { 7 } } ) \ approx \ mathcal { O } ( n ^ { 2.807 } ) USDĐồ thị sau so sánh sự khác nhau về độ phức tạp của hai thuật toán vừa bàn :

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

Dựa trên phát minh của Strassen, vào tháng 5/1987, hai nhà khoa học Don Coppersmith và Shmuel Winograd công bố bài báo Matrix Multiplication via Arithmetic Progression <4> giới thiệu một phương pháp mới để tăng tốc độ nhân ma trận và cho biết độ phức tạp của thuật toán mà họ phát triển là $\mathcal{O}(n^{2.376})$ và được đánh giá là thuật toán nhân ma trận nhanh nhất tính tới thời điểm đó.

Vào tháng 3/2013, A. M. Davie và A. J. Stothers công bố bài báo Improved bound for complexity of matrix multiplication <5> và cho biết họ đặt được con số $\mathcal{O}(n^{2.37369})$ khi cải tiến và 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 and Fast Matrix Multiplication <6> tiếp tục phân tích thuật toán của hai nhà khoa học này và đạt được con số $\mathcal{O}(n^{2.3728639})$.

Vào tháng 7/2014, Virginia Vassilevska Williams thuộc đại học Standford công bố bài báo Multiplying matrices in $\mathcal{O}(n^{2.373})$ time <7> đưa ra phương pháp cải tiến thuật toán của Coppersmith-Winograd và công bố độ phức tạp là $\mathcal{O}(n^{2.372873})$.

Kết luận

Tổng kết lại, với những thuật toán hiện tại, tất cả chúng ta rút ra được bảng so sánh về độ phức tạp như sau :

Và các nhà khoa học vẫn đang miệt mài nghiên cứu để đưa con số này về $\mathcal{O}(n^{2})$

Theo một phản hồi của giáo sư Ngô Quang Hưng trên Procul, thì những thuật toán của Strassen và Coppersmith-Winograd chỉ mang giá trị kim chỉ nan là chính, trong trong thực tiễn ít ai dùng cho những ma trận lớn vì hidden-constant quá lớn và implement phức tạp, dễ bị lỗi < 8 > .
Cảm ơn bạn đã theo dõi bài viết ! những bạn hoàn toàn có thể follow mình trên Facebook để đặt câu hỏi, hoặc nhận thông tin về những bài viết mới .

Source: https://laodongdongnai.vn
Category: Người Lao Động