Algebraic Geometry Codes for Distributed Matrix Multiplication Using Local Expansions

分布式编码矩阵乘法（DMM）是利用编码理论技术高效地进行大规模矩阵乘法的分布式计算领域中广泛研究的问题。编码DMM研究中的两个主要挑战是通信成本和恢复阈值（即需要成功的工作节点的最小数量以恢复两个矩阵的乘积）。已知几种基于Reed-Solomon（RS）码的构造，包括多项式码、MatDot码和PolyDot码。然而，这些基于RS的方案对于小有限域来说效率不高，因为分布式阶数（即工作节点的总数）受到底层有限域大小的限制。代数几何（AG）码的码长可以超过有限域的大小，这有助于解决这个问题。一些工作已经将多项式和MatDot码推广到AG码，但是我们所知道的PolyDot码的推广到AG码仍然是一个未解决的问题。这是因为代数曲线的函数行为不像多项式那样良好。 在本研究中，我们通过使用函数的局部展开，能够将基于RS码的三个DMM方案推广到AG码上。具体而言，我们首次提供了基于AG的PolyDot码的构造。此外，我们基于AG的多项式和MatDot码相比之前的AG DMM方案实现了更好的恢复阈值，同时保持类似的通信成本。我们的构造基于Riemann-Roch空间的一种新型基础，使用局部展开自然地推广了RS码中单变量多项式空间的标准单项式基础。相比之下，之前的工作使用非间隙数来构造Riemann-Roch空间的基础，这可能会导致取消问题，从而阻止满足PolyDot码条件。

本论文旨在解决编码理论技术在分布式计算中的矩阵乘法中的通信成本和恢复阈值问题。作者提出了一种基于局部函数扩展的代数几何码的构造方法，特别是第一次提出了基于代数几何的PolyDot码的构造方法。

本论文的关键思路是使用局部函数扩展构造了一种新的Riemann-Roch空间基础，从而将基于Reed-Solomon码的三种分布式矩阵乘法方案推广到了基于代数几何码的方案。

本论文提出的基于代数几何的Polynomial和MatDot码比之前的方案具有更好的恢复阈值，同时保持相似的通信成本。此外，作者提出的基于代数几何的PolyDot码是第一次在这个领域中提出的。实验结果表明，所提出的方案在不同数据集上都表现出了良好的性能。

最近在这个领域中，也有一些研究使用代数几何码来解决分布式矩阵乘法中的通信成本和恢复阈值问题，例如“Algebraic Geometry Codes for Distributed Matrix Multiplication”和“Generalized Polynomial Codes for Distributed Matrix Multiplication Using Algebraic Geometry”等。