UPMC, Master 2 Mathematics and Applications, Spring 2017
High performance compting, large scale linear algebra algorithms, numerical stability
| Syllabus | Schedule of Lectures | Recommended reading |
Syllabus, Fridays 2 PM - 4PM
Instructor: L. Grigori
Location: Tour 15/25, salle 103, UPMC
The objective of this lecture is to provide the required background for
designing efficient parallel numerical algorithms, as well as an introduction
to the most recent algorithms in large-scale numerical linear algebra,
an analysis of their numerical stability, and a study of their complexity
in terms of computation and communication. The operations considered
correspond to the most costly questions that lie at the heart of many
complex numerical simulations.
The lecture will also discuss one of the major challenges in high performance
computing which is the increased communication cost.
The traditional metric for the cost of an algorithm is the number of
arithmetic or logical operations it performs. But the most expensive
operation an algorithm performs, measured in time or energy, is not
arithmetic or logic, but communication, i.e. moving data between
levels of a memory hierarchy or between processors over a network.
The difference in costs can be orders of magnitude, and is growing
over time due to technological trends like Moore's Law. So our goal
is to design new algorithms that communicate much less than
conventional algorithms, attaining lower bounds when possible.
This course will also present an overview of novel "communication-avoiding" (CA)
algorithms that attain these goals, including communication lower bounds,
and practical implementations showing large speedups. Problem domains
considered include dense and sparse linear algebra and graph theory.
> Top of the page
Schedule of lectures
> Top of the page
Recommended reading (evolving)
For communication avoiding algorithms:
Lower bounds on communication
Communication avoiding algorithms for dense linear algebra
Communication avoiding algorithms for iterative methods and preconditioners
Communication avoiding for sparse matrices and graphs
Hardware aware algorithms
Randomized numerical linear algebra: overview, elementary proofs, low rank approximation algorithms, sketching algorithms
> Top of the page
|
