
News
Colloquia
Communication Avoiding Algorithms for Linear Algebra and Beyond
Speaker: Professor James Demmel
University of California, Berkeley
November 7, 2012  4:00 p.m. to 5:00 p.m.
Reception at 3:3opm
Location: DCC 337
Hosted By: Prof. Fran Berman (x4873)
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 nbody 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 p (resp. is independent of p). Finally, we describe extensions
to algorithms involving arbitrary loop nests and array accesses,
assuming only that array subscripts are linear functions of the loop indices.
Bio:
James Demmel is the Dr. Richard Carl Dehmel Distinguished Professor of
Computer Science and Mathematics at the University of
California at Berkeley. His personal research interests are in numerical
linear algebra, high performance computing, and communication avoiding
algorithms in general. He is known for his work on the LAPACK and ScaL APACK
linear algebra libraries. He is a member of the
National Academy of Sciences, National Academy of Engineering, a Fellow of
the ACM, IEEE and SIAM, and winner of the IEEE Computer Society Sidney
Fernbach Award, the SIAM J. H. Wilkinson Prize in Numerical Analysis and
Scientific Computing, and numerous best paper prizes, including being the
only 3time winner of the SIAM Linear Algebra (SIAG/LA) Prize. He was an
invited speaker at the 2002 International Congress of Mathematicians and
the 2003 International Congress on Industrial and Applied Mathematics.
Last updated: October 23, 2012

