Numerically Stable Polynomially Coded Computing
Numerically Stable Polynomially Coded Computing
复制标题
DOI：
10.1109/tit.2021.3050526
复制
发表时间：
2019-03
影响因子：
2.5
通讯作者：
Mohammad Fahim;V. Cadambe
中科院分区：
文献类型：
--
作者：
Mohammad Fahim;V. Cadambe
我们研究了基于多项式的编码方法的数值稳定性，这已经成为一类强大的技术，在编码计算领域提供掉队和容错。我们的贡献如下：1）我们构造了新的矩阵乘法码，它们与以前构造的MatDot码和Polynomial码具有相同的容错性。2）我们证明了在$n$ -点Chebyshev网格上计算的$m\times n，n \geq m$ Chebyshev-Vandermonde矩阵的每个$m \times m$子矩阵的条件数，增长为$O（n^{2（n-m）}）$ for $n > m$. 3）通过将我们基于正交多项式的构造专门化为切比雪夫多项式，并使用我们对切比雪夫-范德蒙矩阵的条件数界，我们构造了新的编码矩阵乘法的数值稳定技术。我们的经验表明，我们的建设有显着较低的数值误差相比，以前的方法，涉及范德蒙矩阵的逆。4）提出了一种数值稳定的拉格朗日编码计算的特殊化。我们的方法涉及到评估点的选择和一个合适的解码过程。经验证明，我们的方法与标准方法相比具有较低的数值误差。
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.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$ .3)By specializing our orthogonal polynomial based constructions to Chebyshev polynomials, and using our condition number bound for Chebyshev-Vandermonde matrices, we construct new numerically stable techniques for coded matrix multiplication. We empirically demonstrate that our constructions have significantly lower numerical errors compared to previous approaches which involve inversion of Vandermonde matrices. We generalize our constructions to explore the trade-off between computation/communication and fault-tolerance.4)We propose a numerically stable specialization of Lagrange coded computing. Our approach involves the choice of evaluation points and a suitable decoding procedure. Our approach is demonstrated empirically to have lower numerical errors as compared to standard methods.