Event
CCSP Seminar: Viveck Cadambe, Penn State, "Coded Matrix Multiplications"
Thursday, April 18, 2019
5:00 p.m.-6:30 p.m.
2168 A. V. Williams
Ajaykrishnan Nageswaran
301 405 3661
ajayk@umd.edu
http://www.ece.umd.edu/seminars/ccsp/
Communication, Control and Signal Processing Seminar
Coded Matrix Multiplications
Vivek Cadambe
The Pennsylvania State University
Abstract
There is a lot of recent interest in the emerging area of coded computing that uses redundancy to mitigate stragglers and errors in distributed data processing. This talk will present some ideas and results in this area. Specifically, given two matrices $A$, $B$, we consider the problem of computing the product $AB$ over $P$ processing nodes in a fault-tolerant manner. We assume that the $i$-th node, for $i = 1,2,\ldots,P$ receives $g_i(A)$, and $h_i(B),$ where $g_i, h_i$ are linear operators on the space of matrices, and the nodes compute the product of the matrices it receives, i.e., $g_i(A) h_i(B)$. The functions are designed so that the product $AB$ is recoverable from any $K$ of the $P$ nodes; for a given scheme, we refer to the smallest such $K$ as the recovery threshold of the scheme.
We will survey results related to the minimum known recovery threshold under various restrictions/constraints on the functions $g_i$, $h_i$. We will describe several schemes via polynomial evaluation based encoding and polynomial interpolation based decoding. We first present conceptually simple code constructions that work well for small $P$, but perform poorly in larger systems due to numerical precision errors. We then present some of our recent results in numerical analysis, and show how the conceptually simple code constructions can be modified to solve some of these precision errors.
