Skip to Main content Skip to Navigation
Book sections

Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra

Laura Grigori 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
LJLL - Laboratoire Jacques-Louis Lions, INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris
Abstract : Modern, massively parallel computers play a fundamental role in a large and rapidly growing number of academic and industrial applications. However, extremely complex hardware architectures, which these computers feature, effectively prevent most of the existing algorithms to scale up to a large number of processors. Part of the reason behind this is the exponentially increasing divide between the time required to communicate a floating-point number between two processors and the time needed to perform a single floating point operation by one of the processors. Previous investigations have typically aimed at overlapping as much as possible communication with computation. While this is important, the improvement achieved by such an approach is not sufficient. The communication problem needs to be addressed also directly at the mathematical formulation and the algorithmic design level. This requires a shift in the way the numerical algorithms are devised, which now need to reduce, or even minimize when possible, the number of communication instances. Communication avoiding algorithms provide such a perspective on designing algorithms that minimize communication in numerical linear algebra. In this document we describe some of the novel numerical schemes employed by those communication avoiding algorithms, with a particular focus on direct methods of factorization.
Complete list of metadatas
Contributor : Laura Grigori <>
Submitted on : Wednesday, December 20, 2017 - 5:34:37 PM
Last modification on : Saturday, March 28, 2020 - 2:13:53 AM



Laura Grigori. Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra. Mariano Mateos; Pedro Alonso. SEMA SIMAI Springer Series, 13, Springer, pp.153-185, 2017, Computational Mathematics, Numerical Analysis and Applications, 978-3-319-49631-3. ⟨10.1007/978-3-319-49631-3_4⟩. ⟨hal-01669315⟩



Record views