 Teaching plan for the course unit

 Close  General information

Course unit name: Computational Algebra

Course unit code: 568186

Coordinator: Luis Victor Dieulefait

Department: Department of Mathematics and Computer Science

Credits: 6

Single program: S Estimated learning time Total number of hours 150

 Face-to-face learning activities 60
 -  Lecture 30 -  Problem-solving class 15 -  Laboratory session 15
 Supervised project (Resolution of exercices and preparation of the students’presentation, or preparation for the final exam.) 20
 Independent learning (Study of class material and completion of proofs of statements delivered during the magistral classes.) 70

 Recommendations

 This course requires knowledge of linear algebra. It is also recommended that students have some knowledge of calculus, commutative algebra and algebraic geometry, and are familiar with some programming language.

 Competences to be gained during study

 — Ability to work with fundamental algorithms for polynomials and integers.  — Capacity to work in basic computational algebraic geometry.

 Learning objectives
 Referring to knowledge — To understand the fundamental algorithms for polynomials and integers, and the basic problems of computational algebraic geometry.  Referring to abilities, skills — To acquire the knowledge and ability to solve theoretical problems and implement algorithms. — To be Introduced to mathematical research in this area.

 Teaching blocks

1. Basic Algorithms

1.1. Complexity. Recursive algorithms vs iterative algorithms

1.2. Fast multiplication of polynomials and integer numbers: Karatsuba’s algorithm, Discrete Fourier Transform, Fast Fourier Transform and Schönhage-Strassen algorithm

1.3. Newton iteration: division with remainder using Newton iteration. Computation of integer roots of a polynomial.

1.4. Fast multipoint evaluation and interpolation of polynomials

1.5. Fast Linear Algebra: multiplication and inversion of matrices. Fast Euclidean algorithm

2. Factorization

2.1. Factorization of polynomials over finite fields: Cantor-Zassenhaus algorithm

2.2. Hensel’s Lemma and factorization of polynomials. Zassenhaus algorithm.

2.3. Short vectors in lattices: Lenstra-Lenstra-Lovasz algorithm, factorization in Q[x]

3. Systems of polynomial equations

3.1. Real roots of a polynomial: Descartes rule of signs, Budan-Fourier and Sturm theorems, Hermite theorem

3.2. Gröbner basis: Monomial orders and division with remainder for multivariate polynomials, S-polynomials and Gröbner bases, the Buchberger algorithm

3.3. Applications: Resolution of systems of polynomial equations, computation of real roots, symbolic integration

 Teaching methods and general organization

 The teaching methodology  consists of: — Two hours of magistral classes per week — One hour of problem-solving classes per week — One hour of computer laboratory per week — Supervised personal work on problem solving and preparation of the student presentation — Independent learningDuring the magistral classes, the instructor will explain the definitions and main results of the syllabus, which will be illustrated with examples. Some statements will be left for the students to complete their proofs. Lists of exercises will be delivered so that students can solve and present them to the rest of the class; There will also be computer lab sessions to be prepared by the students, and exercises to be solved with the aid of a software in Computational Algebra.The final evaluation of the course will be done either with a midterm and a final exam, or -if the size of the class allows it and the performance of the students during the semester is reasonable- by the end of the term each student will be offered one topic to work upon, related to the course content. The student should work around this topic, solve some exercises, understand some results and implement codes which will be presented to the rest of the class for the final evaluation.

 Official assessment of learning outcomes

 Participation in magistral classes, problem sessions and computer labs, and scheduled delivery of exercises  and assignments given during the the magistral classes  will be up to 50% of the final grade for the course.   The remaining grade will be given by the final evaluation.     Examination-based assessment   Students not following the continuous evaluation explained above must sit for a final exam which consists of problem-solving exercises and theory questions at the end of the semester. Reevaluationt   Students who have failed the class (in the continuous or unique evaluation) may apply for Reevaluation, which will consist of an exam of problems and theory in the date scheduled by the Coordinator of the Master.   Also, those willing to improve their grade may apply for Reevaluation. In order to be eligible for this step, students must have a minimum grade of 3 in either the continuous or single evaluation. Applying for Reevaluation implies giving up to the initial grade obtained during the course (i.e., the final grade will be the one obtained in the Reevaluation exam).