| 关于矩阵乘法与整数卷积最佳算法运算量的估计 |
| |
| 引用本文： | 成礼智,曾泳泓.关于矩阵乘法与整数卷积最佳算法运算量的估计[J].计算数学,1993,15(3):342-345. |
| |
| 作者姓名： | 成礼智 曾泳泓 |
| |
| 作者单位： | 国防科技大学
(成礼智)，国防科技大学(曾泳泓) |
| |
| 摘 要： | §1.引言 1]通过构造一个大整数然后作整数乘除法给出了用于有理数矩阵相乘的算法,运算量为O(n~2),达到了矩阵乘法复杂性下界,是最佳算法。2]曾指出1]中忽略了不同字长有不同运算量这一事实。但对1]中算法复杂性未作具体讨论和质疑。最近,3]—4]采用类似于1]中的大整数乘除法分别提出整数向量卷积的算法,并认为运算量级为
|
| 关 键 词： | 矩阵 乘法 整数卷积 最佳算法 |
ESTIMATION OF TIME ABOUT THE OPTIMAL ALGORITHMS FOR MATRIX MULTIPLICATION AND INTEGER CONVOLUTION |
| |
| Institution: | Cheng Li-zhi;Zeng Yong-hong National University of Defense Technology |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《计算数学》浏览原始摘要信息 |
| 点击此处可从《计算数学》下载免费的PDF全文 |
|
