Distributed Matrix Tiling using a Hypergraph Labeling Formulation
Partitioning large matrices is an important problem in distributed linear algebra computing, used in ML among others. Briefly, our goal is to perform a sequence of matrix algebra operations in a distributed manner on these large matrices. However, not all partitioning schemes work well with different matrix algebra operations and their implementations (algorithms). This is a type of data tiling problem. In this paper we consider a data tiling problem using hypergraphs. We prove some hardness results and give a theoretical characterization of its complexity on random instances. Additionally we develop a greedy algorithm and experimentally show its efficacy.
A. Banerjee et al., "Distributed Matrix Tiling using a Hypergraph Labeling Formulation," ACM International Conference Proceeding Series, pp. 62 - 71, Association for Computing Machinery (ACM), Jan 2022.
The definitive version is available at https://doi.org/10.1145/3491003.3491017
23rd International Conference on Distributed Computing and Networking, ICDCN 2022 (2022: Jan. 4-7, Delhi, India)
Keywords and Phrases
Greedy Algorithm; Hypergraph Coloring; Tiling
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2022 Association for Computing Machinery (ACM), All rights reserved.
07 Jan 2022