Skip to main content
Article
Distributed Matrix Tiling using a Hypergraph Labeling Formulation
ACM International Conference Proceeding Series
  • Avah Banerjee, Missouri University of Science and Technology
  • Maxwell Reeser
  • Guoli Ding
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/