{"ID":2842469,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10786","arxiv_id":"2511.10786","title":"Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search","abstract":"We give explicit low-rank bilinear non-commutative schemes for multiplying structured $n \\times n$ matrices with $2 \\leq n \\leq 5$, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over $\\mathbb{F}_2$ or $\\mathbb{F}_3$ and lifted to $\\mathbb{Z}$ or $\\mathbb{Q}$. Using a flip graph search over tensor decompositions, we derive schemes for general, upper-triangular, lower-triangular, symmetric, and skew-symmetric inputs, as well as products of a structured matrix with its transpose. These schemes improve asymptotic constants for 13 of 15 structured formats. In particular, we obtain $4 \\times 4$ rank-34 schemes for both multiplying a general matrix by its transpose and an upper-triangular matrix by a general matrix, improving the asymptotic factor from 8/13 (0.615) to 22/37 (0.595). Additionally, using $\\mathbb{F}_3$ flip graphs, we discover schemes over $\\mathbb{Q}$ that fundamentally require the inverse of 2, including a $2 \\times 2$ symmetric-symmetric multiplication of rank 5 and a $3 \\times 3$ skew-symmetric-general multiplication of rank 14 (improving upon AlphaTensor's 15).","short_abstract":"We give explicit low-rank bilinear non-commutative schemes for multiplying structured $n \\times n$ matrices with $2 \\leq n \\leq 5$, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over $\\mathbb{F}_2$ or $\\mathbb{F}_3$ and...","url_abs":"https://arxiv.org/abs/2511.10786","url_pdf":"https://arxiv.org/pdf/2511.10786v2","authors":"[\"Kirill Khoruzhii\",\"Patrick Gelß\",\"Sebastian Pokutta\"]","published":"2025-11-13T20:19:05Z","proceeding":"cs.SC","tasks":"[\"cs.SC\",\"cs.DS\"]","methods":"[]","has_code":false}