**
**

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