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.
Graph expansion, complexity, and numerical stability of algorithms
Olga Holtz, UC-Berkeley – Mathematics
Feb 25 2014 - 10:55am