Communication-Avoiding Algorithms for Linear Algebra, Machine Learning and Beyond
Professor James Demmel
Department of Mathematics, University of California at Berkeley
James Demmel is a Dr. Richard Carl Dehmel Distinguished Professor at the
Department of Mathematics, University of California at Berkeley.
He is former Department Chair of Electrical Engineering and Computer Sciences Department,
former Division Chair of Computer Science Division of UC Berkeley and former Chief Scientist
of the Center for Information Technology Research in the Interest of Society.
He is a Fellow of AAAS, AMS, SIAM, IEEE and ACM.
Honours include ACM Paris Kanellakis Theory and Practice Award (2014),
IPDPS Charles Babbage Award (2013), Sidney Fernbach Award (2010),
J. H. Wilkinson Prize in Numerical Analysis and Scientific Computing (1993),
Presidential Young Investigator Award (1986) and
IBM Faculty Development Award (1985). He was elected to the American Academy of Arts and Sciences (2018),
National Academy of Sciences (2011) and
National Academy of Engineering (1999).
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) greatly exceed arithmetic costs, so our goal is to design algorithms that minimize communication. We survey some known algorithms that communicate asymptotically less than their classical counterparts,
for a variety of linear algebra and machine learning problems, often attaining lower bounds.
We also discuss recent work on automating the design and implementation of these algorithms, starting from a simple specification as nested loops.