Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
复制标题
二次时间内整数矩阵乘法的确定性验证
DOI：
10.1007/978-3-319-04298-5_33
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. Wiedermann
中科院分区：
文献类型：
--
作者：
I. Korec;J. Wiedermann
设A,BandCben×n为整数矩阵。我们证明了存在一种二次时间复杂度（相对于算术运算的数量）的确定性算法来验证是否 AB=C。对于整数矩阵，该结果改进了 Freivalds 1977 年的最著名结果，该结果仅适用于随机（蒙特卡罗）算法。因此，我们设计了一种时间复杂度无法进一步提高的二次时间不确定整数和有理矩阵乘法算法。这表明任何证明确定性矩阵乘法的超二次下界的技术都必须利用不适用于非确定性情况的方法。
LetA,BandCben×nmatrices of integer numbers. We show that there is a deterministic algorithm of quadratic time complexity (w.r.t. the number of arithmetical operations) verifying whetherAB=C.For the integer matrices this result improves upon the best known result by Freivalds from 1977 that only holds for a randomized (Monte Carlo) algorithm. As a consequence, we design a quadratic time nondeterministic integer and rational matrix multiplication algorithm whose time complexity cannot be further improved. This indicates that any technique for proving a super-quadratic lower bound for deterministic matrix multiplication must exploit methods which would not work for the non-deterministic case.