CS 775 Parallel Algorithms in Scientific Computing


This course studies efficient algorithms to exploit the full potential of the parallel computer technology. Emphasis is on different techniques for obtaining maximum parallelism in various numerical algorithms, especially those occurring when solving matrix problems and partial differential equations, and the subsequent mapping onto the computer. Example applications include: image processing, computational fluid dynamics, structural analysis. Assignments will involve programming on existing parallel machines as available.


Introduction to Parallel Computing, by V. Kumar, A. Grama, A. Gupta, G. Karypis, (1994), Benjamin/Cummings.


Three hours of lecture per week.


Parallel Architecture and Performance Models

Vector processors, distributed memory, SMP, NUMA, Beowulf clusters. Interconnection topologies. Bandwidth, latency, speedup, Amdahl's law.

Message Passing/Shared Memory Programming

High level description with examples and implementation. MPI, PVM, OpenMP, automatic parallelizing compilers, threads.

Matrix Computations

Dense and sparse matrix multiplication, Gaussian elimination, tridiagonal solvers. Data mapping onto parallel computers. Jacobi, Gauss-Seidel, SOR, Krylov subspace methods.

Fast Fourier Transform

Butterfly algorithm, fast multipole methods.

Graph Partitioning

Bisection, spectral, Metis, ParMetis.

Domain Decomposition Methods

Algorithm decomposition: additive/multiplicative Schwarz, overlapping/nonover-lapping methods.

Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

Valid HTML 4.01!Valid CSS! Last modified: Friday, 01-Jun-2012 11:00:32 EDT