Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

CS 573 / CA: Core Lecture
Computer Algebra – Summer Term 2011

News:

Lectures

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 Square-free 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); square-free 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)
Akra-Bazzi-Theorem: NewMasterTheorem.pdf (Mehlhorn)
Leighton: Notes on Better Master Theorems for Divide-and-Conquer Recurrences
Ex01.pdf
Apr 12 Overview, Integer arithmetic Mehlhorn, Sanders: Algorithms and Data Structures, Chapter 1

Please use our LaTeX template for sample solutions.

Overview:

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.

Basics and Dates:

Prerequisites:

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.

Grading:

The grade is determined by the final exam.
The final exam will be at July 29th, 10.00-13.00 We will announce the room soon.

Exercises:

Literature: