Deterministic Verification of Integer Matrix Multiplication in Quadratic Time

Autoři: prof. RNDr. Jiří Wiedermann, DSc.
Rok vydání: 2014
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: SOFSEM 2014. Theory and Practice of Computer Science
Projekty: NoSCoM: nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení
Bibliografická citace: KOREC, I., WIEDERMANN, Jiří. Deterministic Verification of Integer Matrix Multiplication in Quadratic Time. In: GEFFERT, V., PRENEEL, B., ROVAN, B., ŠTULLER, J., TJOA, A.M., eds. SOFSEM 2014. Theory and Practice of Computer Science. Cham: Springer, 2014, S. 375-382. Lecture Notes in Computer Science, 8327. ISBN 978-3-319-04297-8. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-319-04298-5_33
DOI: 10.1007/978-3-319-04298-5_33
ID: 425985

Abstrakt

Let A, B and C be n x n matrices of integer numbers. We show that there is a deterministic algorithm of quadratic time complexity (w.r.t. the number of arithmetical operations) verifying whether AB=C. For the integer matrices this result improves upon the best known result by Freivalds from 1977 that only holds for a randomized (Monte Carlo) algorithm. As a consequence, we design a quadratic time nondeterministic integer and rational matrix multiplication algorithm whose time complexity cannot be further improved. This indicates that any technique for proving a super-quadratic lower bound for deterministic matrix multiplication must exploit methods which would not work for the non-deterministic case.