The Number of the Beast : Reducing Additions in Fast Matrix Multiplication Algorithms for Dimensions up to 666
Mårtensson, Erik LU
and Stankovski Wagner, Paul
LU
(2025)
p.47-60
- Abstract
- While a naive algorithm for multiplying two 2 × 2 matrices requires eight multiplications and four additions, Strassen showed how to compute the same matrix product using seven multiplications and 18 additions. Winograd reduced the number of additions to 15, which was assumed to be optimal. However, by introducing a change of basis, Karstadt and Schwartz showed how to lower the number of additions to 12, which they further showed to be optimal within this generalized Karstadt-Schwartz (KS) framework. Since the cost of the change of basis is smaller than one addition (per each recursive level), it is disregarded in this cost metric.
In this work we present improved methods for classical optimization of the number of additions in... (More) - While a naive algorithm for multiplying two 2 × 2 matrices requires eight multiplications and four additions, Strassen showed how to compute the same matrix product using seven multiplications and 18 additions. Winograd reduced the number of additions to 15, which was assumed to be optimal. However, by introducing a change of basis, Karstadt and Schwartz showed how to lower the number of additions to 12, which they further showed to be optimal within this generalized Karstadt-Schwartz (KS) framework. Since the cost of the change of basis is smaller than one addition (per each recursive level), it is disregarded in this cost metric.
In this work we present improved methods for classical optimization of the number of additions in Strassen-type matrix multiplication schemes for larger matrix sizes, and without any change of basis.
We find specific examples where our methods beat the best instances found within the KS framework, the most impressive one being Laderman’s algorithm for multiplying 3 × 3 matrices, which we reduce from the naive 98 additions to 62, compared to 74 in the KS framework. We indicate that our approach performs better compared to previous work within the KS framework, as the matrix dimensions increase.
We additionally apply our algorithms to another reference set of algorithms due to Moosbauer and Kauers for which we do not have results in the KS framework as a comparison. For parameters (n, m, k ), when multiplying an (n × m ) matrix with an (m × k ) matrix, the schoolbook algorithm uses nk (m — 1) additions. Using the reference set of algorithms we find that our algorithm leads to an optimized number of additions of roughly cnk (m — 1), where c is a small constant which is independent of the dimensions.
We further provide concrete and practical implementations of our methods that are very efficient for dimensions including (and surpassing) the 666 limit, i.e. (n, m, k ) = (6, 6, 6), in our reference set of fast multiplication algorithms. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/b54757d4-d957-44b0-9faf-875735558313
- author
- Mårtensson, Erik
LU
and Stankovski Wagner, Paul
LU
- organization
- publishing date
- 2025
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA)
- pages
- 47 - 60
- publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/1.9781611978759.4
- language
- English
- LU publication?
- yes
- id
- b54757d4-d957-44b0-9faf-875735558313
- alternative location
- https://eprint.iacr.org/2024/2063
- date added to LUP
- 2025-10-30 14:05:50
- date last changed
- 2025-11-03 11:35:51
@inproceedings{b54757d4-d957-44b0-9faf-875735558313,
abstract = {{While a naive algorithm for multiplying two 2 × 2 matrices requires eight multiplications and four additions, Strassen showed how to compute the same matrix product using seven multiplications and 18 additions. Winograd reduced the number of additions to 15, which was assumed to be optimal. However, by introducing a change of basis, Karstadt and Schwartz showed how to lower the number of additions to 12, which they further showed to be optimal within this generalized Karstadt-Schwartz (KS) framework. Since the cost of the change of basis is smaller than one addition (per each recursive level), it is disregarded in this cost metric.<br/><br/>In this work we present improved methods for classical optimization of the number of additions in Strassen-type matrix multiplication schemes for larger matrix sizes, and without any change of basis.<br/><br/>We find specific examples where our methods beat the best instances found within the KS framework, the most impressive one being Laderman’s algorithm for multiplying 3 × 3 matrices, which we reduce from the naive 98 additions to 62, compared to 74 in the KS framework. We indicate that our approach performs better compared to previous work within the KS framework, as the matrix dimensions increase.<br/><br/>We additionally apply our algorithms to another reference set of algorithms due to Moosbauer and Kauers for which we do not have results in the KS framework as a comparison. For parameters (n, m, k ), when multiplying an (n × m ) matrix with an (m × k ) matrix, the schoolbook algorithm uses nk (m — 1) additions. Using the reference set of algorithms we find that our algorithm leads to an optimized number of additions of roughly cnk (m — 1), where c is a small constant which is independent of the dimensions.<br/><br/>We further provide concrete and practical implementations of our methods that are very efficient for dimensions including (and surpassing) the 666 limit, i.e. (n, m, k ) = (6, 6, 6), in our reference set of fast multiplication algorithms.}},
author = {{Mårtensson, Erik and Stankovski Wagner, Paul}},
booktitle = {{2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA)}},
language = {{eng}},
pages = {{47--60}},
publisher = {{Society for Industrial and Applied Mathematics}},
title = {{The Number of the Beast : Reducing Additions in Fast Matrix Multiplication Algorithms for Dimensions up to 666}},
url = {{http://dx.doi.org/10.1137/1.9781611978759.4}},
doi = {{10.1137/1.9781611978759.4}},
year = {{2025}},
}