Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds? Algorithm

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds? Algorithm

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds? Algorithm

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F1333" target="_blank" >GAP202/10/1333: NoSCoM: Nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název statě ve sborníku

Theoretical Computer Science

ISBN

978-3-662-44601-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

123-135

Název nakladatele

Springer

Místo vydání

Heidelberg

Místo konání akce

Rome

Datum konání akce

1. 9. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—