Giới thiệu. Năm $1969,$ Volker Strassen, nhà toán học người Đức, đã phát triển $1$ thuật toán tìm tích của $2$ ma trận có kích thước $2\times 2$ chỉ cần $7$ dấu nhân thay vì $8.$ Lúc này đây, chúng ta đều hiểu rằng thuật toán nhân $2$ ma trận có kích thước $n\times n$ thậm chí sẽ có độ phức tạp nhỏ hơn $\mathcal{O}\left ( n^{3} \right ).$ Đến nay việc tìm ra hằng số tốt nhất đó $\omega< 2.372873$ vẫn chưa có dấu hiệu dừng lại (xem thêm tại_ https://people.csail...atrixmult-f.pdf)..
Cách thông thường nhất. Phép nhân $2$ ma trận $A, B$ có kích thước $2\times 2$ với tích $C$
$$\begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix}\begin{bmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{bmatrix}= \begin{bmatrix} C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix}$$
được biểu diễn như sau
$$\begin{matrix} C_{11}= A_{11}B_{11}+ A_{12}B_{21}\\ C_{12}= A_{11}B_{12}+ A_{12}B_{22}\\ C_{21}= A_{21}B_{11}+ A_{22}B_{21}\\ C_{22}= A_{21}B_{12}+ A_{22}B_{22} \end{matrix}$$
với $4$ dấu cộng, và $8$ dấu nhân.
Thuật toán Strassen. Có được
$$\begin{array}{l} C_{11}= M_{1}+ M_{4}- M_{5}+ M_{7}\\ C_{12}= M_{3}+ M_{5}\\ C_{21}= M_{2}+ M_{4}\\ C_{22}= M_{1}- M_{2}+ M_{3}+ M_{6} \end{array}$$
được biểu diễn như sau
$$\begin{array}{l} M_{1}:=\left ( A_{11}+ A_{22} \right )\left ( B_{11}+ B_{22} \right )\\ M_{2}:=\left ( A_{21}+ A_{22} \right )B_{11}\\ M_{3}:=A_{11}\left ( B_{12}- B_{22} \right )\\ M_{4}:=A_{22}\left ( B_{21}- B_{11} \right )\\ M_{5}:=\left ( A_{11}+ A_{12} \right )B_{22}\\ M_{6}:=\left ( A_{21}- A_{11} \right )\left ( B_{11}+ B_{12} \right )\\ M_{7}:=\left ( A_{12}- A_{22} \right )\left ( B_{21}+ B_{22} \right ) \end{array}$$
với $18$ dấu cộng, và $7$ dấu nhân.
Thuật toán Shmuel Winograd (cải tiến từ thuật toán của Strassen). Có được
$$\begin{array}{l} C_{11}= M_{2}+ M_{3}\\ C_{12}= T_{1}+ M_{5}+ M_{6}\\ C_{21}= T_{2}- M_{7}\\ C_{22}= T_{2}+ M_{5} \end{array}$$
được biểu diễn như sau
$$\begin{array}{llll} S_{1}:=A_{21}+ A_{22} & \quad & \quad & S_{2}:=S_{1}- A_{11}\\ S_{3}:=B_{12}- B_{11} & \quad & \quad & S_{4}:=B_{22}- S_{3}\\ M_{1}:=S_{2}S_{4} & \quad & \quad & M_{2}:=A_{11}B_{11}\\ M_{3}:=A_{12}B_{21} & \quad & \quad & M_{4}:=\left ( A_{11}- A_{21} \right )\left ( B_{22}- B_{12} \right )\\ M_{5}:=S_{1}S_{3} & \quad & \quad & M_{6}:=\left ( A_{12}- S_{2} \right )B_{22}\\ M_{7}:=A_{22}\left ( S_{4}- B_{21} \right ) & \quad & \quad & \quad\\ T_{1}:=M_{1}+ M_{2} & \quad & \quad & T_{2}:=T_{1}+ M_{4} \end{array}$$
với $17$ dấu cộng, và $7$ dấu nhân.
Nhận xét. Với các ma trận có kích thước lớn, hiệu quả của việc giảm độ phức tạp với dấu nhân sẽ rõ ràng hơn với dấu cộng.
Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 03-09-2021 - 15:37