Colloquium: Avoiding Communication in Linear Algebra

Avoiding Communication in Linear Algebra
Date:  Tuesday, January 22, 2013 – 11:00
Location:  Manchester Hall, Room 016
Speaker:  Grey Ballard (Computer Science – UC Berkeley)

11:00—12:00 noon, Manchester Hall, Room 016
(Reception to following in the third floor lounge)

Abstract: The running time of an algorithm depends not only on the amount of computation it performs, but also on its communication requirements (i.e., how much data it moves up and down the memory hierarchy and between processors).  In many cases, we can significantly decrease the running times of numerical computations by reformulating existing algorithms to avoid communication.

I will discuss communication lower bounds we have proved for a wide class of algorithms in numerical linear algebra and whether known algorithms achieve these lower bounds.  In several cases where a gap exists between known algorithms and lower bounds, we have developed new algorithms which communicate asymptotically less than previous ones. These include algorithms for solving linear systems, least squares problems, eigenvalue problems, and parallelization of Strassen’s matrix multiplication algorithm.  I’ll also show some performance results that demonstrate how the new algorithms outperform state-of-the-art implementations of old approaches.

Bio: Grey Ballard is a PhD candidate in computer science at UC Berkeley.  He graduated from Wake Forest University in 2006, majoring in math and computer science, and completed his Master’s degree in math in 2008, also at Wake Forest.  Grey’s main research interests lie in numerical linear algebra, parallel computing, and computational science.  He is interested in designing numerical algorithms that can harness the growing computational power being delivered by today’s massively parallel machines.