ALGEBRE LINEAIRE AVANCEE

Les méthodes itératives de Krylov sont des méthodes efficaces pour résoudre de très grands systèmes d’équations linéaires. On les utilise notamment en simulation numérique, mécanique, traitement d’images ou apprentissage automatique, là où les méthodes directes seraient trop lentes ou trop coûteuses.

points abordés : 
 - notion d'espace de Krylov et construction d'une base de cet espace
 - présentation des méthodes FOM, GMRES
 - introduction au préconditionnement

Toujours dans le cas de grands systèmes d'équations s'exprimant sous forme de matrices creuses (présentant un nombre de zéros significatif), on peut adapter les méthodes directes, à base de factorisation, à condition de préserver le caractère creux des matrices que l'on manipule (facteurs).

points abordés :
 - ré-ordonnacement, minimisation du remplissage
 - factorisation creuse, arbre d'élimination
 - méthode multi-frontale

Voir la page complète

Ce cours commence par rappeler l'ensemble des notions déjà vues en algèbre linéaire numérique, avec notamment les systèmes d’équations linéaires et leur résolution. Certaines extensions sont développées en détail, comme la notion de corrélation canonique entre sous-espaces, les formules de Sherman-Morrisson-Woodbury, ainsi que les notions d'analyse d'erreur a priori et d'analyse d'erreur a posteriori.

Une partie importante du cours est consacrée à la réduction de dimension, en particulier au travers des décompositions matricielles, comme la décomposition en valeurs singulière, ou les méthodes de Krylov basées sur le processus de bidiagonalisation de Lanczos-Golub-Kahan, ou bien encore les méthodes de factorisation non-négative, et leur rôle dans les systèmes de recommandation, la compression de données et le traitement de l’information.

La dernière partie du cours présente diverses notions complémentaires, comme la régularisation de Tikhonov, la validation croisée généralisée, les moindres carrés totaux, les moindres carrés linéaires mixtes,  ainsi que l'homogénéisation des données par des techniques de Scaling et leur application à la classification spectrale ou le page-ranking, avec l'exploitation du théorème de Perron-Frobenius en particulier. Les travaux pratiques, qui comptent pour presque la moitié des séances, permettent d'illustrer sur des cas concrets les diverses notions abordées. 

Voir la page complète

Au sein de ce module, sont décrits en premier lieu des algorithmes déterministes pour la factorisation au sens du rang faible de matrices creuses ou denses. Ces méthodes sont principalement basées sur la notion de décomposition interpolatoire (Interpolative Decomposition ou ID). Différentes variantes algorithmiques sont introduites (ID, Row ID, Column ID, Two sided ID, CUR-ID notamment). Ces méthodes récentes viennent compléter les méthodes classiques de factorisation orthogonale QR avec pivotage de colonnes par exemple. 

En second lieu sont abordées les variantes basées sur des factorisations de rang faible exploitant l'aléatoire. Ces variantes sont en effet particulièrement intéressantes dans ce contexte car elles permettent de réduire les coûts de calcul et éventuellement d'exploiter le parallélisme de façon plus prononcée que lors de l'emploi des variantes déterministes. 

Ces différents algorithmes sont mis en œuvre au travers d'un projet sous le format Notebook en Python. Les étudiants comparent l'efficacité, la précision et la robustesse de ces méthodes sur un problème de traitement d'images. 

Ce module est orienté vers la pratique: il comporte deux séances de TP et un C/TD introductif permettant de présenter le contexte de l'étude. 

Voir la page complète