Computer Algebra
Core Course, 4+2
Basic Information
Lecturer:  

Lectures:  Monday and Wednesday 1214 (c.t.), Room 24 in E1 4 
Tutor:  tba 
Tutorials:  will be fixed within the first week of the lecture 
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.
Exercises:
 There will be an assignment sheet every week. We will discuss the exact rules for handing in exercises with the participants within the first week of the lecture – expect something similar to other theoretical computer science or math lectures.
 We expect you to regularly attend and participate in the tutorial sessions.
Lectures
Date  Topic  Reference  Homework 

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.