max planck institut
mpii logo Minerva of the Max Planck Society

CS 573 / CA: Core Lecture
Computer Algebra – Winter Term 2014/2015



Date Topic Reference Homework
Jan 21 Polynomial root solving (cont'd) ca14ex11.pdf
Jan 19 Polynomial root solving
Jan 14 Modular algorithms (cont'd) ca14ex10.pdf
Jan 12 Modular algorithms
Jan 07 Chinese remaindering ca14ex09.pdf
Jan 05 AKS primality test (cont'd)
Dec 17 AKS primality test ca14ex08.pdf
Dec 15 Half-GCD
Dec 10 Subresultants (cont'd) ca14ex07.pdf
Dec 08 Subresultants (cont'd)
Dec 03 Resultants and subresultants ca14ex06.pdf
Dec 01 Extended Euclidean Algorithm (cont'd); Yun's algorithm; Resultants
Nov 26 Extended Euclidean Algorithm ca14ex05.pdf
Nov 24 Ring theory; Gauss' Lemma
Nov 19 Fast polynomial interpolation; fast Taylor shift ca14ex04.pdf
Nov 17 Fast polynomial multipoint evaluation
Nov 12 Fast polynomial division ca14ex03.pdf
Nov 10 Schönhage-Strassen multiplication
Nov 05 FFT multiplication (cont'd) ca14ex02.pdf
Nov 03 DFT (cont'd); FFT multiplication
Oct 29 Interval arithmetic, box functions; Discrete Fourier Transform Kerber, Sagraloff: Root Refinement for Real Polynomials using Quadratic Interval Refinement, pages 11-13 ca14ex01.pdf
Oct 27 Toom-Cook multiplication; approximate arithmetic
Oct 22 Integer arithmetic; multiplication methods: School method, Karatsuba, Toom-Cook Mehlhorn, Sanders: Algorithms and Data Structures, Chapter 1


We will provide an introduction into the most fundamental and ubiquitous algorithms in computer algebra. We further focus on topics related to geometric computing with (real) algebraic curves and surfaces.

Basics and Dates:


Information and Rules:

This is a theoretical core course for computer science students and an applied mathematics core course for mathematics students.
Successful completion (that is, solving the expected 50 % of the weekly exercises and passing the exam) is worth 9 ECTS credit points. Expect to be imposed a total workload of about 270 hours, distributed to 90 hours of attended lectures and 180 hours of private study.

This course is intended for graduate students and/or senior undergraduate students. It consists of two two-hour lectures and a two-hour tutorial session per week.


The grade is determined by the final exam.