Title

Distributed Matrix Tiling using a Hypergraph Labeling Formulation

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

07 Jan 2022

Share

 
COinS