Powers of tensors and fast matrix multiplication

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computation, 1990] and obtain the upper bound ω

• MO
  Ministry of Education, Culture, Sports, Science and Technology

  Award: 24106009
• JS
  Japan Society for the Promotion of Science

  Award: 24700005