SURF

Rahul Jain

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

Dear Sherrill Fund, this experience was amazing as I got to really learn what pursuing a research project from scratch was all about from the guidance of professors and my SURF advisors. I really got to learn how to communicate in a team and how to set small goals and deadlines for myself and how to effectively work in an online remote environment. Initially I was expecting to digest all the material and discover a huge discovery, but when it got hard I got frustrated. I think this was helpful because I got to learn how research in the real world worked. It has taught me that research is meant to be hard and that I should enjoy the ride. Seeing the results at the end were quite nice as it was good to see our final efforts. The SURF experience has affected my future plans in that I plan to pursue a Masters in Computer Science because I feel like a masters with a research emphasis would be quite interesting because I really like the autonomy that I have when determining my own deadlines. My confidence definitely rose because when I got to present to my family and friends at the end, it was really cool to see how much we accomplished and I felt really smart! I would love to extend my note of appreciation to Sherrill Fund for funding my fellowship because it was one of the greatest experiences of my life as I got to learn so much and enjoy the ride as we created an algorithm that will hopefully be used in the future! This is all dedicated to you!
  • Major: Applied Mathematics, Computer Science
  • Sponsor: Sherrill Fund
  • Mentor: James Demmel & Olga Holtz