Exploring Commutative Matrix Multiplication Schemes via Flip Graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916812976816128 |
|---|---|
| author | Wood, Isaac |
| author_facet | Wood, Isaac |
| contents | We explore new approaches for finding matrix multiplication algorithms in the commutative setting by adapting the flip graph technique: a method previously shown to be effective for discovering fast algorithms in the non-commutative case. While an earlier attempt to apply flip graphs to commutative algorithms saw limited success, we overcome both theoretical and practical obstacles using two strategies: one inspired by Marakov's algorithm to multiply 3x3 matrices, in which we construct a commutative tensor and approximate its rank using the standard flip graph; and a second that introduces a fully commutative variant of the flip graph defined via a quotient tensor space. We also present a hybrid method that combines the strengths of both. Across all matrix sizes up to 5x5, these methods recover the best known bounds on the number of multiplications and allow for a comparison of their efficiency and efficacy. Although no new improvements are found, our results demonstrate strong potential for these techniques at larger scales. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22113 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exploring Commutative Matrix Multiplication Schemes via Flip Graphs Wood, Isaac Symbolic Computation We explore new approaches for finding matrix multiplication algorithms in the commutative setting by adapting the flip graph technique: a method previously shown to be effective for discovering fast algorithms in the non-commutative case. While an earlier attempt to apply flip graphs to commutative algorithms saw limited success, we overcome both theoretical and practical obstacles using two strategies: one inspired by Marakov's algorithm to multiply 3x3 matrices, in which we construct a commutative tensor and approximate its rank using the standard flip graph; and a second that introduces a fully commutative variant of the flip graph defined via a quotient tensor space. We also present a hybrid method that combines the strengths of both. Across all matrix sizes up to 5x5, these methods recover the best known bounds on the number of multiplications and allow for a comparison of their efficiency and efficacy. Although no new improvements are found, our results demonstrate strong potential for these techniques at larger scales. |
| title | Exploring Commutative Matrix Multiplication Schemes via Flip Graphs |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2506.22113 |