Improved algorithms for Boolean matrix multiplication via opportunistic matrix multiplication
share
Karppa Kaski (2019) proposed a novel type of "broken" or "opportunistic" multiplication algorithm, based on a variant of Strassen's alkgorithm, and used this to develop new algorithms for Boolean matrix multiplication, among other tasks. For instance, their algorithm can compute Boolean matrix multiplication in O(n^log_2(6 + 6/7)log n) = O(n^2.778) time. While faster matrix multiplication algorithms exist asymptotically, in practice most such algorithms are infeasible for practical problems. Their opportunistic algorithm is a slight variant of Strassen's algorithm, so hopefully it should yield practical as well as asymptotic improvements to it. In this note, we describe a more efficient way to use the broken matrix multiplication algorithm to solve Boolean matrix multiplication. In brief, instead of running multiple iterations of the broken algorithm on the original input matrix, we form a new larger matrix by sampling and run a single iteration of the broken algorithm on it. The resulting algorithm has runtime O( n^3 log 6/log 7 (log n)^log 6/log 7) ≤ O(n^2.763). We also describe an extension to witnessing Boolean matrix multiplication, as well as extensions to non-square matrices. The new algorithm is simple and has reasonable constants. We hope it may lead to improved practical algorithms
READ FULL TEXT