# Computer Algebra

## Announcements

There will be no tutorial session tomorrow, January 4th.

Chapters 1-3 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.30-10.00 am in Room 24, Building E14

Since the Semester-kick-off Meeting will be held 4:30pm on 16 October, 2017,  our first lecture will start on 18 October, 2017.

## Basic Information

Lecturer: Michael Sagraloff Monday and Wednesday 12-14 (c.t.), Room 24 in E1 4 Anurag Pandey Thursday 08:30 am - 10:00 am, Room 24 in E1 4 (first tutorial is on November 2nd) Analysis I and Linear Algebra I or Mathematics for Computer Scientists I and IIBasic 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.

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

## 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. 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 Toom-Cook Multiplication 25.10.2017 Fixed-Point 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önhage-Strassen 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), Square-Free 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, Marie-Françoise Roy: Algorithms in Real Algebraic Geometry. Springer, 2003, ISBN 3-540-00973-6.