License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.57
URN: urn:nbn:de:0030-drops-187104
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18710/
Go to the corresponding LIPIcs Volume Portal

Harris, David G.

Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication

pdf-format:
LIPIcs-ESA-2023-57.pdf (0.7 MB)

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 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.

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:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18710},
  URN =		{urn:nbn:de:0030-drops-187104},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI