On the complexity of integer matrix multiplication
On the complexity of integer matrix multiplication
复制标题
关于整数矩阵乘法的复杂度
DOI：
10.1016/j.jsc.2017.11.001
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Hoeven
中科院分区：
文献类型：
--
作者：
David Harvey;J. Hoeven
令 M (n) 表示 n 位整数相乘的位复杂度，让 ωε(2, 3] 为矩阵乘法的指数，让 lg⁎ n 为迭代对数。假设 log d= O (n) 并且 M (n)/(n log n) 递增，我们证明具有 n 位整数项的 d× d 矩阵可以在 O 中相乘(d 2 M (n)+ d ω n 2 O (lg⁎ n− lg⁎ d) M (lg d)/lg d) 位运算特别是，如果 n 比 d 大，比如 d= O (log n)，则复杂度仅为 O (d 2 M (n))。
Let M (n) denote the bit complexity of multiplying n-bit integers, let ω∈(2, 3] be an exponent for matrix multiplication, and let lg⁎ n be the iterated logarithm. Assuming that log d= O (n) and that M (n)/(n log n) is increasing, we prove that d× d matrices with n-bit integer entries may be multiplied in O (d 2 M (n)+ d ω n 2 O (lg⁎ n− lg⁎ d) M (lg d)/lg d) bit operations. In particular, if n is large compared to d, say d= O (log n), then the complexity is only O (d 2 M (n)).