Numerically Stable Polynomially Coded Computing

Understand

We study the numerical stability of polynomial based encoding methods, which has emerged to be a powerful class of techniques for providing straggler and fault tolerance in the area of coded computing.

• Our contributions are as follows: 1) We construct new codes for matrix multiplication that achieve the same fault/straggler tolerance as the previously constructed MatDot Codes and Polynomial Codes.
• Unlike previous codes that use polynomials expanded in a monomial basis, our codes uses a basis of orthogonal polynomials.
• 2) We show that the condition number of every $m \times m$ sub-matrix of an $m \times n, n \geq m$ Chebyshev-Vandermonde matrix, evaluated on the $n$-point Chebyshev grid, grows as $O(n^{2(n-m)})$ for $n > m$.