CS424b/CS556b -- Foundations of Computational Algebra

Course Description

Symbolic computations manipulate numbers by using their mathematical definitions rather than using floating point approximations. Consequently, their results are exact, complete and can be made canonical. However, they can be huge! Moreover, intermediate expressions may be much bigger than the input and output. One of the main successes of the Computer Algebra community in the last 30 years is the discovery of algorithms, called modular methods, that allow to keep the swell of the intermediate expressions under control. Even better: these methods fit almost each of the intermediate values in a machine word. Without these methods, many applications of Computer Algebra would not be possible and the impact of Computer Algebra in the scientific community would be severely reduced. Today, modular computations are well-developed, especially for univariate and bivariate polynomial arithmetic and for linear algebra. They form the foundation for all modern algorithms in Computer Algebra. This will be the main topic of this course. In particular, we will discuss

• Fast multiplication algorithms (FFT, Karatsuba, Strassen)
• Chinese remaindering algorithm
• Newton's iteration and Hensel lifting
• Fast Linear Algebra and the LLL algorithm
• Polynomial gcds and resultants
• Factorization of Univariate Polynomials

Prerequisites

• Math223 (Discrete Structures II)
• OR permission from the instructor

Familiarity with a variety of programming languages is a bonus, although not required.

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 is Postscript and HTML.

There is only one (highly) recommended text for the course. The other references are given for the curious reader.

• Modern Computer Algebra J. von zur Gathen and J. Gerhard (RECOMMENDED). Cambridge University Press, 1999.
• Algorithms for Computer Algebra. K.O. Geddes and S.R. Czapor and G. Labahn (SUPPLEMENTARY). Kluver Acadenic Publishers, 1992.

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

The list of topics will be something on the order of:

1. Introduction to computer algebra and computer algebra systems
2. Fast multiplication algorithms (FFT, Karatsuba, Strassen)
3. Euclidean methods (Chinese remaindering algorithm, rational reconstruction, ...)
4. Newton's iteration and Hensel lifting
5. Fast linear algebra and the LLL algorithm
6. Polynomial gcds and resultants
7. Factorization of Univariate Polynomials

Class Schedule

Lectures: 3 hours (Tuesday from 3:30 to 4:30pm and Thursday from 3:30 to 5:30pm in MC320). In general, a lecture consists of a talk by the instructor followed by an exercise session.

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

Student Evaluation

• The course is very oriented toward assignments and projects.
• Assignments and projects constitute 40% and 40% of the course mark, respectively.
• Assignments consist of theoretical exercises. Projects can be theoretical work (research article presentations, research work), practical (programming, experimentation and analysis) or combination of both.
• There is no midterm examination and no final examination.
• However, there will be at least four quizzes given, but only your best three will count toward your mark.
• Quizzes constitute 20% of the course mark.
• A quiz is a series of short and simple exercises similar to the examples of the course notes, whereas assignments consist of more advanced exercises.
• In order to successfully complete the course, a student must achieve at least 50% on assignments, 50% on projects and 50% on quizzes. This is to prevent a serious lack of effort in either area. Thus, a student cannot get 100% on assignments and projects and barely pass the quizzes.

Assignment/Project/Quiz Schedule

All dates are tentative and currently subject to change, although it is doubtful by any significant amount.

If for any reason the schedule given above cannot be adhered to, the assignment, project and quiz marks will be pro-rated. For instance, if an assignment has to be canceled for any reason, the remaining assignment weight will be prorated to add up to 30%.)

Every effort will be made to have assignments, projects and quizzes marked and handed back within 3 weeks of the hand-in date, preferably sooner.

Quizzes

Quizzes may be held without being announced in advance.

Quizzes will be closed book.

Assignments

Assignments will be due on the (tentative) dates listed above. The assignment can be sent by email to the instructor or given to the instructor during the class or office hours.

Extensions will be granted only by the course instructor. If you have serious medical or compassionate grounds for an extension, you should take supporting documentation to the office of the Dean of your faculty, who will contact the instructor.

Projects

Projects will be presented by the students during the class on the (tentative) dates listed above.

It is expected that presentation session may last longer than a usual class.

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

Note: After-hours access to certain Computer Science lab rooms is by student card. If a student card is lost, a replacement card will no longer open these lab rooms, and the student must bring the new card to a member of the Systems Group in Middlesex College Room 346.

Email Contact

The instructor will occasionally need to send email messages to the whole class, or to students individually. Email will be sent to your GAUL email address. You must make sure that you read your email on GAUL on a frequent and regular basis, or have it forwarded to an alternative email address if you prefer to read it there.

However, you should note that email at ITS (your UWO account) and other email providers such as hotmail.com or yahoo.com may have quotas or limits on the amount of space they can use. If you let your email accumulate there, your mailbox may fill up and you may lose important email from the instructor. Losing email that you have forwarded to an alternative email address is not an excuse for not knowing about the information that was sent.

Students can ask questions via email, however if there are any large, somewhat complicated issues, it is recommended to discuss them during office hours. Moreover, you MUST use your UWO account or your GAUL account in order to write to the instructor. Emails from non-academic accounts will be automatically ignored.

Ethical Conduct

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 an individual effort. Assignments that are judged to be the result of academic dishonesty will, for the student's first offense, be given a mark of zero with an additional penalty equal to the weight of the assignment also being applied. You are responsible for reading and respecting the Computer Science Department's policy on Scholastic Offenses and Rules of Ethical Conduct.

Students must write their essays and assignments in their own words. Whenever students take an idea, or a passage from another author, they must acknowledge their debt both by using quotation marks where appropriate and by proper referencing such as footnotes or citations. Plagiarism is a major academic offense (see Scholastic Offense Policy in the Western Academic Calendar).

The University of Western Ontario uses software for plagiarism checking. Students may be required to submit their written work and programs in electronic form for plagiarism checking.