Home / Curated / Algorithms / Polynomial Codes for Straggler-Resilient High-Dimensional Coded Matrix Multiplication

Polynomial Codes for Straggler-Resilient High-Dimensional Coded Matrix Multiplication

Algorithms AIMech:PolynomialCodesForStragglerResilientHighDimensionalCodedMatrixMultiplication DRAFT

Aliases: Polynomial Codes, (alpha, beta)-Polynomial Code, (1, m)-Polynomial Code for Coded Matrix Multiplication

An algebraic coded distributed computation method proposed by Yu, Maddah-Ali, and Avestimehr (NeurIPS 2017) for computing high-dimensional matrix products C = A^T B across N workers—where each worker stores a 1/m fraction of A and a 1/n fraction of B—by partitioning A into m column blocks [A_0, ..., A_{m-1}] and B into n column blocks [B_0, ..., B_{n-1}], encoding worker i's stored submatrices as tilde{A}_i = sum_{j=0}^{m-1} A_j x_i^j and tilde{B}_i = sum_{k=0}^{n-1} B_k x_i^{k m} at distinct evaluation points x_i, and recovering all mn block products A_j^T B_k from any K* = mn responding workers via degree-(mn - 1) polynomial interpolation.

Identity Notes & Concept Scope Distinct from Lagrange Coded Computing (AIMech:LagrangeCodedComputingForResilientSecureAndPrivateDistributedLearning, which encodes a dataset of K separate inputs via Lagrange interpolation polynomials to evaluate a single multivariate polynomial f(X_i) on each batch), from Gradient Coding (AIMech:GradientCodingForStragglerResilientDistributedOptimization, which encodes partial loss gradients over replicated data blocks), and from MatDot and PolyDot Codes (AIMech:MatDotAndPolyDotCodesForStragglerResilientCodedMatrixMultiplication, which split A into column blocks and B into row blocks to compute inner-product sums sum_i A_i B_i with recovery threshold 2m - 1 at higher worker-to-master communication cost). Polynomial Codes (Yu, Maddah-Ali, & Avestimehr, NeurIPS 2017, pp. 4403-4413 / arXiv:1705.10464, Section II-IV, Definition 2, Equations 14-18, Theorems 1-5) achieve the information-theoretically minimum recovery threshold K_{poly} = mn = Theta(1) independent of N under minimum worker-to-master communication load L* = r t log_2 q (Theorems 1-3), and extend via the (alpha, beta) = (1, 1) code (Equations 31-33, Theorem 4) to distributed convolution c = a * b with recovery threshold K_{conv-poly} = m + n - 1.

Claims & Grounded Evidence

4 Claims

Mechanism #polynomial-codes-outer-product-block-encoding-and-vandermonde-interpolation

Given A = [A_0, ..., A_{m-1}] and B = [B_0, ..., B_{n-1}], the (1, m)-Polynomial Code assigns each worker i in {0, ..., N-1} a distinct scalar x_i in F_q and encoded submatrices tilde{A}_i = sum_{j=0}^{m-1} A_j x_i^j and tilde{B}_i = sum_{k=0}^{n-1} B_k x_i^{km} (Equation 17); worker i returns tilde{C}_i = tilde{A}_i^T tilde{B}_i = sum_{j=0}^{m-1} sum_{k=0}^{n-1} A_j^T B_k x_i^{j + km} (Equation 18), enabling the master to recover all mn block products A_j^T B_k by interpolating a degree-(mn - 1) polynomial from any mn workers in time O(rt log^2(mn) log log(mn)).

supports Source: Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication · Locator: Section III-A & III-B, Definition 2 and Equations (10)-(18), pp. 5-6

Scope #polynomial-codes-optimal-recovery-threshold-latency-communication-and-convolution-theorems

Theorems 1-3 and Corollary 1 prove that Polynomial Codes achieve the cut-set optimal recovery threshold K* = mn (strictly improving over 1D-MDS K = N - N/n + m and Product Codes K = 2(m-1)sqrt(N) - (m-1)^2 + 1), minimum computation latency T_{poly}, minimum communication load L* = rt log_2 q, and Reed-Solomon error correction of up to floor((N - mn)/2) Byzantine module errors; Theorems 4-5 prove that the (1, 1)-Polynomial Code achieves recovery threshold K_{conv-poly} = m + n - 1 (within a factor of 2 of optimal) for distributed convolution.

supports Source: Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication · Locator: Section I, Equations (1)-(3), pp. 2-3; Section II-B, Theorem 1 & Remark 6, pp. 4-5; Section III-C & III-D, Theorems 2-3, p. 7; Section IV, Theorems 4-5, p. 8

Limitation #polynomial-codes-real-valued-vandermonde-conditioning-and-quadratic-threshold-limitation

When each worker stores 1/m of both A and B (m = n), Polynomial Codes require K* = m^2 responding workers because they partition A and B into outer-product column blocks, and real-valued Vandermonde interpolation suffers numerical ill-conditioning for large mn unless inputs are quantized and embedded into a finite field F_q.

supports Source: Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication · Locator: Section III-B, Remark 7, p. 6

Application #polynomial-codes-straggler-resilient-cluster-matrix-multiplication-application

Applied to straggler-resilient distributed large-matrix multiplication and FFT-based Reed-Solomon decoding on MPI/AWS EC2 clusters, reducing tail computation latency by 37% compared to uncoded execution.

supports Source: Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication · Locator: Section V, Figure 5, p. 8

⚠️ Curated Limitations & Negative Results

Because Polynomial Codes partition A and B to recover all mn outer-product blocks A_j^T B_k, their recovery threshold scales as m^2 when m = n, whereas inner-product MatDot codes reduce the recovery threshold to 2m - 1 at the cost of higher communication.
Over real or floating-point numbers, high-degree Vandermonde interpolation matrices become exponentially ill-conditioned as mn grows unless finite-field quantization is applied.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LinearRegression` Linear Regression	related_match	AIO:LinearRegression and large-scale linear model training rely on distributed high-dimensional matrix multiplication accelerated by Polynomial Codes.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r540-primary-pdf`	Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper full_text	ID: https://dblp.org/rec/conf/nips/YuMA17.xml sha256:a29f9a31e95e…
`r540-arxiv-abs`	Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (arXiv abstract) Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper abstract_only	ID: https://arxiv.org/abs/1705.10464 sha256:8ea1a6d3fdb1…
`r540-metadata-cr`	Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (Crossref metadata) Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper abstract_only	ID: https://dblp.org/rec/conf/nips/YuMA17.xml sha256:b3a0eb0e8e80…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:23:00Z

Updated: 2026-10-19T10:23:00Z

Source File: data/curated/PolynomialCodesForStragglerResilientHighDimensionalCodedMatrixMultiplication.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories