Single-Course English 5 ECTS

# Computational Discrete Mathematics

## Overall Course Objectives

This is a course about ingenious methods for solving algebraic questions, such as factoring polynomials over a finite field, or finding simultaneous roots to several multivariate polynomials. We are in a discrete and exact arena: integers, fractions, finite fields and polynomials, and our main concern will be to study algorithms that are fast for very large input.

If you like discrete mathematics, you will like this course because we will dig deep into beautiful and surprising algebraic properties that can be turned into concrete recipes for solving problems. Abstract algebra will become concrete and hands-on by understanding how to actually solve algebraic questions.

We will take a mathematically stringent approach with proofs of algebraic theorems, algorithms’ correctness and their complexity. We will mix this with experimentation with a computer-algebra program.

Learning Objectives

• Explain how to explicitly represent and compute with very large integers, finite fields, and with polynomials over finite fields.
• Describe a fast multiplication algorithm and applications for other computations.
• Apply modular methods and chinese remaindering to algebraic computations.
• Efficiently factor a polynomial over a finite field.
• Perform multivariate polynomial division with remainder and describe the role of monomial orders.
• Compute a Gröbner basis and describe its relevance for ideal membership and related problems.
• Represent real-world problems as non-linear equations and the relation to ideals of multivariate polynomial rings.
• Use a computer algebra system to experimentally work with algebraic problems.
• Determine the asymptotic complexity of algorithm for algebraic problems in a realistic computational model.
• Prove the correctness of algebraic algorithms.

Course Content

Exact algebraic computation. Arithmetic in finite fields, with polynomials over finite fields and over integers, and with matrices over finite fields and over integers. Algorithms for factoring. Ideals in Noetherian rings, especially multivariate polynomial rings, Gröbner bases and Buchberger’s algorithm.

Recommended prerequisites

01018, Understanding of concepts from abstract algebra: linear algebra, rings, ideals, quotient rings, the isomorphism theorem, finite fields. Some experience with programming and algorithms.
Students that have not taken 01018 but have 01017 and 01426 should be able to follow the course but should expect reading up on the mentioned algebra.

Teaching Method

Lectures, exercises, assignments

Faculty

Limited number of seats

Minimum: 5.

Please be aware that this course will only be held if the required minimum number of participants is met. You will be informed 8 days before the start of the course, whether the course will be held.

See course in the course database.

## Registration

Language English 13 weeks Compute DTU Lyngby Campus 01415 Candidate Week 35 Week 48 Wed 13-17
Price 7.500,00 DKK