Parallel algorithms for Scientific Computing

This course is organized by the Division of Scientific Computing at the IT Department (DCS)
If you intend to participate in the course, please send an email to maya.neytcheva@it.uu.se. Thank you.

General description

The course focuses on parallel algorithms for scientific computing problems (not on parallel programming). We will cover parallel algorithms for a range of problem classes in Scientific Computing, from linear algebra (with a focus on sparse problems related to solving PDE), iterative solvers, multigrid, particle interaction problems (Barnes-Hut, multipole etc) to algorithms, typical for data intensive applications and machine learning.

The material is split into three parts as follows.

Examination and grading

The course gives 5 hp. To pass the course, one has to fulfill an assignment for each part, to be delivered in a written form. It is possible to obtain 7.5 hp by doing an additional project that includes some testing on a parallel computer facility (to be discussed individually).

Course prerequisites

Experience of scientific computing problems and basic knowledge of scientific computing algorithms. Detailed knowledge of algorithms like conjugate gradients, multigrid and multipole approximations is not needed. Experience of programming for scientific computing in languages like C, but you do not need to have taken a course in parallel programming to do the assignments. An optional project work (for obtaining 7,5 hp) should contain implementation and experiments using a parallel system, thus, presumably more experience of parallel programming will be needed.
The lectures will be given at the Department of Information Technology, Uppsala University.

Lecturers

Sverker Holmgren (SH) Carl Nettelblad (CN) Maya Neytcheva (MN)

Additional course materials (to be added during the course)

Part 1: Assignment
Part 2:
Part 3:

Detailed time schedule

Date Topic(s) Time
Location
Lecturer
Nov 28 Lecture 1: Sparse matrices and storage schemes. 13:15-15:00
2414b
MN
Nov 30 Lecture 2: Iterative methods and parallelization. Pipelined versions of CG and GMRES - an attempt to achieve better scaling for Very Large/Exascale 10:15-12:00
2415b
MN
Dec 6 Lecture 3: Preconditioners - parallelization aspects 13:15-15:00
1406
MN
Dec 7 Parallelization of incomplete factorization methods. Talk by prof. Thomas Huckle at the TDB seminar 13:15-14:00
2344
MN
     
XX Lecture 1: TBA XX
XXXX
SH
XX Lecture 2: TBA XX
XXXX
SH
XX Lecture 3: TBA XX
XXXX
SH
     
XX Lecture 1: TBA XX
XXXX
CN
XX Lecture 2: TBA XX
XXXX
CN
XX Lecture 3: TBA XX
XXXX
CN

Recommended books:

  1. Part 1:
    1. Data storage schemes for parallel computations old source, 1992, new source, 2017
    2. P. Ghysels, W. Vanroose, Hiding global synchronization latency in the preconditioned conjugate gradient algorithm, Parallel Computing, 40 (2014), pp. 224-238, (also here)
    3. P. Sanan, S.M. Schnepp, D.A. May, Pipelined flexible Krylov subspace methods
    4. Pipelined solvers, performance comparison
    5. PETSc: pipelined CG , PETSc: pipelined GMRES
  2. Part 2: To come
  3. Part 3: To come

Last changed on Nov 22, 2017.
Mail to: Maya dot Neytcheva "at" it dot uu dot se "