Back to Search
Start Over
On the Optimal Recovery Threshold of Coded Matrix Multiplication
- Source :
- Allerton
- Publication Year :
- 2020
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2020.
-
Abstract
- We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When $m$-th fraction of each matrix can be stored in each worker node, Polynomial codes require $m^2$ successful workers, while our MatDot codes only require $2m-1$ successful workers, albeit at a higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Further, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off communication cost and recovery threshold. Finally, we demonstrate a coding technique for multiplying $n$ matrices ($n \geq 3$) by applying MatDot and PolyDot coding ideas.<br />Comment: Extended version of the paper that appeared at Allerton 2017 (October 2017), including full proofs and further results. Submitted to IEEE Transactions on Information Theory
- Subjects :
- FOS: Computer and information sciences
Polynomial code
Computer science
Computer Science - Information Theory
Information Theory (cs.IT)
Computation
020206 networking & telecommunications
02 engineering and technology
010501 environmental sciences
Library and Information Sciences
01 natural sciences
Matrix multiplication
Computer Science Applications
Matrix (mathematics)
Computer Science - Distributed, Parallel, and Cluster Computing
0202 electrical engineering, electronic engineering, information engineering
Distributed, Parallel, and Cluster Computing (cs.DC)
Arithmetic
0105 earth and related environmental sciences
Coding (social sciences)
Information Systems
Subjects
Details
- ISSN :
- 15579654 and 00189448
- Volume :
- 66
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Information Theory
- Accession number :
- edsair.doi.dedup.....c1378add45b70f1b37192b9c87bea696