Date  Topic  Reference  Homework 

July 21  no lecture  
July 19  Applications of Gröbner bases (cont'd); recap of the lecture 
Decker, Schreyer: Varieties, Gröbner Bases, and Algebraic Curves, Sections 2.3 to 2.4  
July 14  Applications of Gröbner bases  
July 12  Buchberger's algorithm; Reduced Gröbner bases  Gerhard, von zur Gathen: Modern Computer Algebra, Chapter 21 Decker, Schreyer: Varieties, Gröbner Bases, and Algebraic Curves, Sections 2.1 to 2.4 
Ex13.pdf 
July 7  Gröbner bases & Buchberger's algorithm  
July 5  Ideal operations; Primary decomposition  Decker, Schreyer: Varieties, Gröbner Bases, and Algebraic Curves, Sections 1.3, 1.7 and 1.8  Ex12.pdf 
June 30  Fast Taylor shift, fast integer division; Algebraic varieties  Gerhard, von zur Gathen: Modern Computer Algebra, Chapter 9 Gerhard, von zur Gathen: Fast algorithms for Taylor shifts and certain difference equations Decker, Schreyer: Varieties, Gröbner Bases, and Algebraic Curves, Sections 1.1 to 1.6 

June 28  Fast multiplication of integer polynomials and integers  Gerhard, von zur Gathen: Modern Computer Algebra, Sections 8.2 and 8.3  Ex11.pdf 
June 21  Fast algorithms: Discrete Fourier transform for polynomial multiplication (cont'd)  Ex10.pdf  
June 16  Fast algorithms: Discrete Fourier transform for polynomial multiplication  
June 14  Modular algorithms (cont'd), Chinese remaindering; Bitstream Descartes root isolator  Gerhard, von zur Gathen: Modern Computer Algebra, Sections 5.1 to 5.5 and 6.4 to 6.7 Mehlhorn, Sagraloff: A Deterministic Descartes Algorithm for Real Polynomials Eigenwillig: Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs, Chapter 2 
no exercise sheet today 
June 9  Descartes method for root solving  Eigenwillig: Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs, Sections 2.1 and 2.2 Kerber: Geometric Algorithms for Algebraic Curves and Surfaces, Section 2.4.4 Basu, Pollack, Roy: Algorithms in Real Algebraic Geometry, Section 10.2 

June 7  Descartes' Rule of Signs  Ex09.pdf  
May 31  Modular algorithms  Gerhard, von zur Gathen: Modern Computer Algebra, Section 5.1 to 5.4  Ex08.pdf 
May 26  Algebraic plane curve analysis (cont'd); modular arithmetic  Berberich, Emeliyanenko, Kobel, Sagraloff: Arrangement Computation for Planar Algebraic Curves Kerber: Geometric Algorithms for Algebraic Curves and Surfaces, Sections 2.2 and 3.2 

May 24  Algebraic plane curve analysis  Ex07.pdf  
May 19  Bivariate system solving (cont'd)  Berberich, Emeliyanenko, Sagraloff: An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks  
May 17  Bivariate system solving  Ex06.pdf  
May 12  Subresultant sequences and the Extended Euclidean Algorithm  Gerhard, von zur Gathen: Modern Computer Algebra, Sections 6.3 and 6.10 Kerber: Geometric Algorithms for Algebraic Curves and Surfaces, Section 2.3 

May 10  Properties of subresultants, subresultant sequences  Ex05.pdf  
May 05  Properties of resultants, subresultants  
May 03  Squarefree decomposition: Yun's algorithm; resultants  Gerhard, von zur Gathen: Modern Computer Algebra, Sections 14.6 and 6.3 Koepf: Computeralgebra, Chapter 7 (in German) Kerber: Geometric Algorithms for Algebraic Curves and Surfaces, Section 2.3 
Ex04.pdf 
Apr 28  Extended Euclidean algorithm (cont'd); squarefree factorization  Gerhard, von zur Gathen: Modern Computer Algebra, Chapter 3 and Sections 6.1 and 6.2 Koepf: Computeralgebra, Chapter 3 (in German) 

Apr 26  Principle ideal rings; Extended Euclidean algorithm  Gerhard, von zur Gathen: Modern Computer Algebra, Chapter 3 Koepf: Computeralgebra, Chapter 3 (in German) 
Ex03.pdf 
Apr 21  Unique factorization domains, Hilbert's Basis Theorem  Bosch: Algebra, Section 3.9 (in German)  
Apr 19  Interval arithmetic, box functions, EVAL; Unique factorization of integers  Sommese, Wampler: The Numerical Solution of Systems of Polynomials, Chapter 6 ceval.pdf (Sagraloff, Yap) 
Ex02.pdf 
Apr 14  Floating and fixed point arithmetic  numbers.pdf (Mehlhorn), cp.pdf (Mehlhorn, Sagraloff) AkraBazziTheorem: NewMasterTheorem.pdf (Mehlhorn) Leighton: Notes on Better Master Theorems for DivideandConquer Recurrences 
Ex01.pdf 
Apr 12  Overview, Integer arithmetic  Mehlhorn, Sanders: Algorithms and Data Structures, Chapter 1 
Please use our LaTeX template for sample solutions.
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.
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.
The grade is determined by the final exam.
The final exam will be at July 29th, 10.0013.00 We will announce the room soon.