I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication.
I read some content saying fast matrix multiplications are impractical because of large constant factors. These constant factors are because of algebraic techniques.
I do not understand where these constant factors come from. Some references also say $O(n^{3-\omega})$ may become practical when $O(n^{3-\omega})$ combinatorial algorithm exists. What is the large constant factor and combinatorial algorithm for Boolean matrix multiplication?
Best Answer
Matrix multiplication based on Strassen's algorithm is in $O(n^{\log(7)/\log(2)})$ and is quite practical. As far as I am aware, for any exponent $\omega<\log(7)/\log(2)$ the corresponding algorithm is impractical, indeed because of huge constants.