A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication
复制标题
n×n 矩阵乘法的乘法复杂度的 (5/2)n2-下界
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
M. Bläser
中科院分区：
文献类型：
--
作者：
M. Bläser
证明了任意域上n × n矩阵乘法的乘法复杂度的下界为5/2n2 - 3n。更一般地，我们证明了对于任意具有单位的有限维半简单代数A， A中乘法的乘法复杂度从下以5/2 dim A - 3(n1 +…+ nt)，如果分解A × A1 ×…× At化为简单代数AΤ = DΤnΤ×nΤ只包含非交换因子，即除法代数DΤ为非交换或nΤ≥2。
We prove a lower bound of 5/2n2 - 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(n1 + ... + nt) if the decomposition of A ≅ A1 × ... × At into simple algebras AΤ ≅ DΤnΤ×nΤ contains only noncommutative factors, that is, the division algebra DΤ is noncommutative or nΤ ≥ 2.