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 $p$-by-$m$ and $m$-by-$p$ 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 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.
翻译:在本文中,由于实际应用中的重要价值,我们考虑了在使用美元工人节点和主节点的分布式计算系统中计算$A ⁇ top$的编码分布式矩阵倍增问题,在这种系统中,输入矩阵$A$和$A ⁇ top$被分别分割成以美元乘以美元和以美元乘以美元乘以美元区块的相等大小子体块。为了有效地减少分流,我们提出了一个新颖的计算战略,名为\emph{折叠的多元码},这是通过修改缠绕的多元码获得的。此外,当基础字段为实际数字字段时,我们对所有线性计算战略的最佳回收阈值定下了一个较低的约束,而我们的折叠合多边编码可以在1美元的情况下达到这一约束。与所有已知的编码分布式矩阵倍增法计算战略相比,我们折叠的多元编码在回收阈值、下载成本和解码复杂度方面超越了它们。