Michael Monagan, Simon Fraser University (3 lectures, 6 hours)
Lecture 1 : Euclidean domains. The Euclidean algorithm. The polynomial ring R[x], division in F[x].
Video Lec5Anotes.pdf Lec5Bnotes.pdf Lec5Handouts.zipLecture 2 : Cost of division and the Euclidean algorithm in F[x], solving diophantine equations in F[x].
Multivariate polynomials, exact division in D[x1,..., xn].
Video Lec6Anotes.pdf Lec6Bnotes.pdf Lec6Handouts.zipLecture 3 : Multivariate gcds: primitive polynomials, pseudo division. The primitive Euclidean algorithm, expression swell.
Video Lec7Anotes.pdf Lec7Bnotes.pdf Lec7Cdemo.pdf Lec7Handouts.zip
The following two lectures (4 hours) were given subsequently in Topics in Computer Algebra. The focus is on multiplication and division of sparse polynomials in a monomial ordering where terms need to be sorted, either by repeated merging or using a heap. For example, to multiply two polynomials f and g with n terms and m terms, respectively, naive repeated merging does O(n2 m) monomial comparisons. Using a heap reduces this to O(n m min(log n, log m)) monomial comparisons.
Lecture 4A : Polynomial addition and division using merging. Monomial orderings. Video
Lecture 4B : Polynomial multiplication using repeated merging and divide and conqer. Video
Multivariate polynomial data structures in Maple, Singular, Pari and Trip. Slides
Lecture 5A : Binary heaps. Insertion and extraction algorithms. Video
Lecture 5B : Johnson's polynomial multiplication and division using a heap. Video