Structured Codes for Distributed Matrix Multiplication

Derya Malak · 2025

Read Structured Codes for Distributed Matrix Multiplication by Derya Malak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00371.txt.

Introduction

Derya Malak tackles a long-open problem in distributed computing, in a research paper published in 2024. Two nodes hold linked data sources, one each, and a receiver must compute a function of both, such as a dot product or a matrix product. The question is the least total data rate that makes the computation possible.

Malak sets tight bounds on that best sum rate, exact for large field sizes across all problem sizes and a broad class of sources. The scheme reshapes each source in a nonlinear way tuned to a classic structured coding method. Matching limit proofs adapt two known converse tools. Against standard Slepian-Wolf coding, the gains from using the structure grow without bound as the sources correlate more.

Catalog record

CREATORDerya Malak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE146 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00371

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structured Codes for Distributed Matrix Multiplication Derya Malak Abstract Our work addresses the well-known open problem of distributed computing of bilinear functions of two correlated sources 𝐀 {\bf A} and 𝐁 {\bf B} . In a setting with two nodes, with the first node having access to 𝐀 {\bf A} and the second to 𝐁 {\bf B} , we establish bounds on the optimal sum rate that allows a receiver to compute an important class of non-linear functions, and in particular bilinear functions, including dot products ⟨ 𝐀 , 𝐁 ⟩ \langle{\bf A},{\bf B}\rangle , and general matrix products 𝐀 ⊺ ​ 𝐁 {\bf A}^{\intercal}{\bf B} over finite fields. The bounds are tight for large field sizes, for which case we can derive the exact fundamental performance limits for all problem dimensions and a large class of sources. Our achievability scheme involves the design of non-linear transformations of 𝐀 {\bf A} and 𝐁 {\bf B} , carefully calibrated to work synergistically with the structured linear encoding scheme by Körner and Marton. The subsequent converses derived here, calibrate the Han-Kobayashi approach and the strong converse of Ahlswede-Gács-Körner to yield relatively tight converses on the sum rate. We exhibit unbounded compression gains over Slepian-Wolf coding, depending on the source correlations. In the end, this work characterizes the fundamental limits of distributed computing for a crucial class of functions, while succinctly capturing the inherent computation structures and source correlations. I Introduction Basic functions like matrix multiplication, currently constitute the bulk of computational load in scientific computing, as they are omnipresent in applications that include convolution [ 2 ] , large linear transforms, Fourier transforms, quantum computing [ 3 ] , as well as in applications of machine learning such as linear regression, least squares modeling [ 2 ] , and many more. The unprecedented intensity of such computational loads often brings to the fore the necessity for massive parallelization techniques, and we are now witnessing the deployment of massive distributed computing systems, geared at tackling complex distributed computing tasks. It is the case though that to be successfully deployed, distributed computing requires an intense exchange of information among the participating nodes. In most scenarios, including matrix multiplication, it is evident that to meaningfully parallelize across multiple workers, one must maintain a reduced communication load, which is now considered as a main bottleneck of parallel processing. The need for minimizing this load is clear and evident, and this is a need that has motivated several of the noteworthy parallel computing techniques, such as in [ 4 , 5 , 6 , 7 , 8 , 9 , 10 ] to mention just a fraction, many of which have been designed and tested with success. Motivated by the above, we here study the communication cost of distributed computing, and we do so for a prevalent class of non-linear functions, namely of bilinear functions. As suggested above, this setting finds itself at the core of various technological fields in edge and cloud computing [ 11 ] and machine learning [ 12 ] , and again, as suggested, this is a setting that entails considerable communication overheads as well as an intriguingly intertwined relationship between communication and computational parallelization. This bottleneck has been studied in seminal works such as [ 13 , 14 , 15 , 16 , 17 ] , focusing often on the linear function case. Our work focuses on the classical problem of distributed computing of bilinear functions of two correlated sources, placing emphasis on dot and matrix products, while also capturing an important element of modern large data; the strong structural correlations of this data that serves as computing input. In a context similar to [ 18 , 13 , 14 ] where the receiver wishes to compute bilinear functions of the distributed sources, our aim is to establish bounds on the optimal sum rate (the minimum amount of information) that allows a receiver to compute these functions. The technical contributions of this work are summarized in the following. I-A Main Contributions of this Work • New structured source codes for distributed computing of dot and matrix products. We devise an encoding framework for computing the product of two distributed correlated source variables {\bf A} and {\bf B} (vectors or matrices), over finite fields. To this end, our achievability scheme involves the novel design of non-linear transformations for long sequences of {\bf A} and {\bf B} drawn i.i.d. across realizations, according to some joint probability distribution. These transformations are then carefully calibrated to work synergistically with the structured linear encoding scheme by Körner and Marton [ 13 ] as well as the more general scheme by Ahlswede and Han [ 19 ] for computing a class of bilinear functions, all with a vanishing error probability. Our achievability results include constructions for distributed computing of dot products (Corollary 1 ), matrix products that are symmetric (Propositions 1 and 2 , and Theorem 2 ), and general square matrix products (Proposition 3 , and Theorem 3 ). We also explore a hybrid encoding scheme (Proposition 4 ), as well as consider recursive and nested applications of the dot product (Propositions 5 - 7 ) for distributed matrix multiplication. Our schemes are flexible, allowing the receiver to recover {\bf A}^{\intercal}{\bf B} without imposing structural constraints on {\bf A} and {\bf B} . • Achievable compression gains. Contrasting the sum rates of our structured source codes (see Propositions 1 - 4 and Theorems 2 and 3 ) with the state-of-the-art codes (e.g., [ 18 , 20 , 21 ] ) reveals significant gains when computing dot products and matrix products (of distributed sources {\bf A} and {\bf B} ). Our schemes carefully harness the structure of the source data, and the corresponding sum-rate gains are naturally more pronounced in the presence of stronger correlations (see Examples 1 - 3 , and see also Figure 4 which relates to Propositions 1 and 4 ). • Converse results. Leveraging the Ahlswede-Gács-Körner approach in [ 22 ] allows us here to derive a strong converse for the square matrix product setting, as q\to\infty (Theorem 4 ). Furthermore, calibrating the Han-Kobayashi approach in [ 14 ] yields a relatively tight lower bound on the sum rate for all q\geq 2 (Theorem 5 ). In addition to the main converse bounds, for independently and uniformly drawn source matrices {\bf A} and {\bf B} when q\to\infty , we also derive a matching strong converse to the achievability Theorem 3 for the case of square matrix products (Corollary 5 ). Finally, for the cases of symmetric and square matrix products over \mathbb{F}_{2} , we upper bound the optimality gaps of our design (see Propositions 8 and 9 respectively). • Our schemes have some additional properties, like balancing the computation load across the nodes, as well as offering some security advantages. We briefly discuss these in Section V . I-B Related Work and Connections of Our Work to the State of the Art Below, we detail two main approaches used in distributed coding for computation: unstructured coding-based approaches (also known as random binning, relying on hashing functions), and structured coding-based approaches that are more directly geared towards leveraging the structure of the computation task. Unstructured

Read the complete text