sparse matrix

finite fields

linear equations

We consider the issue of numerical stability in solving the problem of coded large scale matrix multiplication in distributed systems where worker nodes are prone to failures/delays. We construct new codes that achieve comparable fault tolerance as previous codes, but are more numerically stable. Unlike previous codes that use polynomials expanded in a monomial basis, our codes use polynomials expressed in a basis of orthonormal polynomials. We show via new theoretical results on the condition number, as well as numerical experiments, that the application of these codes can lead to significantly more numerically stable computation than the current monomial-basis codes.

Numerically Stable Polynomially Coded Computing