Correcting matrix products over the ring of integers

Yu Lun Wu; Hung Lung Wang

doi:10.1016/j.ipl.2024.106496

Correcting matrix products over the ring of integers

Yu Lun Wu
, Hung Lung Wang^*

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

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(kn²+k²n) operations. Let α be the largest absolute value of an entry in A, B, and C. The integers involved in the computation are of O(n³α²).

Original language	English
Article number	106496
Journal	Information Processing Letters
Volume	186
DOIs	https://doi.org/10.1016/j.ipl.2024.106496
Publication status	Published - 2024 Aug

Keywords

Algorithms
Certifying algorithm
Correction
Design of algorithms
Matrix multiplication

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2024.106496

Cite this

@article{9eab6c15ae5c4d5c92695b4b253a2489,

title = "Correcting matrix products over the ring of integers",

abstract = "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).",

keywords = "Algorithms, Certifying algorithm, Correction, Design of algorithms, Matrix multiplication",

author = "Wu, \{Yu Lun\} and Wang, \{Hung Lung\}",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = aug,

doi = "10.1016/j.ipl.2024.106496",

language = "English",

volume = "186",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Correcting matrix products over the ring of integers

AU - Wu, Yu Lun

AU - Wang, Hung Lung

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 - https://www.scopus.com/pages/publications/85190558881

UR - https://www.scopus.com/pages/publications/85190558881#tab=citedBy

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 -

Correcting matrix products over the ring of integers

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this