CS9867B: Algorithmic Properties of Polynomial Rings, Winter 2020



Welcome to CS9867B, 2020!

  • First lecture (13:30-16:30, Monday, Jan. 6): Introduction, motivation and work plan

Lecture Materials

  Given Topic Slides
Lecture 1 Mon. Jan. 13 Saturated ideals, localization and direct products (1/2) slides
Lecture 2 Mon. Jan. 20 Saturated ideals, localization and direct products (2/2) slides
Lecture 3 Mon. Jan. 27 Univariate polynomials and resultant theory (1/2) slides
Lecture 4 Mon. Feb. 3 Univariate polynomials and resultant theory (2/2) slides
Lecture 5 Mon. Feb. 24 Exercises example_1.mpl example_2.mpl example_3.mpl example_4.mpl
Lecture 6 Fr. Feb. 28 Multivariate polynomials, ideals and varieties (1/2) slides example_5.mpl
Lecture 7 Mon. Mar. 2 Multivariate polynomials, ideals and varieties (2/2) slides example_5.mpl
Lecture 8 Mon. Mar. 9 Regular chain theory slides
Lecture 10 Mon. Mar. 23 Regular GCDs slides example_7.mpl example_8.mpl Bareiss.mw
Lecture 11 Mon. Mar. 30 The Intersect algorithm slides ISSAC 2011 slides
Lecture 12 Fr. Apr. 3 The Triangularize algorithm TBA

Some research papers used in the lectures are listed below

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

Computer algebra systems and related software used in this course

Quizzes and Projects

Tentative Quiz and Project Schedule

  Given Due Weight
Quiz 1 Mon. Oct. 4 3:30-4:00pm 10%
Quiz 2 Mon.Nov. 1 3:30-4:00pm 10%
Project selection Mon. Nov. 8 3:00 - 6:00pm
Quiz 3 Mon. Nov. 22 3:30-4:00pm 10%
Quiz 4 Mon. Dec. 6 2:30-3:00pm 10%
Project presentations Mon. Dec. 6 3:00 - 6:00pm 70%

Teaching Crew and Hours

  • Instructor
    Marc Moreno Maza
    email: moreno@csd.uwo.ca

    Lecture hours: 13:30-16:30pm on Mondays
    Lecture room: MC 316

    Office: Middlesex College, Room 327
    Office hours: 13:30-14:30 on Tuesdays

CS9867B, Fall 2017
Algorithmic Properties of Polynomial Rings
Course Outline

Course Description

It is a standard problem in mathematical sciences to study which properties of a given structure are preserved in derived structures. A trivial example of such preservation is the fact that every subgraph of a planar graph is itself planar. A more involved example is the fact that, if R is a unique factorization domain, then so is the ring R[x] of univariate polynomials over R. Many algorithms rely on properties that are preserved under certain transformations. For instance, if R is again a unique factorization domain, then the so-called subresultant algorithm reduces polynomial gcd computations in R[x] to gcd computations in R. In this course, we will discuss the algorithmic properties of R that can be lifted to R[x], with an emphasis on those which help solving systems of equations. In particular, we will discuss the lifting from R to R[x] of prime and primary decomposition of ideals.

The following topics will be covered during the lectures:
  • Saturated ideals, localization and direct products of rings
  • Univariate polynomials and subresultant theory
  • Multivariate polynomials and quasi-varieties
  • Zero-dimensional regular chains
  • Equiprojectable decomposition
  • Regular chain theory
  • Regular GCDs
  • The Intersect algorithm
  • The Triangularize algorithm
  • Real algebraic numbers and their representations
  • Cylindrical decompositions of semi-algebraic sets
  • Non-cylindrical decompositions of semi-algebraic sets

Instructor

Marc Moreno Maza
Email: moreno@csd.uwo.ca
Office: Middlesex College 327
Office hours: 13:30-14:30 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/CS9867 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, 13:30 - 16:30 in MC 316.

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 30% of the final grade;
  • 1 course project worth 70%;

A CS6652 project topic is chosen by the student from a list of topics proposed by the instructor. Project topics will be posted by Feb. 10. and each student must choose a project topic by Feb. 24. 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 5 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 quizzes marked and handed back within 2 weeks of the hand-in date.

Tentative Quiz and Project Schedule

  Given Due Weight
Quiz 1 Mon. Feb. 3 13:30-16:30 10%
Quiz 2 Mon. Mar. 2 13:30-16:30 10%
Project selection Mon. Feb. 24 13:30-16:30
Quiz 3 Mon. Mar. 30 3:30-4:00pm 10%
Project presentations Mon. April. 6 13:30 - 16:30 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.
  • All quizzes are close-book. A reference sheet (provided by the instructor) is allowed for the quizzes.
  • In case of questions regarding the marks, please note that no quizzes 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. The University Policy on Accommodation Consideration for Student Absences can be found here.

If you are a science student, the Academic Counselling Office of the Faculty of Science can be contacted at 519-661-3040 or scibmsac@uwo.ca. See their Their web site.

A student requiring academic accommodation due to illness must use the Student Medical certificate when visiting an off-campus medical facility.

For further information, please consult the university's medical illness policy. and the University' policy on academic accommodation for student with disabilities.

Ethical Conduct

Scholastic offences are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offence, at the following web site.

All assignments are individual assignments. You may discuss approaches to problems among yourselves. However, the actual details of the work (assignment coding, answers to concept questions, etc.) must be your individual effort. Assignments that are judged to be the result of academic dishonesty will, for the student's first offence. You are responsible for reading and respecting the Computer Science Department's policy on Rules of Ethical Conduct and Scholastic Offenses.

All required papers may be subject to submission for textual similarity review to the commercial plagiarism detection software under license to the University for the detection of plagiarism. All papers submitted for such checking will be included as source documents in the reference database for the purpose of detecting plagiarism of papers subsequently submitted to the system. Use of the service is subject to the licensing agreement, currently between The University of Western Ontario and Turnitin.com.

Computer-marked multiple-choice tests and/or exams may be subject to submission for similarity review by software that will check for unusual coincidences in answer patterns that may indicate cheating.

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.

Mental Health

All students who are in emotional/mental distress should refer to Mental Health@Western. for a complete list of options about how to obtain help.

Support Services

Learning-skills counsellors at the Student Development Centre. 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. See also the services provided by the University Students’ Council.

The website for Registrarial Services.