On Large-Scale Matrix-Matrix Multiplication On Compressed Structures
Sudhindra Gopal Krishna, Aditya Narasimhan, Sridhar Radhakrishnan, Richard Veras · 2021 IEEE International Conference on Big Data (Big Data) · 2021
Matrix multiplication is an essential operation in the field of mathematics and computer science. Many critical computations, such as matrix factorization and graph computations, cast the bulk of their computation in terms of this operation. Thus, it is crucial that this operation is tuned to the data being computed on. In the case of sparse domains, this translates to minimizing the traffic between the CPU and main memory as the amount of work is not necessarily sufficient to amortize the code of the data movement. The amount of memory required to store a nonnegative valued matrix of n rows and m columns requires (n × m) × log2(n) bits. When these dimensions are converted to real world scenarios, for example, a one billion by one billion matrix will require 1000 petabytes of memory, which is impractical. This hinders the ability to perform any operations on the matrix.In this paper, we propose techniques for performing Matrix-Matrix multiplication directly on compressed data stored in two different compression data structures. The structures we consider are the well-known compressed sparse matrix and the Compressed Binary Trees [1]. We test our algorithm on extremely large matrices, in the order of 100s of millions with various levels of sparsity. We show for matrices of order 100 million with 10 million nonzero elements, the space required to store the matrices using the CBT representation is about 6.4MB and requires 13.52s to complete the multiplication using the sequential algorithms provided in this paper.