Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, April 17, 2013 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

[Dissertation Talk] Avoiding Communication in Dense Linear Algebra

Seminar: Departmental | April 17 | 12:10-1 p.m. | 380 Soda Hall

Grey Ballard, UC Berkeley

Electrical Engineering and Computer Sciences (EECS)

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