CS 855 - Parallel Scientific Computing: Models, Algorithms and Implementation

University of Western Ontario
Computer Science Department

Date: September 7, 2009

The motivation of this course is the parallelization of algorithms for solving systems of equations, both linear and non-linear. The topics covered are the computer science techniques needed for achieving this goal.

The first third of this course will be devoted to the complexity analysis of parallel algorithms. In the second third, we will discuss parallel algorithms for scientific computations, with a view toward symbolic computations. Then, we will focuss on parallel solvers and their applications.

A good familiarity with linear algebra and complexity analysis of algorithms is necessary.
Lectures (tentative schedule).
Week Jan. 8-14 Performance and scalability of parallel algorithms
Week Jan. 15-21 PRAM, BSP models
Week Jan. 22-28 Parallel Complexity Theory
Week Jan. 29-4 No lecture.
Week Feb. 5-11 Parallel Complexity Theory
Week Feb. 12-18 Parallel Sorting
Week Feb. 19-25 Parallel Sorting
Week Feb. 26-4 No lecture.
Week Mar. 5-11 Parallel Matrix Operations
Week Mar. 12-18 Solving systems of linear equations in parallel
Week Mar. 19-25 Task scheduling and load balancing
Week Mar. 26-1 Parallel algorithms for GCD computations
Week Apr. 2-8 Programming environments for parallel solvers
Week Apr. 9-15 Challenges for parallel solvers
Week Apr. 16-22 Project presentations
Student Evaluation.
No quizzes, exams or assignments. Each student chooses a subject based on the articles posted below in the area of Parallel Symbolic Computing. More papers will be posted soon. Then the student writes a report and presents it during one of the two last weeks of classes.
Software and Courses.
These are links to some books and software related to the course.
Papers on Parallel Scientific Computing.
Papers on Parallel Symbolic Computing.