Strassen's method to multiply two matrices runs in subcubic time
83 بار بازدید -
2 هفته پیش
-
The straightforward algorithm to multiply
The straightforward algorithm to multiply two matrices of size n has a running time proportional to n^3, a cubic in n. As follows from the application of the master method, the direct application of divide and conquer does not improve the cubic time. Instead of 8 multiplications of matrices half the input size, Strassen's method reduces this to 7 multiplications and a constant number of matrix additions. Then the subcubic bound on the running time follows from the application of the master method.
2 هفته پیش
در تاریخ 1403/04/09 منتشر شده
است.
83
بـار بازدید شده