Communication-Avoiding Algorithms for Linear Algebra, Machine Learning and Beyond

Explore communication-avoiding algorithms that minimize data movement costs in computational systems through this conference talk from the Simons Institute's Complexity and Linear Algebra Boot Camp. Learn how communication costs in time and energy far exceed arithmetic costs when moving data between memory hierarchy levels or across network processors, making algorithm optimization crucial for efficiency. Discover asymptotically superior algorithms compared to classical counterparts across various linear algebra and machine learning problems, many of which achieve theoretical lower bounds. Examine recent advances in automating the design and implementation of these optimized algorithms, while gaining insight into current open problems in the field. Understand the fundamental trade-offs between computation and communication in modern computing architectures and how strategic algorithm design can dramatically improve performance in large-scale computational tasks.