Correcting matrix products over the ring of integers
| Autor: | Wu, Yu-Lun, Wang, Hung-Lung |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Information Processing Letters 186 (2024), 106496 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.ipl.2024.106496 |
| Popis: | Let $A$, $B$, and $C$ be three $n\times 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(\sqrt{k}n^2+k^2n)$ operations. Let $\alpha$ be the largest absolute value of an entry in $A$, $B$, and $C$. The integers involved in the computation are of $O(n^3\alpha^2)$. Comment: 10 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|