Teaching plan for the course unit

 

 
Close imatge de maquetació

 

Print

 

General information

 

Course unit name: Computational Algebra

Course unit code: 568186

Academic year: 2021-2022

Coordinator: Luis Victor Dieulefait

Department: Department of Mathematics and Computer Science

Credits: 6

Single program: S

More information enllaç

 

 

Estimated learning time

Total number of hours 150

 

Face-to-face and/or online activities

60
 

-  Lecture

Face-to-face

  

30
 

(face to face or remotely)
 

-  Problem-solving class

Face-to-face

  

15
 

(face to face or remotely)
 

-  Laboratory session

Face-to-face

  

15
 

(face to face or remotely)

Supervised project

20

(Resolution of exercices and preparation of the students’presentation, or preparation for the final exam.)

Independent learning

70

(Study of class material and completion of proofs of statements delivered during the magistral classes.)

 

 

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 learning

During 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.

If special circumstances forces us to do so, part of the classes will be remote, via UB’s Campus Virtual. Exercises and computer lab sessions may also be delivered online through the Campus Virtual if special circumstances occur.

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.

Both the delivery of exercises and the final evaluation may take place remotely via UB’s Campus Virtual if special circumstances prevent us to do it face-to-face.

 

 

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).

The final exam and the reevaluation may take place remotely via UB’s Campus Virtual if special circumstances prevent us to do it face-to-face.