You are probably familiar with Maple or another computer algebra system, which can instantly compute the 70.000 digits of 987 to the 10.00th power; or the determinant of a 1000 x 1000 integer matrix; or the set of exact solutions to 21 non-linear equations in as many variables.

You may think that these incredible feats are due to the blazing speeds of today's computers. You would be wrong. While computation power has increased exponentially fast, our knowledge of better algorithms for computing these things has grown even faster. Without these algorithmic improvements, even the fastest computers today would barely be solving beyond toy problems.

Computer Algebra is the search for faster algorithms for solving exact algebraic questions. This is in contrast to Numerical Algorithms, where approximate solutions are sought. Most of the natural problems are inherently discrete: our arena is integers, fractions, finite fields and polynomials.

In this course we discuss some of the most important breakthroughs in Computer Algebra, and how these are used for fast computation and manipulation of the objects you take for granted that Maple can solve for you. We take a mathematically stringent approach with formal proofs mixed with high-level experimentation and implementation in Python/SageMath. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Efficiently compute with finite fields
• Describe a fast multiplication algorithm and applications for other computations.
• Describe fast multiplication of square matrices and applications for other computations.
• Efficiently compute the determinant of a large integer matrix.
• 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 solve algebraic problems.
• Implement algorithms for solving algebraic problems in Python using SageMath.
• Determine the asymptotic complexity of algorithm for algebraic problems, in particular with concern to coefficient swell over infinite rings and fields.
• Prove the correctness of algebraic algorithms.

Exact symbolic/algebraic computation. Finite fields, polynomials over finite fields and over integers, matrices over finite fields and over integers, multivariate polynomials and their ideals. Algorithms with basic arithmetic for all of the above. Gröbner bases and Buchberger's algorithm. SageMath and Python, and computer algebra systems in general. J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed. Kurset har fået ny kursusansvarlig for E19 og har gennemgået signifikante ændringer siden tidligere år. Bemærk i særdeleshed ny eksamensform. 26. april, 2019