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

University of Western Ontario
Computer Science Department

Date: September 11, 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.

Prerequisites.

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.

• MPICH-A Portable Implementation of MPI
• Development Tools for MPICH
• CS 402/CS 535: Parallel and Distributed Computing at UWO
• CS 424b - CS 556b Foundations of Computational Algebra at UWO
• Parallel Algorithms (WISM 459, 2005/2006) by Rob Bisseling
• Topics in Parallel Computing (CS 838, Univ. of Wisconsin-Madison, Spring 1999) by Pavel Tvrdik
• Parallel Algorithms (CS 662, San Diego Univ., Spring 1996)by Roger Whitney
• U.C. Berkeley CS267/EngC233 Home Page by James Demmel
• MIT 6.895 Fall 2003 by Charles E. Leiserson

Conferences.

• PARALLEL PROCESSING AND APPLIED MATHEMATICS
• SIAM Conference on Parallel Processing for Scientific Computing
• Some Compiler and Parallel Computing Conferences
• IEEE International Parallel & Distributed Processing Symposium
• ACM Symposium on Parallelism in Algorithms and Architectures
• Some Theoretical Computer Science Conferences

Papers on Parallel Scientific Computing.

• Estimating Execution Time of Distributed Applications by Maciej Drozdowski
• pARMS: A Package for Solving General Sparse Linear Systems on Parallel Computers by Y. Saad and M. Sosonkina
• Fast Scheduling and Partitioning Algorithm in the Multi-processor System with Redundant Communication Resources by Eryk Laskowski
• Evaluation of Parallel Programs by Measurement of Its Granularity by Jan Kwiatkowski
• Parallel Triangular Decompositions of an Oil Refining Simulation by Xiaodong Zhang
• Parallel Algorithms for Arrangements by Richard Anderson, Paul Beame and Erik Brisson
• Efficient parallel computation of arrangements of hyperplanes in d dimensions by Torben Hagerup, Hermann Jung and Emo Welzl
• Recursive Array Layouts and Fast Parallel Matrix Multiplication by Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala and Mithuna Thottethodi
• A Quantitative Comparison of Parallel Computation Models by Ben H.H. Juurlink and Harry A.G. Wijshoff
• Towards Efficiemlcy and Portability: Programming with the BSP Model by Mark Gouclreau, Kevin Lang Satish Rao, Torsten Suel and Thanasis Tsantilas

Papers on Parallel Symbolic Computing.

• A BSP Parallel Model for the Göttfert Algorithm over F2 by Fatima Abu Salem
• Fast Rectangular Matrix Multiplications and Improving Parallel Matrix Computations by Xiaohan Huang and Victor Y. Pan
• $NC^2$ Computation of Gcd-free Basis and Application to Parallel Algebraic Numbers Computation by T. Gautier and J.L. Roth
• Processor-Efficient Parallel Matrix Inversion over .Abstract Fields: Two Extensions by W. Eberly
• Complexity of the Wu-Ritt decomposition by Á. Szántó
• Distributed Partial Evaluation by Michael Sperber, Herbert Klaeren and Peter Thiemann
• Processor Efficient Parallel Solution of Linear Systems over an Abstract Field by E. Kaltofen and V. Pan
• On the Parallel Cbmplexity of Matrix Factorization Algorithms byMauro Leoncini, Giovanni Manzi and Luciano Margara
• Multidimensional, Multiprocessor, Out-of-Core FFTs with Distributed Memory and Parallel Disks by Lauren M. Baptist and Thomas H. Cormen
• Multithreaded Algorithms for the Fast Fourier Transform by Parimala Thulasiraman, Kevin B. Theobald, Ashfaq A. Khokhar and Guang R. Gao
• How much can we speedup Gaussian Elimination with Pivoting? by M. Leoncini
• Communication Efficient Matrix Multiplication on Hypercubes by Himanshu Gupta and P. Sadayappan
• Distributed Data Structures and Algorithms for Gröbner Basis Computation by SOUMEN CHAKRABARTI and KATHERINE YELICK
• On the Correctness of a Distributed Memory Gröbner Basis Algorithm by SOUMEN CHAKRABARTI and KATHERINE YELICK
• Extended Parallelism in the Gröbner Basis Algorithm by Stephen A. Schwab
• A Fine-Grained Parallel Completion Procedure by Reinhard Bündgen, Manfred Göbel and Wolfgang Küchlin
• Parallelization of The Sparse Modular GCD Algorithm for Multivariate Polynomials on Shared Memory Multiprocessors by Mohamed Omar Rayes, Paul S. Wang and Kenneth Weber
• Parallel Computation of Modular Multivariate Polynomial Resultants on a Shared Memory Machine by H. Hong and H. W. Loidl
• A Parallel Completion Procedure for Term Rewriting Systems by Katherine Yelick and Stephen Garland
• Programming Models for Irregular Applications by Katherine Yelick
• Data Structures for Irregular Applications by Katherine Yelick
• Strategy-Accurate Parallel Buchberger Algorithms by G. Attardi and C. Traverso
• Work Efficient Parallel Solution of Toeplitz Systems and Polynomial GCD by John H. Reif
• Processor-Efficient Parallel Matrix Inversion over .Abstract Fields: Two Extensions by W. Eberly
• A New Approach to Parallel Computation of Polynomial GCD and to Related Parallel Computations over Fields and Integer Rings by Victor Y. Pan
• Processor-Efficient Parallel Computation of Polynomial Greatest Common Divisors by Erich Kaltofen