Communication-Avoiding Algorithms for Linear Algebra and Beyond
The Center for Computational and Applied Mathematics is sponsoring a distinguished lecture series taking place both in the fall and spring semesters. The first talk will be on Oct. 19 at 3:30 pm in LWSN 1142. Prof. James Demmel the Dr. Richard Carl Dehmel Distinguished Professor of mathematics and computer science at University of California, Berkeley, will present a lecture titled "Communication-Avoiding Algorithms for Linear Algebra and Beyond." Refreshments will be served outside the lecture hall at 3 pm.
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 are for direct and iterative linear algebra, for dense and sparse matrices, as well as direct n-body simulations. 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, we describe extensions to algorithms involving very general loop nests and array accesses, in a way that could be incorporated into compilers.
James Demmel is the Dr. Richard Carl Dehmel Distinguished Professor of mathematics and computer science at University of California, Berkeley. He is a member of the National Academy of Sciences (2011) and the National Academy of Engineering (1999).
Some of his recent awards include the ACM Paris Kanellakis Theory and Practice Award (2014), IPDPS Charles Babbage Award (2013), SIAG on Linear Algebra Prize (2012), and the Sidney Fernbach Award (2010). He also served as Chief Scientist of CITRIS: the Center for Information Technology Research in the Interest of Society.