Distributed Matrix Tiling using a Hypergraph Labeling Formulation

Author

Avah Banerjee, Missouri University of Science and TechnologyFollow
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.

Recommended Citation

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

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

07 Jan 2022