# Graph expansion, complexity, and numerical stability of algorithms

Tuesday, February 25, 2014 -

4:30pm to 5:30pm

Please note special day (Tuesday). In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion approach produces first lower bounds on the communication costs of Strassen's and other fast matrix multiplication algorithms. I will discuss both the general method and its concrete implementations, pointing out the interplay between communication and arithmetic as well as numerical stability of various algorithms.

Speaker:

Olga Holtz

UC-Berkeley - Mathematics

Event Location:

Fine Hall 214