在整數環中關於矩陣乘法的校正演算法

Abstract

給定三個 n × n 的整數矩陣 A, B, 和 C，其中 C 與 A × B 的乘積有最多 k 個元素相異。我們研究如何有效率的修正整數矩陣乘積的錯誤，並找到了時間複雜度為 O(k^0.5 × n^2) 的決定性演算法。另外，在執行演算法的過程中所須要處理的數字最大值為 O(n^2α^2 + nα)，其中 α 是 A, B, 和 C 的元素的最大值。

Given three n × n matrices A, B, and C with C containing at most k entries differfrom A × B, we investigate how to find the correct matrix products over the ring overintegers efficiently and provide a deterministic algorithm running in O(k^0.5 × n^2) time. In addition, the values need to manipulate during the algorithm are O(n^2 × α^2 + n^α), where α is the largest value of entries in A, B, and C.