SURF

Jon Hillery

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 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.

Message to Sponsor

I, and the rest of the math team, would like to thank the Sherrill Fund for funding and supporting us this past summer. I now have a much better understanding of what it means to be an independent researcher. In addition to discovering exciting new things about communication-avoiding CNNs, I feel much better prepared to conduct research in other areas in the future. This experience helped me grow greatly as a young mathematician and will prepare me for graduate school in the future.
  • Major: Mathematics
  • Sponsor: Sherrill Fund
  • Mentor: James Demmel & Olga Holtz