CS 623 - Parallel Iterative Computing

Bulletin Description

The course will present advanced computational science techniques needed to support large scale engineering and scientific computations. Emphasis on iterative methods for solving large sparse linear systems and parallel implementations of iterative techniques.

Prerequisites

CS 537 or consent of the instructor.

Expected Preparation

Programming proficiency in Fortran or C.

Student Learning Outcomes

Students will learn how to use iterative methods for solving large sparse linear systems on high-performance computers. They will learn how to partition a domain, select algorithms, obtain and develop code for computing solutions in parallel environments. Students will gain hands-on experience in writing parallel programs on a shared-memory parallel computer using high-level directives.

Syllabus Information

Week by Week Course Outline:

This is a sample outline. Exact outline will be determined by the instructor offering this course.

 

Weeks Topics
1 Parallel Computing Overview: high performance computers, parallel programming language and skills, parallel computing techniques;
2-3 Structured and Unstructured Matrices: discretized partial differential equations, graph representations, permutations and reorderings, sparse matrix storage schemes, basic sparse matrix operations;
4 Basic Iterative and Projection Methods: point and block relaxation methods, iteration matrices and preconditioning, general convergence results, general projection methods, parallel implementations;
5 Multigrid Methods: smooth and rough errors, restriction and interpolation, V cycle and W cycle algorithms, parallel multigrid methods;
6-7 Krylov Subspace Methods (I): Krylov subspace, Arnoldi's method, FOM, GMRES, conjugate gradient algorithm;
8-10 Krylov Subspace Methods (II): Lanczos biorthogonalization, Lanczos algorithm for linear systems, BCG and QMR algorithms, transpose free variants, practical and parallel implementations;
11 Preconditioned Iterations: preconditioned conjugate gradient, preconditioned GMRES, flexible variants, preconditioned CG for normal equations;
12-13 Preconditioning Techniques: basic iterative methods as preconditioners, incomplete LU factorization, threshold strategies and ILUT, approximate inverse preconditioners, block preconditioners
14-15 Parallel Preconditioners: block Jacobi preconditioner, polynomial preconditioners, multicoloring, multilevel ILU preconditioners, distributed ILU and SSOR.

 

Grading:

Exact details about graded work in this course will be determined by the instructor offering the course and will be made available in the syllabus during the first class meeting. Typically, a student's grade will be determined by a weighted average of homework assignments, programming projects, midterm and final examinations. A typical weighting is:

Homework - 25%

Programming projects - 25%

Midterm Examination - 25%

Final Examination - 25%

Letter Grades: A: 100-86, B: 85-76, C: 75-76, E: 59-0.

Possible Textbooks:

Text books will be determined by the instructor. Suggested text books:

Iterative Methods for Sparse Linear Systems,
Yousef Saad, 1996, PWS Publishing Company;
A Multigrid Tutorial, by William Briggs, 1986, SIAM.