Numerically Stable Coded Matrix Computations via Circulant and Rotation Matrix Embeddings
Aditya Ramamoorthy, Li Tang
Abstract
Polynomial based methods have recently been used in several works for mitigating the effect of stragglers (slow or failed nodes) in distributed matrix computations. For a system with <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> worker nodes where <inline-formula> <tex-math notation="LaTeX">$s$ </tex-math></inline-formula> can be stragglers, these approaches allow for an optimal recovery threshold, whereby the intended result can be decoded as long as any <inline-formula> <tex-math notation="LaTeX">$(n-s)$ </tex-math></inline-formula> worker nodes complete their tasks. However, they suffer from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices; this condition number grows exponentially in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. We present a novel approach that leverages the properties of circulant permutation matrices and rotation matrices for coded matrix computation. In addition to having an optimal recovery threshold, we demonstrate an upper bound on the worst-case condition number of our recovery matrices which grows as <inline-formula> <tex-math notation="LaTeX">$\approx O(n^{s+5.5})$ </tex-math></inline-formula>; in the practical scenario where <inline-formula> <tex-math notation="LaTeX">$s$ </tex-math></inline-formula> is a constant, this grows polynomially in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. 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.