Numerically stable coded matrix computations via circulant and rotation matrix embeddings

Understand

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 $n$ worker nodes where $s$ can be stragglers, these approaches allow for an optimal recovery threshold, whereby the intended result can be decoded as long as any $(n-s)$ 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 $n$.
• We present a novel approach that leverages the properties of circulant permutation matrices and rotation matrices for coded matrix computation.