Multi-user non-linearly separable distributed computing

Khalesi, Ali; Tanha, Ahmad; Malak, Derya; Elia, Petros

Submitted to ArXiV, 30 April 2026

This paper considers an

-server distributed computing setting with

users requesting functions that are arbitrary multivariable polynomial evaluations of

real (potentially non-linear) basis subfunctions, where each function output is raised to a bounded power. Our aim is to seek efficient task allocation and data communication techniques that reduce computation and communication costs. To this end, we take a tensor-theoretic approach, in which we represent the requested non-linearly decomposable functions using a properly designed tensor

, whose sparse decomposition into a tensor

and a matrix

directly defines the task assignment, connectivity, and communication patterns.

We design a lossless achievable scheme that integrates fixed-support SVD-based tensor factorization with multi-dimensional tiling of

and

, followed by a bipartite graph matching-based recursive assignment of tiles. This step transforms an overlapping decomposition into a disjoint one and reduces the resulting sum rank of the tiles, thereby decreasing the number of required servers. Under mild dimensionality conditions, we derive an explicit zero-error characterization of the achievable system rate

. Numerical simulations demonstrate the computational and communication savings over existing state-of-the-art matrix factorization approaches across a wide range of system parameters.

Detail

ARXIV

BIBTEX

Type:

Rapport

Date:

2026-04-30

Department:

Systèmes de Communication

Eurecom Ref:

8738

© 2026 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.