Computer Algebra
Core Course, 4+2
Announcements
There will be no tutorial session tomorrow, January 4th.
Chapters 13 of the lecture notes are now online.
Today, December 18, the lecture will take place in Room 22 (MPII).
The typos in Exercise 1 in Exercise Sheet 4 is fixed now.
Exercise 4 in Exercise Sheet 4 is fixed now.
Chapter 1 of the lecture notes is now online.
We fixed a room for the tutorials. They will take place every Thursday (starting November 2nd) at 8.3010.00 am in Room 24, Building E14
Since the Semesterkickoff Meeting will be held 4:30pm on 16 October, 2017, our first lecture will start on 18 October, 2017.
Basic Information
Lecturer:  

Lectures:  Monday and Wednesday 1214 (c.t.), Room 24 in E1 4 
Tutor:  Anurag Pandey 
Tutorials:  Thursday 08:30 am  10:00 am, Room 24 in E1 4 (first tutorial is on November 2nd) 
Prerequisites: 

Description
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.
 numbers and arithmetics: school method vs. faster methods for multiplication, floating point arithmetic, interval arithmetic
 polynomial arithmetics: division with remainder, fast multipoint evaluation, (asymptotically fast) Euclidean algorithm, greatest common divisor, factorization, comparison and representation of algebraic numbers.
 polynomial root finding: Sturm sequences, Descartes algorithm, NewtonRaphson method, complex root finding.
 modular arithmetic and modular algorithms: evaluation, interpolation, Chinese Remainder Algorithm, prime number tests.
 discrete and Fast Fourier transformation: fast multiplication of polynomials, fast Taylor shift.
 elimination theory and polynomial system solving: polynomials ideal, resultants and subresultant sequences, multivariate division with remainder, Gröbner bases, Cylindrical Algebraic Decomposition.
 geometric algorithms: topology of algebraic curves and surfaces, arrangement computation.
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 twohour lectures and a twohour tutorial session per week.
Grading:
The grade is determined by the final exam. We will have an oral exam within the first two weeks of February.
Exercises:
 There will be an assignment sheet every week, which will be posted on Monday. You have to hand in you solutions one week later before the lecture on Monday.
 Solutions can be handed in as a group of at most 2 students
 We expect you to regularly attend and participate in the tutorial sessions.
Lectures
Date  Topic  Reference 
18.10.2017  Introduction and Overview, School method and Karatsuba's method for integer multiplication  
23.10.2017  ToomCook Multiplication  
25.10.2017  FixedPoint Arithmetic and Interval Arithmetic  
30.10.2017  Box functions, Floating Point Arithmetic, Fast Division  Chapter 1: Basic Arithmetic 
06.11.2017  Fast Fourier Transform: Overview of the SchönhageStrassen method for integer multiplication and Definition of Convolution, Primitive Roots of Unity, DFT  
08.11.2017  DFT and FFT, Fast Convolution  
13.11.2017  Schönhage Strassen method for the multiplication of integers and integer polynomials, Kronecker Substitution  
15.11.2017  Fast Multiplication over arbitrary Rings, Fast Polynomial Division  
17.11.2017  Fast Multipoint Evaluation and Applications  
20.11.2017  Fast Multipoint Evaluation and Applications ctd., Fast Polynomial Arithmetic over C  
22.11.2017  Fast Polynomial Arithmetic over C ctd., Integral Domains, Ideals  Chapter 2: The Fast Fourier Transform and Fast Polynomial Arithmetic 
27.11.2017  Noether Rings, Hilbert's Basis Theorem  
29.11.2017  Factorial Rings, Gauss' Lemma  
04.12.2017  Extended Euclidean Algorithm (Analysis and Definition), SquareFree Factorization  
06.12.2017  Resultants (Definition and Properties)  
11.12.2017  Mahler Measure, Root Separation Bounds  
13.12.2017  Subresultants  
18.12.2017  Subresultants ctd., Structure Theorem for Subresultants  Chapter 3: The Extended Euclidean Algorithm and (Sub) Resultants 
20.12.2017  Modular Computation, Prime Number Theorem, AKS Primality Test 
Exercises
Exercise Sheet  Due Date 
Exercise Sheet 1  October 30 
Exercise Sheet 2  November 6 
Exercise Sheet 3  November 13 
Exercise Sheet 4  November 20 
Exercise Sheet 5  November 27 
Exercise Sheet 6  December 4 
Exercise Sheet 7  December 11 
Exercise Sheet 8  December 18 
Exercise Sheet 9  January 8 
Exercise Sheet 10  January 15 
Exercise Sheet 11  January 22 
Exercise Sheet 12  January 29 
Literature
 Jürgen Gerhard and Joachim von zur Gathen: Modern Computer Algebra. Cambridge University Press, third edition, 2013, ISBN 9781107039032.
Available in the Campus library of Computer Science and Mathematics.  Saugata Basu, Richard Pollack, MarieFrançoise Roy: Algorithms in Real Algebraic Geometry. Springer, 2003, ISBN 3540009736.
Available for download here.  Yap, Chee: Fundamental Problems in Algorithmic Algebra. Oxford University Press, 2000, ISBN 0195125169.
Preliminary version available for download here.  Richard P. Brent and Paul Zimmermann: Modern Computer Arithmetic. Cambridge University Press, 2010, ISBN 0521194695.
Preliminary version available for download here.  Wolfram Koepf: Computeralgebra – Eine algorithmisch orientierte Einführung. Springer Verlag, 2006, ISBN 3540298940. In German.
Available for download for students of the University of Saarland via SpringerLink.  Hal Schenck: Computational Algebraic Geometry. Cambridge University Press, 2003, ISBN 9780521829649.