2026-07-23T07:02:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18710 2024-03-06T11:02:31Z ddc:004 open_access

Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication Harris, David G. Matrix multiplication Boolean matrix multiplication Strassen’s algorithmkeyword 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 real-valued 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 Karppa-Kaski’s algorithm. Since the goal is to obtain new practical matrix-multiplication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David G. Harris 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.57 urn:nbn:de:0030-drops-187104 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.57 eng https://creativecommons.org/licenses/by/4.0/legalcode