Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds? Algorithm

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F14%3A00431579" target="_blank" >RIV/67985807:_____/14:00431579 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-662-44602-7_11" target="_blank" >http://dx.doi.org/10.1007/978-3-662-44602-7_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-44602-7_11" target="_blank" >10.1007/978-3-662-44602-7_11</a>

Result language
angličtina
Original language name
Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds? Algorithm
Original language description
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 designof 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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GAP202%2F10%2F1333" target="_blank" >GAP202/10/1333: NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)