论文标题
编码分布式的折叠多项式代码$ aa^\ top $ -type矩阵乘法
Folded Polynomial Codes for Coded Distributed $AA^\top$-Type Matrix Multiplication
论文作者
论文摘要
In this paper, due to the important value in practical applications, we consider the coded distributed matrix multiplication problem of computing $AA^\top$ in a distributed computing system with $N$ worker nodes and a master node, where the input matrices $A$ and $A^\top$ are partitioned into $m$-by-$p$ and $p$-by-$m$ blocks of equal-size sub-matrices respectively.为了有效缓解straggler，我们提出了一种新的计算策略，称为\ emph {折叠多项式代码}，该策略是通过修改纠缠多项式代码来获得的。此外，当底层字段是实际数字字段时，我们在所有线性计算策略中的最佳恢复阈值中表征了一个下限，而在$ M = 1 $的情况下，我们的折叠多项式代码可以实现此键。与编码分布式矩阵乘法的所有已知计算策略相比，我们的折叠多项式代码在恢复阈值，下载成本和解码复杂性方面都优于它们。
In this paper, due to the important value in practical applications, we consider the coded distributed matrix multiplication problem of computing $AA^\top$ in a distributed computing system with $N$ worker nodes and a master node, where the input matrices $A$ and $A^\top$ are partitioned into $m$-by-$p$ and $p$-by-$m$ blocks of equal-size sub-matrices respectively. For effective straggler mitigation, we propose a novel computation strategy, named \emph{folded polynomial code}, which is obtained by modifying the entangled polynomial codes. Moreover, we characterize a lower bound on the optimal recovery threshold among all linear computation strategies when the underlying field is the real number field, and our folded polynomial codes can achieve this bound in the case of $m=1$. Compared with all known computation strategies for coded distributed matrix multiplication, our folded polynomial codes outperform them in terms of recovery threshold, download cost, and decoding complexity.
