A (5/2)n-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication
Lists
Only you see this
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...