CS 652b -- Algorithms and Software for Symbolic Solvers of Polynomial Systems

Course Description

Systems of equations have been studied for centuries. However, the development of symbolic (or exact) methods for solving them is quite recent. No efficient software existed 10 years ago. Many theoretical and practical questions are still open and many problems in mathematical and engineering sciences are solved today by symbolic solvers. Digital signal processing, theoretical physics, cryptography, auto-correcting codes are some of the areas where exact solutions of systems of equations are used. In this course we will describe the key ideas of some of the most popular algorithms for solving systems of equations symbolically (Groebner bases, triangular decompositions). These algorithms are quite elegant but their implementation leads to several difficult challenges. We will explain how emerging techniques (modular algorithms, distributed computations) address these difficulties. Finally, a detailed application will be presented.

Prerequisites

It is assumed that the student has taken at least one undergraduate course in Linear Algebra and one undergraduate course about data-structures and algorithms. Every concept from Abstract Algebra (but not from Linear Algebra) needed in the course will be reviewed. But having some knowledge in Abstract Algebra would help the student enjoy the lectures better.

Instructor

Lecture Notes and Textbook

Notes of each lecture will be available on the course website, approximatively one week after the oral presentation. The format (Postscript, PDF, ...) of these notes will be announced later.

There are two recommended textbooks for the course. The other references are given for the curious reader.

• Ideals, Varieties, and Algorithms. D. Cox, J. Little and D. O'Shea. Spinger-Verlag, 1992. (RECOMMENDED).
• An Introduction to Groebner Bases. W. W. Adams and P. Loustaunau. American Mathematical Society, 1994. (SUPPLEMENTARY).
• Groebner Bases: A computational approach to commutative algebra. T. Becker and V. Weispfenning. Springer Verlag, 1991 (SUPPLEMENTARY).
• Using Algebraic Geometry. D. Cox, J. Little and D. O'Shea. Spinger-Verlag, 1998. (SUPPLEMENTARY).

Course Website

The course web site is accessible from: http://www.csd.uwo.ca/~moreno/

Please check the site often for updates on lecture notes and errata. Also be aware that the course website is not a substitute for actual classroom attendance!

Lecture Topics

1. An Introduction to Systems of Polynomial Equations and Symbolic Solvers.
2. A review of Polynomial Rings.
3. Resultants, Sub-Resultants, Discriminants and Gcds.
4. Field Extensions, Product of fields.
5. Groebner Bases over Fields.
6. A Presentation of some Symbolic Solvers.
7. Affine Varieties and Radical Polynomial Ideals.
8. Decompositions of Zero-Dimensional Ideals.
9. Prime and Primary Decompositions.
10. Characteristic Sets, Regular Chains.
11. Triangular Decompositions.
12. Implementation of Symbolic Solvers.
13. An Application of Symbolic Solvers.

Class Schedule

Lectures: 3 hours (Thursdays from 10:00am to 1:00pm in MC316)

Each student is expected to attend the lectures. In particular, quizzes (short written tests) may take place without notice.

Computing Facilities

Each student will be given an account on the Computer Science Department senior undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department's Rules of Ethical Conduct

Email Contact

The instructor will occasionally need to send email messages to the whole class, or to students individually. Each student must read her/his email on a frequent and regular basis.

Students can ask questions via email, however if there are any large, somewhat complicated issues, it is recommended to discuss them during office hours.

Email will be sent by the instructor to UWO (GAUL, ORCCA, ....) email addresses only. Similarly, students should write to the instructor using UWO email addresses only. Emails from non-academic accounts will be automatically ignored.

Student Evaluation

The course is very project oriented. The project constitute 60% of the course mark. There is no midterm or final examination. The remaining 40% are based on one assignment (20%) and quizzes (20%). The goal of the assignment and quizzes is to prepare the student for the project. In order to successfully complete the course, a student must achieve at least 50% on the project and at least 50% as an overall average over all assignments and quizzes. This is to prevent a serious lack of preparation to the project.

There will be at least three quizzes given, but only your best two will count toward your mark.

The assignment consists of a set of programming exercises in a Computer Algebra System of your choice among several ones proposed by the instructor. This choice should be related to the choice of your project, if your project involves a programming or experimental work.

Projects will be presented to students at the beginning of February, chosen by the students one week later and defended by the students at the beginning of April. Projects are individual.

A typical project will be based on a research article. Depending on the topic, the project may be of different natures: a presentation of the article, experimentations based on the article, implementation of an algorithm in the article, a combination of the previous activities.

The assignment is due three weeks after the project is chosen. Extension times will be granted only by the course instructor.

Ethical Conduct

You are responsible for reading and respecting the Computer Science Department's policy on Scholastic Offenses and Rules of Ethical Conduct.