CS 855 - Symbolic Parallel Computation
and Algebraic Geometry

University of Western Ontario
Computer Science Department

Date: September 11, 2009

Since the discovery of Groebner bases, the algorithmic advances in Commutative Algebra have made possible to tackle many classical problems in Algebraic Geometry that were previously out of reach. However, algorithmic progress is still desirable, for instance when solving symbolically a large system of algebraic (non-linear) equations is needed.

For such a system, in particular if its solution set consists of geometric components of different nature (surfaces, curves, points) it is necessary to combine Groebner bases with decomposition techniques, such as triangular decompositions.

The efficiency of this approach depends on its ability to detect and exploit geometrical information during the solving process. Its implementation, which naturally involves symbolic parallel computations, is another challenging topic.

The motivation of this course is the parallelization of triangular decompositions for solving systems of algebraic equations. 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 present a triangular decomposition algorithm and its applications.

Prerequisites.

A good familiarity with linear algebra and complexity analysis of algorithms is necessary. However, no background in symbolic computations or parallel computations is required.

Lectures (tentative schedule).

Week Jan. 9-15	Introduction to Parallel Symbolic Computations
Week Jan. 16-22	No lecture.
Week Jan. 23-29	Performance and scalability of parallel algorithms, PRAM models
Week Jan. 30-5	Parallel Complexity Theory
Week Feb. 6-12	Parallel Sorting I
Week Feb. 13-19	Parallel Sorting II
Week Feb. 20-26	Parallel Dense Matrix Operations
Week Mar. 6-12	Solving systems of non-linear equations in parallel
Week Mar. 13-19	Solving systems of linear equations in parallel
Week Mar. 20-26	Triangular decomposition algorithms
Week Mar. 27-2	No lecture.
Week Apr. 3-9	Parallel algorithms for GCD computations
Week Apr. 10-16	Processor Efficient Parallel algorithms for Linear Algebra
Week Apr. 17-23	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

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