Đến nội dung

Hình ảnh

Giới thiệu về thuật toán Strassen tìm tích của $2$ ma trận có kích thước $2\times 2$ với $7$ dấu nhân

2by2 7multiplications strassenalgorithm winograd shmuel winograd algorithm mitstudent eigendecomposition lu decomposition lupdecomposition

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
DOTOANNANG

DOTOANNANG

    Đại úy

  • ĐHV Toán Cao cấp
  • 1609 Bài viết

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


#2
DOTOANNANG

DOTOANNANG

    Đại úy

  • ĐHV Toán Cao cấp
  • 1609 Bài viết
Update on Wikipedia,Strassen_algorithm



Screenshot 2022-08-31 164155.png

Liệu 15 có phải là Winograd's number sau cuối ?


Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 31-08-2022 - 17:41






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: 2by2, 7multiplications, strassenalgorithm, winograd, shmuel, winograd algorithm, mitstudent, eigendecomposition, lu decomposition, lupdecomposition

0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh