UPMC, Master 2 Mathematics and Applications, Fall 2019
High performance computing for numerical methods and data analysis
| Syllabus | Schedule of Lectures | Recommended reading |
Syllabus, Wednesdays 9 AM - 12 PM
Instructor: L. Grigori
Location: 15-25/103 (except on October 24 when the location will be 15-25/101), UPMC
The objective of this course is to provide the necessary background for designing efficient parallel algorithms in scientific computing as well as in the analysis of large volumes of data. The operations considered are the most costly steps at the heart of many complex numerical simulations. Parallel computing aspects in the analysis of large data sets will be studied through tensor calculus in high dimension. The course will also give an introduction to the most recent algorithms in large scale numerical linear algebra, an analysis of their numerical stability, associated with a study of their complexity in terms of computation and communication.
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 tensors.
> 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
Randomized numerical linear algebra: overview, elementary proofs, low rank approximation algorithms, sketching algorithms
> Top of the page
|
