CS6652A: Algorithms and Software for Symbolic Solvers for Polynomial Systems, Fall 2017
Welcome to CS6652A, 2017!
- First lecture (2:30-5:30pm, Wednesday, Sept. 13th): Introduction, motivation and work plan
Lecture Materials
| Given | Topic | Slides | |
| Lecture 1 | Wed. Sept. 13 | Polynomial adata-types | slides |
| Lecture 2 | Wed. Sept. 20 | Modular methods for polynomial and matrix arithmetic | slides |
| Lecture 3 | Wed. Sept. 27 | Asymptotically fast algorithms for polynomial and matrix arithmetic | slides |
| Lecture 4 | Wed. Oct. 4 | Polynomial ideals and algebraic varieties | slides |
| Lecture 5 | Wed. Oct. 18 | Algebraic numbers and their representations | TBA |
| Lecture 6 | Wed. Oct. 18 | Regular chain theory | TBA |
| Lecture 7 | Wed. Oct. 25 | Real algebraic numbers and their representations | TBA |
| Lecture 8 | Wed. Nov. 1 | Cylindrical decompositions of semi-algebraic sets | TBA |
| Lecture 9 | Wed. Nov. 8 | Non-cylindrical decompositions of semi-algebraic sets | TBA |
| Lecture 10 | Wed. Nov. 15 | Polyhedral sets, linear programming (LP) | TBA |
| Lecture 11 | Wed. Nov. 22 | Integer points of polyhedral sets, integer linear programming (ILP) | TBA |
| Lecture 12 | Wed. Nov. 29 | Parametric integer programming and applications | TBA |
Some research papers used in the lectures are listed below
- Sparse polynomial arithmetic
- Parallel sparse polynomial multiplication using heaps
- Sparse Polynomial Powering Using Heaps
- Sparse polynomial division using a heap
- Parallel sparse multivariate polynomial division
- Highly Scalable Multiplication for Distributed Sparse Multivariate Polynomials on Many-Core Systems
- Matrix Multiplication a Little Faster
- What Every Programmer Should Know About Memory
- Faster Deterministic Sparse Interpolation Algorithms for Straight Line Program Multivariate Polynomials
- Factor Refinement by Bach E., Driscoll J., Shallit J.
- On the solution of algebraic equations over finite fields by E.R.Berlekamp, H.Rumsey, G.Solomon
- A new algorithm for factoring polynomials over finite fields by David G. Cantor and Hans Zassenhaus
- Fast Algorithms for Manipulating Formal Power Series by R.P. Brent and H.T. Kung
- Practical Fast Polynomial Multiplication by Robert T.Moenck
- Notes on the Truncated Fourier Transform by Joris van der Hoeven
- A long note on Mulders' short product by G. Hanrot, P. Zimmermann
- Variations On Computing Reciprocals Of Power Series by Arnold Schönage
- Comparing Several GCD Algorithms by Jebelean
- Solving Sparse Linear Equations Over Finite Fields by Douglas H. Wiedemann
- Algebraic factoring and rational function integration by Barry M. Trager
Some research slides used in the lectures are listed below
Some Maple programs used in the lectures are listed below
Some reference books are listed below
- Modern Computer Algebra
- Ideals, Varieties, and Algorithms
- Using Algebraic Geometry
- Algorithms in Real Algebraic Geometry
- Theory of linear and integer programming
Computer algebra systems and related software used in this course
Quizzes and Projects
Tentative Quiz and Project Schedule
| Given | Due | Weight | |
| Quiz 1 | Wed. Oct. 4 | 3:30-4:00pm | 10% |
| Quiz 2 | Wed.Nov. 1 | 3:30-4:00pm | 10% |
| Project selection | Wed. Nov. 8 | 3:00 - 6:00pm | |
| Quiz 3 | Wed. Nov. 22 | 3:30-4:00pm | 10% |
| Quiz 4 | Wed. Dec. 6 | 2:30-3:00pm | 10% |
| Project presentations | Wed. Dec. 6 | 3:00 - 6:00pm | 60% |
Teaching Crew and Hours
- Instructor
Marc Moreno Maza
email: moreno@csd.uwo.ca
Lecture hours: 2:30-5:30pm on Wednesdays
Lecture room: MC 320
Office: Middlesex College, Room 327
Office hours: 1:30-2:30pm on Tuesdays
CS6652A, Fall 2017
Algorithms and Software for Symbolic Solvers for Polynomial Systems
Course Outline
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 25 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, computer program analysis 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. These algorithms are quite elegant but their implementation leads to several difficult challenges. We will explain how emerging techniques (modular algorithms, parallel and distributed computations) address these difficulties. A driving application of this course is computer program analysis, with an emphasis on automatic parallelization of computer programs.The following topics will be covered during the lectures:
- Polynomial and matrix data-types
- Modular methods for polynomial and matrix arithmetic
- Asymptotically fast algorithms for polynomial and matrix arithmetic
- Algebraic numbers and their representations
- Polynomial ideals and constructible sets
- Regular chain theory
- Real algebraic numbers and their representations
- Cylindrical decompositions of semi-algebraic sets
- Non-cylindrical decompositions of semi-algebraic sets
- Polyhedral sets, linear programming (LP)
- Integer points of polyhedral sets, integer linear programming (ILP)
- Parametric integer programming and applications
Instructor
Marc Moreno Maza
Email: moreno@csd.uwo.ca
Office: Middlesex College 327
Office hours: 1:30-2:30pm on Tuesdays
Course Materials
There is no specific textbook for this course. Lecture notes, suggested readings and supplementary materials are available electronically on the course website.
Course Website
Students should check the course website http://www.csd.uwo.ca/courses/CS6652a on a regular basis for news and updates. These are the primary method by which information will be disseminated to all students in the class. The missing of critical information due to your failure to check the course website cannot be used as a basis for appeal.
Class Schedule
There is one lecture of 3 hours, on Wednesdays, 2:30pm - 5:30pm in MC 320.
Course Work Evaluation
The overall course grade, out of 100, will be calculated as follows:
- 4 in-class quizzes about key concepts and principles, each worth 10%, the sum of which will constitute 40% of the final grade;
- 1 course project worth 60%;
A CS6652 project topic is chosen by the student from a list of topics proposed by the instructor. Project topics will be posted by Nov. 1st. and each student must choose a project topic by Nov. 8. The projects will be presented in class by the students during the last week of classes. Each presentation will consist of a 15 minute talk followed by questions for 10 minutes.
There is no midterm examination and no final examination.
It is Faculty of Science policy that a student who chooses to write a test or exam deems themselves fit enough to do so, and the student must accept the mark obtained. Claims of medical, physical, or emotional distress after the fact will not be considered.
Scholastic offences are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offence, at this website: http://www.uwo.ca/univsec/pdf/academic_policies/appeals/scholastic_discipline_undergrad.pdf.
Computer-marked, multiple-choice tests and exams may be subject to submission for similarity review by software that will check for unusual coincidences in answer patterns that may indicate cheating.
Every effort will be made to have assignments, quizzes and tests marked and handed back within 2 weeks of the hand-in date.
Tentative Quiz and Project Schedule
| Given | Due | Weight | |
| Quiz 1 | Wed. Oct. 4 | 3:30-4:00pm | 10% |
| Quiz 2 | Wed.Nov. 1 | 3:30-4:00pm | 10% |
| Project selection | Wed. Nov. 8 | 3:00 - 6:00pm | |
| Quiz 3 | Wed. Nov. 22 | 3:30-4:00pm | 10% |
| Quiz 4 | Wed. Dec. 6 | 2:30-3:00pm | 10% |
| Project presentations | Wed. Dec. 6 | 3:00 - 6:00pm | 60% |
- If for any reason the schedule cannot be adhered to, the marks will be pro-rated.
- No electronic devices may be in your possession during tests and exams.
- All exams, tests and quizzes are close-book. A reference sheet (provided by the instructor) is allowed for the Midterm Test and Final Exam, but not for the quizzes.
- In case of questions regarding the marks, please note that no quizzes or exams will be accepted for re-marking later than two weeks after they have been marked. We reserve the right not to re-mark quizzes or exams that have been written in pencil.
- All students are expected to attend all classes. A student found to be missing a large number of classes without acceptable reasons risks being denied a passing grade.
Missed Test or Final Exam
If you are unable to meet a course requirement due to illness or other serious circumstances, you must provide valid medical or supporting documentation to the Academic Counselling Office of your home faculty as soon as possible.
If you are a science student, the Academic Counselling Office of the Faculty of Science is located in WSC 191, and can be contacted at 519-661-3040 or scibmsac@uwo.ca. Their website is http://www.uwo.ca/sci/undergrad/academic_counselling/index.html.
A student requiring academic accommodation due to illness is recommended to follow the policy on Accommodation for Illness http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_illness.pdf (which includes a link to the Student Medical Certificate)
There are no make-up tests or quizzes. If your faculty's Academic Counselling Office has approved your circumstances, the value of the missed test or quiz will be reallocated.
If you miss the Final Exam, contact your faculty's Academic Counselling Office as soon as possible. They will assess your eligibility to write the Special Exam (the name given by the university to a makeup Final Exam).
You may also be eligible to write the Special Exam if you are in a "Multiple Exam Situation": http://www.registrar.uwo.ca/examinations/exam_schedule.html.
Accessibility
Please contact the course instructor if you require lecture or printed material in an alternate format or if any other arrangements can make this course more accessible to you. You may also wish to contact Services for Students with Disabilities (SSD) at 661-2111 ext. 82147 if you have questions regarding accommodation.
Support Services
Learning-skills counsellors at the Student Development Centre (http://www.sdc.uwo.ca) are ready to help you improve your learning skills. They offer presentations on strategies for improving time management, multiple-choice exam preparation/writing, textbook reading, and more. Individual support is offered throughout the Fall/Winter terms in the drop-in Learning Help Centre, and year-round through individual counselling.
Students who are in emotional/mental distress should refer to Mental Health@Western: http://www.health.uwo.ca/mental_health.
for a complete list of options about how to obtain help. Additional student-run support services are offered by the USC http://westernusc.ca/services.
The website for Registrarial Services is http://www.registrar.uwo.ca.