A (5/2)n-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication

Markus BläserSTACS 2001 · OpenReview

Abstract

We prove a lower bound of 5/2n 2-3n for the multiplicative complexity of n × n-matrix multiplication over arbitrary fields. More general, we show that for any finite dimensional semisimple algebra A with unity, the multiplicative complexity of the multiplication in A is bounded from below by 5/2 dim A - 3(n 1 + ⋯ + n t) if the decomposition of A ≅= A1 x ... x At into simple algebras Aτ ≅ Dτnτ×nτ contains only noncommutative factors, that is, the division algebra Dτ is noncommutative or nτ ≥ 2.
BibTeX
@inproceedings{blaser2001n,
  author = {Markus Bläser},
  title = {{A (5/2)n-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication}},
  booktitle = {STACS},
  year = {2001},
  url = {https://openreview.net/forum?id=cxW2hr3W4j},
}

Loading related content...

Figure