MTL415: Parallel Algorithms

3 Credits (3-0-0)

Pre-requisites: MTL342

Overlaps with: MTL765

Parallel architecture: Shared/local memory systems, pipelining, hypercubes, mesh, linear array etc. Degree of parallelism, Speed-up and efficiency of a parallel algorithm. Principles of parallel algorithm design. Basic communication operations. Parallel algorithms: searching and sorting, matrix-vector and matrix-matrix multiplication for dense, band and triangular matrices. Parallel algorithms for direct methods for dense, band and triangular matrices. Cholesky method. Solving recurrence relations. Parallel iterative methods for finite difference equations of elliptic boundary value problems: point-Jacobi, line Jacobi, block Jacobi methods, 2 colour and multicolour Gauss-Seidel, SOR, SSOR methods. Domain decomposition method in one and two dimensions. Parallel preconditioned conjugate gradient methods. Quadrant interlocking factorization.