TY - JOUR
T1 - Correcting matrix products over the ring of integers
AU - Wu, Yu Lun
AU - Wang, Hung Lung
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
PY - 2024/8
Y1 - 2024/8
N2 - Let A, B, and C be three n×n matrices. We investigate the problem of verifying whether AB=C over the ring of integers and finding the correct product AB. Given that C is different from AB by at most k entries, we propose an algorithm that uses O(kn2+k2n) operations. Let α be the largest absolute value of an entry in A, B, and C. The integers involved in the computation are of O(n3α2).
AB - Let A, B, and C be three n×n matrices. We investigate the problem of verifying whether AB=C over the ring of integers and finding the correct product AB. Given that C is different from AB by at most k entries, we propose an algorithm that uses O(kn2+k2n) operations. Let α be the largest absolute value of an entry in A, B, and C. The integers involved in the computation are of O(n3α2).
KW - Algorithms
KW - Certifying algorithm
KW - Correction
KW - Design of algorithms
KW - Matrix multiplication
UR - http://www.scopus.com/inward/record.url?scp=85190558881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85190558881&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2024.106496
DO - 10.1016/j.ipl.2024.106496
M3 - Article
AN - SCOPUS:85190558881
SN - 0020-0190
VL - 186
JO - Information Processing Letters
JF - Information Processing Letters
M1 - 106496
ER -