Communication-Avoiding Algorithms for Linear Algebra, Machine Learning, 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 new algorithms that communicate asymptotically less than their classical counterparts, for a variety of linear algebra and machine learning problems, demonstrating large speedups on a variety of architectures. Some of these algorithms attain provable lower bounds on communication. We describe generalizations of these bounds, and optimal algorithms, to arbitrary code that can be expressed as nested loops accessing arrays, and to account for arrays having different precisions.

numerical analysis

Audience: researchers in the topic

E-NLA - Online seminar series on numerical linear algebra

Series comments: E-NLA is an online seminar series dedicated to topics in Numerical Linear Algebra. Talks take place on Wednesdays at 4pm (Central European Time) via Zoom and are initially scheduled on a weekly basis.

To join the seminar, please complete the sign up form at the bottom of the webpage. Information about how to connect to the conference call will be circulated via email to all registered attendees.