Article
Distributed Matrix Tiling using a Hypergraph Labeling Formulation
ACM International Conference Proceeding Series
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.
Meeting Name
23rd International Conference on Distributed Computing and Networking, ICDCN 2022 (2022: Jan. 4-7, Delhi, India)
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
Citation
File Type
text
Language(s)
English
Rights
© 2022 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
1-7-2022
Publication Date
07 Jan 2022
Disciplines
Citation Information
Avah Banerjee, Maxwell Reeser and Guoli Ding. "Distributed Matrix Tiling using a Hypergraph Labeling Formulation" ACM International Conference Proceeding Series (2022) p. 62 - 71 Available at: http://works.bepress.com/avah-banerjee/6/