王弘倫Wang, Hung-Lung吳羽倫Wu, Yu-Lun2023-12-082022-08-302023-12-082022https://etds.lib.ntnu.edu.tw/thesis/detail/ae513768b495cb277b0b9844dbc21781/http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/121575給定三個 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.矩陣乘法矩陣乘積校正演算法生成元matrix multiplicationmatrix productcorrectiongroup generatoretd