On modern computer architectures, communication, i.e., the movement of data, is much more expensive than floating point operations in terms of time and energy. This is true both in the sequential setting, where communication involves the movement of data between cache levels and main memory, and in the parallel setting, where communication involves sending messages between processors. For algorithms with a low computational complexity, performance can thus be limited by the cost of communication. This has motivated the development of communication-avoiding algorithms which reduce or minimize data movement (at perhaps the cost of a small additional amount of computation).
In this introductory talk, we present an overview of the current state-of-the-art in the development of communication-avoiding algorithms for both direct and iterative numerical linear algebra. Research in this area requires a three-pronged approach: proving lower bounds on the amount of communication required by an algorithm, designing stable methods that attain those bounds, and developing efficient implementations for particular machines/applications. We touch on work in each of these areas and also discuss major challenges and remaining open problems.