Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 22.4.2014 |
| Speaker: | Jiří Wiedermann, Ústav Informatiky, AV ČR |
| Title: | Deterministic verification of integer matrix multiplication in quadratic time |
| Abstract: | Let $\boldsymbol{A}$, $\boldsymbol{B}$ and $\boldsymbol{C}$ be $n\times 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 $\boldsymbol{AB}=\boldsymbol{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. We will also discuss possibilities of extending our algorithm for the case of real numbers and multiplication of matrices over finite fields. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož