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 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> worker nodes where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s$</tex> 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 ≈ <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O$</tex> (n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</sup> + <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> ); in the practical scenario where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s$</tex> 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.