Research Projects

Matrix multiplication is a powerful mathematical operation that works inside everything from computer graphics and neural networks to quantum physics. It is simple enough to explain to a high school student, yet its exact computational complexity has been elusive to accomplished computer scientists. Researchers have tried to come up with efficient (centralized) algorithms for the problem over the years. However, the rising importance of data-heavy computing – represented in engineering efforts such as MapReduce, Hadoop, Dryad, and Spark – traditional cost measures, such as running time or space consumption, are not sufficient anymore to judge the efficiency of an algorithm. To account for these developments, a number of theoretical models have been proposed that penalize storing or exchanging data. These models come under the umbrella of distributed algorithms. In this project, we aim to obtain efficient algorithms for matrix multiplication of various types of matrices (square, rectangular, sparse etc) in different types of distributed computing models. Such algorithms are important from many perspectives, for example, (i) speedup for large datasets in ML: when the size of matrices in machine learning models or simulations grows, the computational cost of multiplying them can become prohibitively expensive. Fast-distributed algorithms significantly reduce the time required to multiply large matrices, making previously intractable problems feasible. Modern deep learning frameworks like TensorFlow, PyTorch, and Apache MXNet use distributed matrix multiplication to train models across multiple GPUs or machines, significantly speeding up the training process and enabling researchers and engineers to work with larger datasets and more complex models, (ii) quantum computers often simulate quantum systems by performing matrix operations (e.g., matrix exponentiation). Distributing these tasks across multiple quantum processors can speed up these computations, helping scale quantum simulations for larger systems. This motivates us to obtain improved algorithms for matrix multiplication in various modes of distributed algorithms, in particular, the following three models: low bandwidth model, clique model, and MPC (massively parallel computation) model. These models capture the essence of various practical systems around us. For example, the low bandwidth model represents a system where the bandwidth of computers in a (distributed) system is very small compared to the size of the problem. The MPC model addresses the issue of processing big data, i.e., when a computer's memory is too small to store all the input. Thus obtaining faster matrix multiplication algorithms in these models will have ramifications in many real-world applications. In this project, along with algorithmic tools, we plan to use reinforcement learning techniques to solve these problems. Such techniques have been used previously in traditional algorithms but not in distributed algorithms