Algebraic and Combinatorial Techniques for Computing

Enseignants

Jungers Raphaël; Remacle Jean-François;

Langue
d'enseignement

Anglais
> Facilités pour suivre le cours en français

Préalables

Formation de base en algèbre linéaire et en calcul numérique (LEPL1101, LINMA1170).

Thèmes abordés

Ce cours s'appuie sur les solides fondements mathématiques de la théorie des matrices et de la théorie des graphes pour développer des solutions algorithmiques aux problèmes d'ingénierie.
● Matrices polynomiales et structurées : algorithme d'Euclide, formes normales de Smith et d'Hermite, algorithmes rapides
● Semi-groupes de matrices : structure algébrique, algorithmes et applications (par exemple, factorisation non négative, caractéristiques spectrales conjointes)
● Matrices creuses et structures cordales
● Préconditionnement des méthodes itératives, gradients conjugués préconditionnés
● Sujets avancés présentés lors d'un séminaire (optimisation combinatoire et techniques algébriques, théorie spectrale et algébrique des graphes, algèbre tropicale, tenseurs et algèbre multilinéaire, calcul symbolique, théorie des matroïdes)

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

Ce cours renforce les acquis d'apprentissage suivants : ● AA1.1, AA1.2 ● AA5.5 ● AA6.3 Plus précisément, l'étudiant sera capable de : ● Maîtriser l'algèbre linéaire avancée ● Analyser les propriétés mathématiques de divers problèmes en mathématiques appliquées et concevoir des solutions algorithmiques à l'aide de théories mathématiques avancées ● Appliquer ou développer des algorithmes spécifiques pour des applications en statistiques, traitement du signal, imagerie et systèmes dynamiques ● Implémenter des méthodes dans des logiciels de haut niveau et valider leur comportement sur des problèmes concrets Compétences transversales : ● Collaborer en petites équipes pour résoudre numériquement des problèmes mathématiques

Contenu

1. Formes canoniques et calculs sur le quotient d'un ensemble
2. Théorème de Jordan : démonstration et conséquences
3. Matrices polynomiales : formes normales de Smith et d'Hermite, algorithmes rapides
4. Matrices structurées
5. Caractéristiques spectrales conjointes
6. Méthodes directes de résolution de systèmes : LU, Cholesky, pivotage,
réordonnancement (RCMK), stockage creux, remplissage
7. Méthodes itératives de Krylov : itération d'Arnoldi, gradients conjugués,
GMRES, Lanczos
8. Matrices creuses et structures cordales
9. Préconditionnement des méthodes itératives, gradients conjugués préconditionnés

Méthodes d'enseignement

• Cours magistraux
• Devoirs en groupe
• Présentations en classe inversée par les étudiants

Modes d'évaluation
des acquis des étudiants

L'évaluation des étudiants repose en partie sur un examen écrit (ou oral,
selon les circonstances) organisé conformément aux règles imposées par l'EPL. Le contenu de l'examen correspond aux cours magistraux et aux notes de cours, à l'exception possible de certaines parties précisées après la dernière séance du semestre.
Pour un examen écrit, en cas de doute, l'enseignant peut convoquer l'étudiant à un examen oral complémentaire.
L'autre partie de l'évaluation repose sur les travaux et les présentations réalisés au cours du semestre, et sera prise en compte en janvier et en septembre.

Ressources
en ligne

http://moodleucl.uclouvain.be/course/view.php?id=7969

Bibliographie

Ouvrages de référence :
● G.H. Golub and C.F. Van Loan (1989). Matrix 
Computations, 2nd Ed, Johns Hopkins University Press, 
Baltimore. 
● P. Lancaster and M. Tismenetsky (1985). The Theory of 
Matrices, 2nd Ed, Academic Press, New York 
● Trefethen, L. N., & Bau III, D. Numerical linear algebra 
(Vol. 50). Siam.

Support de cours

• LINMA 2380 Course notes by R.J. et al.

Faculté ou entité
en charge

> MAP