Computer Algebra 1000-2M26CAL

1. Foundations: integer and polynomial arithmetic, Extended Euclidean Algorithm, complexity basics.
2. Exact Linear Algebra: Gaussian elimination, Strassen's algorithm for fast matrix multiplication.
3. Fast polynomial arithmetic: polynomial multiplication, evaluation and interpolation, Discrete Fourier Transform and Fast Fourier Transform (FFT).
4. Polynomial factorization over finite fields: algorithms of Berlekamp and Cantor-Zassenhaus.
5. Polynomial factorization over rational numbers: Hensel lifting, lattice reduction and the Lenstra-Lenstra-Lovász (LLL) algorithm.
6. Gröbner Bases: polynomial ideals, Buchberger's algorithm, variable elimination and solving polynomial systems.

Mode

Classroom

Prerequisites

Geometry with linear algebra
Linear algebra and geometry I

Prerequisites (description)

Some familiarity with algebraic structures (rings and fields) would be useful. Having followed Algebra I or an equivalent course would be helpful but is not a requirement.

Learning outcomes

Knowledge.

- The student is familiar with the mathematical background of modern computer algebra systems, as well as how algebraic objects (polynomials, matrices, rings and fields) are represented and efficiently computed.
- The student understands the fundamental algorithms for exact linear algebra, polynomial arithmetic, polynomial factorization, and Gröbner Bases.
- The student is able to prove correctness and analyse the complexity of these algorithms.

Skills.

- The student can apply the algorithms in the course to computational problems in a range of areas, including coding and optimisation.
- The student can use the techniques of the course to design and analyse efficient algorithms in computational algebra.

Assessment criteria

The evaluation is based on an extended homework and a final oral exam. For PhD students, evaluation is instead based on a research mini-project and an oral examination on the project.

Additional information

Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes: