Abstract
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.
Recommended Citation
A. Banerjee et al., "Distributed Matrix Tiling using a Hypergraph Labeling Formulation," ACM International Conference Proceeding Series, pp. 62 - 71, Association of Computing Machinery (ACM), Jan 2022.
The definitive version is available at https://doi.org/10.1145/3491003.3491017
Department(s)
Computer Science
Keywords and Phrases
greedy algorithm; hypergraph coloring; tiling
International Standard Book Number (ISBN)
978-145039560-1
Document Type
Article - Conference proceedings
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 2023 Association of Computing Machinery, All rights reserved.
Publication Date
04 Jan 2022
