| Paper ID | D4-S4-T1.1 |
| Paper Title |
Numerically stable coded matrix computations via circulant and rotation matrix embeddings |
| Authors |
Aditya Ramamoorthy, Li Tang, Iowa State University, United States |
| Session |
D4-S4-T1: Coded Distributed Matrix Multiplication II |
| Chaired Session: |
Thursday, 15 July, 23:00 - 23:20 |
| Engagement Session: |
Thursday, 15 July, 23:20 - 23:40 |
| Abstract |
Polynomial based methods have recently been used in several works for mitigating the effect of stragglers in distributed matrix computations. However, they suffer from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices. For a system with $n$ worker nodes where $s$ can be stragglers the condition number grows exponentially in $n$. We present a novel coded computation approach that leverages the properties of circulant permutation and rotation matrices. Our scheme has an optimal recovery threshold and an upper bound on the worst case condition number of our recovery matrices which grows as $\approx O(n^{s+6})$; in the practical scenario where $s$ is a constant, this grows polynomially in $n$. Our schemes leverage the well-behaved conditioning of complex Vandermonde matrices with parameters on the complex unit circle, while still working with computation over the reals. Exhaustive experimental results demonstrate that our proposed method has condition numbers that are orders of magnitude lower than prior work.
|
