CS 855 - Symbolic Parallel Computation
and Algebraic Geometry


University of Western Ontario
Computer Science Department


Date: September 7, 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.
Conferences.
Papers on Parallel Scientific Computing.
Papers on Parallel Symbolic Computing.