Correcting matrix products over the ring of integers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913321627680768 |
|---|---|
| author | Wu, Yu-Lun Wang, Hung-Lung |
| author_facet | Wu, Yu-Lun Wang, Hung-Lung |
| contents | 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 $α$ be the largest absolute value of an entry in $A$, $B$, and $C$. The integers involved in the computation are of $O(n^3α^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12513 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Correcting matrix products over the ring of integers Wu, Yu-Lun Wang, Hung-Lung Data Structures and Algorithms Discrete Mathematics 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 $α$ be the largest absolute value of an entry in $A$, $B$, and $C$. The integers involved in the computation are of $O(n^3α^2)$. |
| title | Correcting matrix products over the ring of integers |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2307.12513 |