max planck institut

informatik

informatik

Computer Algebra – Winter Term 2014/2015

- Office Hours: 10:00 am - 12:00 pm in my office room 306, E1 4 (Max-Planck-Institute for Informatics).
- Tutorials take place Thursday 08:30 am to 10 am in room 024, E1 4 (Max-Planck-Institute for Informatics). The first tutorial is on Thursday, November 6.
- First lecture is on Wednesday, October 22nd.

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.

**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, Newton-Raphson 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.

**Time:**Monday, 14 – 16 and Wednesday, 10 – 12 c.t.**Room:**Campus E1 3, lecture hall 001**Lecturer:**Michael Sagraloff**First lecture:**Wednesday, October 22nd (Campus E1 3, lecture hall 001)**No lectures:**Monday, December 22nd through Wednesday, December 31st**Last lecture:**Wednesday, February 11th

**Tutorial:**Thursday, 8:30 – 10:00**Room:**Campus E1 4, room 024 (Max-Planck-Institute for Informatics)**First tutorial:**Thursday, November 6

- Analysis I and Linear Algebra I
*or*Mathematics for Computer Scientists I and II - Basic knowledge in Number Theory and Algebra is useful, but not required.
- Programming experience in Maple (or another computer algebra system) is useful, but not required.

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.

- 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.

- 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, Marie-Françoise Roy:
*Algorithms in Real Algebraic Geometry*. Springer, 2003, ISBN 3-540-00973-6.

Available for download here. - Yap, Chee:
*Fundamental Problems in Algorithmic Algebra*. Oxford University Press, 2000, ISBN 0-195-12516-9.

Preliminary version available for download here. - Richard P. Brent and Paul Zimmermann:
*Modern Computer Arithmetic*. Cambridge University Press, 2010, ISBN 0-521-19469-5.

Preliminary version available for download here. - Wolfram Koepf:
*Computeralgebra – Eine algorithmisch orientierte Einführung*. Springer Verlag, 2006, ISBN 3-540-29894-0. 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.