**
**

**
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.
**

**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*by T. Gautier and J.L. Roth^{2}Computation of Gcd-free Basis and Application to Parallel Algebraic Numbers Computation*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