Codes for Distributed Finite Alphabet Matrix-Vector Multiplication
| Autor: | Viveck R. Cadambe, Farzin Haddadpour |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Multiplication algorithm
Computational complexity theory Computer science Computation Binary number 020206 networking & telecommunications 02 engineering and technology 010501 environmental sciences 01 natural sciences Matrix multiplication Matrix (mathematics) Redundancy (information theory) 0202 electrical engineering electronic engineering information engineering Multiplication Arithmetic 0105 earth and related environmental sciences |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit.2018.8437542 |
| Popis: | Recent work has developed coding theoretic approaches to add redundancy to distributed matrix-vector multiplications with the goal of speeding up the computation by mitigating the straggler effect in distributed computing. In this paper, we consider the case where the matrix comes from a small (e.g., binary) alphabet, where a variant of a popular method called the “Four-Russians method” is known to have significantly lower computational complexity as compared with the usual matrix-vector multiplication algorithm. We develop novel code constructions that are applicable to binary matrix-vector multiplication via a variant of the Four-Russians method called the Mailman algorithm. Specifically, in our constructions, the encoded matrices have a low alphabet that ensures lower computational complexity, as well as good straggler tolerance. We also present a trade-off between the communication and computation cost of distributed coded matrix-vector multiplication for general, possibly non-binary, matrices. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|