The Department of Applied Mathematics is pleased to host this series of colloquium lectures, funded in part by a generous gift from the Boeing Company. This series will bring to campus prominent applied mathematicians from around the world.
Speaker: James Demmel, University of California, Berkeley
Date: January 25th, 2018, 4pm, reception to follow
Location: (SMI 102)
Title: Communication-Avoiding Algorithms for Linear Algebra and Beyond.
Abstract: Algorithms have two costs: arithmetic and communication, i.e. moving data between levels of a memory hierarchy or processors over a network. Communication costs (measured in time or energy per operation) already greatly exceed arithmetic costs, and the gap is growing over time following technological trends. Thus our goal is to design algorithms that minimize communication. We present algorithms that attain provable lower bounds on communication, and show large speedups compared to their conventional counterparts. These algorithms include direct and iterative linear algebra, for dense and sparse matrices, direct n-body simulations, and some machine learning algorithms. Several of these algorithms exhibit perfect strong scaling, in both time and energy: run time (resp. energy) for a fixed problem size drops proportionally to the number of processors p (resp. is independent of p). Finally, using recent extensions of the HolderBrascamp-Lieb inequalities, we show how to generalize our approach to algorithms involving arbitrary loop nests and array accesses, assuming only that array subscripts are affine functions of the loop indices.