Liens transverses ENS de Lyon

INFO4218 : Computer algebra

Niveau M1+M2

Discipline(s) Informatique

ECTS 3.00

Période 2e semestre

Localisation Site Monod

Année 2019-2020

 Public externe (ouverts aux auditeurs de cours)
 

Objectif du cours

This class shall survey some of the central topics of computer algebra : arithmetics, effective linear algebra, polynomial system solving. The following topics will be studied :

I. Arithmetic(s) — mostly polynomial. – Representation of polynomials, linear operations (addition, evaluation). – Multiplication : schoolbook method, Karatsuba method, Toom-Cook method Fast Fourier Transform. – Division : schoolbook method, Newton method, recursive division – GCD : Euclidean algorithm, extended GCD, application to CRT; introduction to fast GCD. – Fast multiple point evaluation, fast interpolation, fast CRT.

II. Linear algebra over a field – Matrix/vector product, naive matrix/matrix product – Row echelon form & applications : kernel, image, rank, determinant, linear system solving, etc. – Fast matrix/matrix product : Strassen ; fast inversion/determinant. – Structured matrices: circulant, Hankel, Toeplitz, Cauchy, and related algorithms.

Modifié le :
02/07/2019 10:41:57