General information 
Course unit name: Computational Algebra
Course unit code: 568186
Academic year: 20182019
Coordinator: Luis Victor Dieulefait
Department: Department of Mathematics and Computer Science
Credits: 6
Single program: S
Estimated learning time 
Total number of hours 150 
Facetoface learning activities 
60 
 Lecture 
30 

 Problemsolving 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 

Competences to be gained during study 

Learning objectives 
Referring to knowledge
Referring to abilities, skills

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önhageStrassen 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: CantorZassenhaus algorithm
2.2. Hensel’s Lemma and factorization of polynomials. Zassenhaus algorithm.
2.3. Short vectors in lattices: LenstraLenstraLovasz algorithm, factorization in Q[x]
3. Systems of polynomial equations
3.1. Real roots of a polynomial: Descartes rule of signs, BudanFourier and Sturm theorems, Hermite theorem
3.2. Gröbner basis: Monomial orders and division with remainder for multivariate polynomials, Spolynomials 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: 
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.
Examinationbased assessment 
Reading and study resources 
Consulteu la disponibilitat a CERCABIB
Book
Von zur Gathen, Joachim. Modern computer algebra. Cambridge : Cambridge University Press, 2003.
Cox, David A.; Little, John; O’Shea, Donal. Using algebraic geometry. New York : Springer, 2005.
Bochnak, J. ; Coste, M. ; Roy, M.F. Géométrie algébrique réelle. Berlin : SpringerVerlag, 1987.