People/Web Search Calendar Emergency Info A-Z Index UVA Email University of Virginia

Computer Science Colloquia

Friday, April 5, 2013
Grey Ballard
Host: Andrew Grimshaw

3:30 PM, Rice Hall, Room 130 (auditorium), followed by a reception in Rice Hall Fourth Floor Atrium (west end)

Avoiding Communication in Linear Algebra

ABSTRACT

As our computing capabilities grow, the size and complexity of numerical simulations that today's computational scientists conduct continue to increase. Ultimately, these simulations are limited either by the sheer quantity of computation required by the simulation or by the inability of the software employed to make effective use of the hardware. The gap between the peak capabilities of the hardware and the achieved performance of numerical simulations is caused in large part by the high cost of communication, or movement of data, between processors and throughout the memory hierarchy of a single processor.

As expected, much of this communication cannot be avoided when using parallelism to solve our problems; however, many standard algorithms in linear algebra move more data than necessary. I will discuss lower bounds we have proved on the communication required by a wide class of algorithms and whether standard approaches attain these bounds. In several cases where gaps exist between algorithms and lower bounds, we have developed new algorithms that communicate asymptotically less than previous ones and outperform them on a variety of platforms. These include algorithms for solving linear systems, least squares problems, eigenvalue problems, and parallelization of Strassen's matrix multiplication algorithm.

I'll talk about some open problems in this area, and I'll also discuss the possibility of reducing both communication and computation in dense linear algebra using algorithms that perform asymptotically fewer floating point operations than Strassen's.

Bio: Grey Ballard is currently a PhD candidate at the University of California at Berkeley, working in the Parallel Computing Laboratory. His research interests include improving fundamental algorithms for scientific computing. His work has been recognized by SIAM's Linear Algebra Prize, by best paper awards at the ACM Symposium on Parallelism in Algorithms and Architectures and the IEEE International Parallel and Distributed Processing Symposium, and by the UC Berkeley C.V. Ramamoorthy Distinguished Research Award.

*Mr. Ballard is a faculty candidate for the Department of Computer Science