3 ms·
I feel the other answers you got do not directly answer your question for the following reason. In practice, I believe it is Strassen's algorithm that is used
by davidgrenier 5y ago
I feel the other answers you got do not directly answer your question for the following reason.
In practice, I believe it is Strassen's algorithm that is used for very large matrix multiplication. Strassen's algorithm improves on both the number of multiplications of scalars as well as addition of scalars which both ends up bound by O(n^(lg 7)).
This is because Strassen's algorithm replaces a single large conventional matrix multiplication consisting of n^3 multiplications and n^3-n^2 additions with 7 recursive application of Strassen's multiplication on matrices of size n/2 along with 15 addition of matrices of size n/2.
The number of additions in a matrix addition is n^2 for a matrix of size n. Thus Strassen's requires 7 recursive calls as well as 15(n/2)^2 additions of scalars.
You win on both fronts if the matrices are sufficiently large and you default to conventional matrix multiplication on a recursive call below a certain threshold.