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

News:

Thank you all for participating in the lecture!
We hope you enjoyed it, and look forward to see you again. Feel free to contact us for bachelor and master thesis' topics, PhD positions, interesting work and research projects, upcoming lectures, ...
Sample solutions are removed, to not spoil upcoming lectures.
Old 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.

integer arithmetics: representation, school method vs. faster methods for multiplication, floating point arithmetic, interval arithmetic, optionally: prime number tests, factorization
polynomial arithmetics: basic properties, division with remainder, Euclidean algorithm, greatest common divisor, factorization, comparison and representation of algebraic numbers.
polynomial root finding: Sturm sequences, Descartes algorithm, polynomials with Bitstream coefficients, complex root finding, optionally: numerical methods and certification.
modular arithmetic and modular algorithms: evaluation, interpolation, Chinese Remainder Algorithm.
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.

Basics and Dates:

Time: Tuesday, 10 – 12 and Thursday, 10 – 12 c.t.
Room: Campus E1 3, lecture hall 003
Lecturers and office hours: Michael Sagraloff (Tuesday 15 – 16)
First lecture: Tuesday, April 12th (Campus E1 3, lecture hall 003)
No lectures: Thursday, June 2nd (Ascension Day); Thursday, June 23th (Corpus Christi)
Last lecture: July 21th, 2011

Tutor: Alexander Kobel
Tutorial(s): Wednesday, 8.30 – 10, Campus E1 4 (MPII), lecture hall 024
First tutorial: Wednesday, April 20th

Prerequisites:

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.

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:

There will be theoretical and practical (i.e., programming) exercises, to be handed in before the Tuesday lecture in the lecture hall.
You need to participate in all tutorials and obtain at least 50% of the total exercise scores.
Every student has to present the solution to two assignments (typically about 3 per sheet) in the tutorial sessions.
Every student has to prepare "LaTeX'ed" (sources and pdf) sample solutions to one assignment sheet. Sample solutions are due one week after discussing them in the tutorial. Submitted sample solutions will be checked, and we may ask for improvements.
Download and use our LaTeX template for the sample solutions.

Literature:

Jürgen Gerhard and Joachim von zur Gathen: Modern Computer Algebra. Cambridge University Press, second edition, 2003, ISBN 0-521-82646-2.
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.

CS 573 / CA: Core LectureComputer Algebra – Summer Term 2011