Skip to main content
3 of 4
Copy edited (e.g. ref. <https://en.wiktionary.org/wiki/Boolean#Adjective>). Jeopardy compliance.

Why is fast matrix multiplication impractical?

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?

Jiawei Ren
  • 279
  • 2
  • 5