Mason Haberle L&S Sciences
Holder-Brascamp-Lieb, Red-Blue Pebbling, and Communication-Optimal Algorithms
Numerical linear algebra underlies much of the modern world. It is essential to a wide variety of situations, and, as such, it is of great interest to analyze and optimize the underlying algorithms. In recent years, there has been an increased interest in optimizing algorithms to reduce communication, which is frequently many orders of magnitude slower than performing calculations. The Hlder-Brascamp-Lieb inequality and the Red-Blue Pebbling Game are two powerful approaches to theoretical analysis of communication, and both are used to derive communication optimal lower bounds. Once these bounds have been derived, the next challenge is to implement an algorithm that attains these minimums, and thus, is communication minimizing. Many currently implemented algorithms do not meet these bounds, and this is a matter of great importance, with large potential time and energy savings. In this way, our project has two broad goals. Our first is to implement a communication optimal algorithm for the implementation of convolutional neural networks, and our second is to develop a theoretical framework that unifies the Hlder-Brascamp-Lieb inequality and the Red-Blue Pebbling Game.