CS 623 - Parallel Iterative Computing
Credits: 3
Course 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.
Prereqs: CS 537 or consent of the instructor.
Needed Skills
Programming proficiency in Fortran or C.
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.
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.