Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm

0431579 - ÚI 2015 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Wiedermann, Jiří
Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm.
Theoretical Computer Science. Heidelberg: Springer, 2014 - (Diaz, L.; Lanese, I.; Sangiorgi, D.), s. 123-135. Lecture Notes in Computer Science, 8705. ISBN 978-3-662-44601-0. ISSN 0302-9743.
[TCS 2014. IFIP TC 1/WG 2.2 International Conference /8./. Rome (IT), 01.09.2014-03.09.2014]
Grant CEP: GA ČR GAP202/10/1333
Institucionální podpora: RVO:67985807
Klíčová slova: matrix multiplication * Freivalds' algorithm * derandomization * computational complexity
Kód oboru RIV: IN - Informatika

We design two nondeterministic algorithms for matrix multiplication. Both algorithms are based on derandomization of Freivalds’ algorithm for verification of matrix products. The first algorithm works with real numbers and its time complexity on Real RAMs is O(n 2logn). The second one is of the same complexity, works with integer matrices on a unit cost RAM with numbers whose size is proportional to the size of the largest entry in the underlying matrices. Our algorithms bring new ideas into the design of matrix multiplication algorithms and open new avenues for their further development. The results pose exciting questions concerning the relation of the complexity of deterministic versus nondeterministic algorithms for matrix multiplication, and complexity of integer versus real matrices multiplication.
Trvalý link: http://hdl.handle.net/11104/0236194