Universally Decodable Matrices for Distributed Matrix-Vector Multiplication

Thumbnail Image
Date
2019-01-01
Authors
Tang, Li
Vontobel, Pascal
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

Coded computation is an emerging research area that leverages concepts from erasure coding to mitigate the effect of stragglers (slow nodes) in distributed computation clusters, especially for matrix computation problems. In this work, we present a class of distributed matrix-vector multiplication schemes that are based on codes in the Rosenbloom-Tsfasman metric and universally decodable matrices. Our schemes take into account the inherent computation order within a worker node. In particular, they allow us to effectively leverage partial computations performed by stragglers (a feature that many prior works lack). An additional main contribution of our work is a companion matrix-based embedding of these codes that allows us to obtain sparse and numerically stable schemes for the problem at hand. Experimental results confirm the effectiveness of our techniques.

Series Number
Journal Issue
Is Version Of
Versions
Series
Type
article
Comments

This is a pre-print of the article Ramamoorthy, Aditya, Li Tang, and Pascal O. Vontobel. "Universally Decodable Matrices for Distributed Matrix-Vector Multiplication." arXiv preprint arXiv:1901.10674 (2019). Posted with permission.

Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 2019
Funding
DOI
Supplemental Resources
Source
Collections