Abstract
Karppa & Kaski (2019) proposed a novel type of "broken" or "opportunistic" multiplication algorithm, based on a variant of Strassen’s algorithm, 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₂(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.
We describe an alternative way to use the broken matrix multiplication algorithm to approximately compute matrix multiplication, either for realvalued matrices or Boolean matrices. 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. Asymptotically, the resulting algorithm has runtime O(n^{(3 log6)/log7} log n) ≤ O(n^2.763), a slight improvement of KarppaKaski’s algorithm.
Since the goal is to obtain new practical matrixmultiplication algorithms, these asymptotic runtime bounds are not directly useful. We estimate the runtime for our algorithm for some sample problems which are at the upper limits of practical algorithms; it appears that for these parameters, further optimizations are still needed to make our algorithm competitive.
BibTeX  Entry
@InProceedings{harris:LIPIcs.ESA.2023.57,
author = {Harris, David G.},
title = {{Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {57:157:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18710},
URN = {urn:nbn:de:0030drops187104},
doi = {10.4230/LIPIcs.ESA.2023.57},
annote = {Keywords: Matrix multiplication, Boolean matrix multiplication, Strassen’s algorithmkeyword}
}
Keywords: 

Matrix multiplication, Boolean matrix multiplication, Strassen’s algorithmkeyword 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 