关于矩阵乘法与整数卷积最佳算法运算量的估计

ESTIMATION OF TIME ABOUT THE OPTIMAL ALGORITHMS FOR MATRIX MULTIPLICATION AND INTEGER CONVOLUTION

§1.引言 [1]通过构造一个大整数然后作整数乘除法给出了用于有理数矩阵相乘的算法,运算量为O(n^2),达到了矩阵乘法复杂性下界,是最佳算法。[2]曾指出[1]中忽略了不同字长有不同运算量这一事实。但对[1]中算法复杂性未作具体讨论和质疑。最近,[3]—[4]采用类似于[1]中的大整数乘除法分别提出整数向量卷积的算法。

In this paper, we discuss the methods for estimating the number of operationsabout matrix multiplication and integer convolution. It is shown that the time of ma-trix multipliation in [1] and integer convolution in [3], [4] is no less than O(n^3log n) and O(n^2 log n), respectively, more than that of ordinary algorithms, are notoptimal.