Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm

Abstract : 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(n2logn). 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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.123-135, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_11〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402036
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:49:35
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:12:09

Fichier

978-3-662-44602-7_11_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jiří Wiedermann. Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.123-135, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_11〉. 〈hal-01402036〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

69