Algebraic Geometry Codes for Distributed Matrix Multiplication Using Local Expansions

doi:10.1109/TIT.2025.3641651

2026-02-01

PRE

Jiang Li

Songsong Li *

Chaoping Xing

DOI：10.1109/TIT.2025.3641651

原文链接

原文求助

摘要

En 中文

基于代数的分布式矩阵乘法（DMM）已被广泛研究为分布式系统中大规模矩阵计算的有效方法。基于代数的DMM存在两个核心挑战：最小化通信成本和降低恢复阈值——成功恢复矩阵乘法所需的最少工作节点数。已提出几种基于里德-所罗门（RS）的方案，包括多项式、MatDot和PolyDot码；然而，其适用性受限于底层有限域的大小，限制了可用工作节点的数量。代数几何（AG）码作为RS码的推广，通过在小域上实现更长的码长克服了这一限制。先前的工作将多项式和MatDot码推广至AG码，实现了随着底层代数函数域亏格的加性增加的恢复阈值。然而，由于代数曲线上的函数结构比单变量多项式更复杂，将PolyDot码推广至具有类似加性增加的AG环境仍是一个开放性挑战。在本工作中，我们基于函数的局部展开，在一个统一的AG框架下推广了基于RS的多项式、MatDot和PolyDot码。我们的主要贡献是首次构建了基于AG的PolyDot码，其恢复阈值随亏格加性扩展。此外，我们的基于AG的多项式和MatDot码实现了比现有AG基DMM方案更好的恢复阈值，同时保持可比较的通信成本。我们构造的一个关键创新是来自局部展开的里曼-罗赫空间的 novel 基，避免了因使用非间隙数而在先前构造中引起的抵消问题。

Keyword:

Codes

Polynomials

Costs

Geometry

Reed-Solomon codes

Galois fields

Distributed computing

Decoding

Standards

Hands

Distributed matrix multiplication