论文标题
均等的Strassen算法
Parity-Checked Strassen Algorithm
论文作者
论文摘要
为了使用散布的平行工人乘以天文矩阵，我们建议将校验和一些快速矩阵乘法算法进行交织。我们嵌套了均衡检查的算法，我们编织了产品代码风味。 两种证明性配置如下：（a）$ 9 $工人乘以两个$ 2 \ times 2 $矩阵；每个工人在其中乘以两个线性组合。然后，从任何$ 8 $的工人发送的输入产品足以组装矩阵产品。 （b）$ 754 $工人乘以两个$ 9 \ times 9 $矩阵。有经验频率$ 99.8 \％$，$ 729 $工人就足够了，其中$ 729 $是学科算法的复杂性。 通常，我们提出了概率上有利的配置，其工人数量接近（如果不小于其他代码的阈值）（例如，纠缠的多项式代码和Polydot代码）。我们提出的计划递归地适用，尊重工人所在地，构成中等的预处理和后处理，并扩展到小小的有限领域。
To multiply astronomic matrices using parallel workers subject to straggling, we recommend interleaving checksums with some fast matrix multiplication algorithms. Nesting the parity-checked algorithms, we weave a product code flavor protection. Two demonstrative configurations are as follows: (A) $9$ workers multiply two $2\times 2$ matrices; each worker multiplies two linear combinations of entries therein. Then the entry products sent from any $8$ workers suffice to assemble the matrix product. (B) $754$ workers multiply two $9\times 9$ matrices. With empirical frequency $99.8\%$, $729$ workers suffice, wherein $729$ is the complexity of the schoolbook algorithm. In general, we propose probability-wisely favorable configurations whose numbers of workers are close to, if not less than, the thresholds of other codes (e.g., entangled polynomial code and PolyDot code). Our proposed scheme applies recursively, respects worker locality, incurs moderate pre- and post-processes, and extends over small finite fields.
