CS 573 / CA: Core Lecture
Computer Algebra – Winter Term 2014/2015
News:
Lectures
| 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 |
|
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.
- 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.
Basics and Dates:
- 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
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.
Exercises:
- 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.
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.
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.
