Strassen's method to multiply two matrices runs in subcubic time

Jan Verschelde
Jan Verschelde
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 بـار بازدید شده
... بیشتر