Polynomials and the exponent of matrix multiplication
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 Other

 View All

Overview
abstract

© 2018 London Mathematical Society The exponent of matrix multiplication is the smallest constant ω such that two n×n matrices may be multiplied by performing O(n ω+ϵ ) arithmetic operations for every ϵ>0. Determining the constant ω is a central question in both computer science and mathematics. Strassen [Linear Algebra Appl. 52/53 (1983) 645–685] showed that ω is also governed by the tensor rank of the matrix multiplication tensor. We define certain symmetric tensors, that is, cubic polynomials, and our main result is that their symmetric rank also grows with the same exponent ω, so that ω can be computed in the symmetric setting, where it may be easier to determine. In particular, we study the symmetrized matrix multiplication tensor sM ‹n› defined on an n×n matrix A by sM ‹n› (A)=trace(A 3 ). The use of polynomials enables the introduction of additional techniques from algebraic geometry in the study of the matrix multiplication exponent ω.
altmetric score
author list (cited authors)

Chiantini, L., Hauenstein, J. D., Ikenmeyer, C., Landsberg, J. M., & Ottaviani, G.
citation count
publication date
publisher
published in
Research
keywords

68q17, 14n05, 14q20, 15a69

Math.ag
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue
Other
URL

http://dx.doi.org/10.1112/blms.12147