M2RMA Calcul Exact Lundi, 13h30 UFR-IMA F-117

UJF > UFR-IMA > M2R-MathAppli > Calcul Exact Enseignants : Jean-Guillaume Dumas, Clément Pernet

---

News

• Présentation du cours à la réunion de rentrée: (.... à définir)

Crédits : 3ECTS, 18h

Mots clés:

calcul algébrique, algébre linéaire, complexité algorithmique, calcul certifié et conditionnement, différentiation automatique, cryptographie et codes

Introduction

Ce cours présente les aspects théoriques et pratiques du calcul algébrique: arithmétique et algèbre linéaire exactes. Il s'articule entre les questions de complexité, l'études des différents paradigmes algorithmiques et leurs applications en calcul mathématique, au codage, et au calcul certifié.
- Quelle est la difficulté de calculer un déterminant dans Z ?
- Y a-t-il des complexités optimales en algèbre linéaire?
- Les complexités asymptotiques doivent-elles être considérées pour les mise en pratique ?
- Comment augmenter et certifier la précision d'un calcul approché?
Nous étudirons une sélection des récentes avancées algorithmiques dans le domaine, ainsi que leur applications à la résolution de problèmes divers, comme l'étude de séquences ADN, la reconnaissance de formes, la théorie des codes, etc. Il conviendra aux étudiants intéressés autant par le thème de la complexité algorithmique que celui du calcul mathématique et ses applications.

Prérequis

Aucun

Contenu

• Éléments d'arithmétique entière et polynomiale.
• tests de primalité, factorisation, fonction d'Euler, éléments primitifs, Transformée de Fourier discrète
• Constructions effectives des corps finis, polynômes : irréductibilité, factorisation, remontée de Hensel
• Éléments d'arithmétique flottante à précision garantie.
• Modélisations utilisant le calcul exact:
• Recherche de chaines de caractères et découverte de motifs (ADN),
• Générateurs pseudo aléatoires et poésie
• Topologie algébrique (reconnaissance de formes, interactions moléculaires)
• Combinatoire et algèbre linéaire (isomorphisme de graphes)
• Codes correcteurs d'erreurs et tolérance aux fautes
• Cryptographie (RSA et Logarithme discret)
• Algèbre linéaire exacte
• Matrices denses et matrices creuses/structurées/boîtes noires
• Méthodes directes/itératives exactes
• Reconstructions d'entiers, de rationnels
• Algorithmes adaptatifs et bibliothèque internationale LinBox
• Algorithmes efficaces
• Déterminant, rang, résolution de systèmes, polynômes minimaux et caractéristiques, formes normales.
• Méthodes de Danilevski, FFLAS, Dixon, Wiedemann, Villard, Krylov, etc.

Déroulement du cours

L'introduction et les deux première parties auront lieu au premier semestre et les parties 3 et 4 au deuxième.

• Séance 1 (17 sept, F117) : Introduction (JGD)
  • Modélisation par le calcul exact
  • Démonstration logicielle
  • Modèles de complexité, Master théorème
  Documents annexes: BIBD.pdf, bibd1.pdf, bibd.cpp, binomial.hpp.

PARTIE 1 : Arithmétique et compléxité

• Séance 2 (25 sept) : Arithmétique (JGD)
  • Construction des corps finis
  • Algorithme d'Euclide
  • Racines primitives, primalité, irréductibilité, ...
• Séance 3 (1 oct): Calculs dans Z, Q, K(X) (Slides) (CP)
  • Theorème des restes chinois
  • Reconstruction rationnelle
  • Application aux Codes CRT et tolérance aux fautes
• Séance 4 (8 oct) : Exemple de modélisation : étude des séquences d'ADN (Slides)(JGD)
  • Recherche de chaînes de caractères
  • Découverte de motifs
• Séance 5 (15 oct): Arithmétique rapide des Polynômes et des entiersen précision arbitraire (CP)
  • Algorithmes diviser pour règner pour la multiplication
  • Karatsuba, Toom-Cook
  • FFT

PARTIE 2 : Algèbre linéaire dans un corps

• Séance 6 (22 oct): Algorithmique rapide de la multiplication des matrices (JGD)
  • Strassen-Winograd
  • Complexité mémoire
  • FFLAS
  • Substitution de Kronecker, redQ
  • M4RI
• Séance 7 (5 nov): Élimination de Gauss et applications: réductions au produit de matrices (CP)
  • TRSM et Décomposition PLE/CUP récursive par blocs
  • Applications: inverse, déterminant, résolution de système
  • Complexité mémoire
• Séance 8 (12 nov) : Bornes inf et équivalences en complexité arithmétique (CP)
  • Inverse et MatMul
  • Déterminant et Inverse
• Séance 9 (19 nov) : Polynôme caractéristique (CP)
  • Espaces de Krylov et méthode LU-Krylov
  • Algorithmes de Keller-Gehrig
  • Algorithme par progression arithmétique

PARTIE 3 : Algèbre linéaire creuse et boîte noire

• Séance 10 (26 nov) : Méthodes creuses et boîtes noires (JGD)
  • Elimination creuse
  • Heuristiques combinatoires, remplissage
  • Modèle de complextié boîte noire
  • Algorithmes de Berlekamp-Massey et Wiedemann
  • Préconditionneurs et application au calcul du déterminant, du rang...

PARTIE 4 : Algèbre linéaire dans Z ou K[X]

• Séance 11 (3 déc) :Calcul dans Z et complexités binaires (CP)
  • Evaluation/Interpolation et théorème des Restes Chinois
  • Méthode à la Newton: remontée de Dixon, remontée de haut rang
  • Tolérance aux fautes et codes correcteurs CRT: Reed-Solomon et Mandelbaum
• Séance 12 (10 dec) : Forme normale de Smith entière et topologie algébrique (JGD)
  • Complexes simpliciaux
  • RankSmithForm_JGDumas.pdf
• Séance 13 (17 dec) : Soutenances

Evaluation

L'évaluation se fera sous la forme d'une étude bibliographique, donnant lieu à un rapport et une présentation orale de 20 minutes suivie de 10 minutes de questions. Il s'agit de lire en détail un article de recherche ainsi qu'éventuellement quelques uns cités en référence, nécessaires à sa compréhension. Les étudiants sont libres de choisir un article dans liste ci-dessous, ou proposer des articles de leur choix.

• Quadratic-time certificates in linear algebra. (pdf)
  Erich L. Kaltofen, Michael Nehring, and B. David Saunders.
  In /Proc. 2011 Internat. Symp. Symbolic Algebraic Comput. ISSAC 2011 pages 171-176.
  Lecture complémentaire
  Bounds on Sample Space Size for Matrix Product Verification(pdf)
  Donald Chinn , Rakesh K. Sinha
  Information Processing Letters. Volume 48 Issue 2, Nov. 8, 1993
• On exact and approximate interpolation of sparse rational functions. (pdf)
  Erich Kaltofen and Zhengfeng Yang.
  In ISSAC 2007 Proc. 2007 Internat. Symp. Symbolic Algebraic Comput. pages 203-210.
  Lecture complémentaire:
  Early termination in sparse interpolation algorithms. (pdf)
  Erich Kaltofen and Wen-shin Lee.
  J. Symbolic Comput., 36(3-4):365-400, 2003.
• An LLL-reduction algorithm with quasi-linear time complexity(pdf)
  Andy Novocin, Damien Stehlé and Gilles Villard.
  STOC, San Jose, California, 2011,
  Lecture complémentaire:
  Faster Algorithms for Integer Lattice Basis Reduction.(pdf)
  Arne. Storjohann.
  Technical Report TR249, ETH-Zurich, Dpt. Comp. Sc., 1996.
• Optimizing linear maps modulo 2(pdf)
  D.J. Bernstein
  Lecture complémentaire:
  Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2)(pdf)
  Martin Albrecht, Gregory Bard and Bill Hart.
  ACM Transactions on Mathematical Software, Volume 37, pre-print available at http://arxiv.org/abs/0811.1714. 2009.
• Computing specified generators of structured matrix inverses,(pdf on demand)
  C-P. Jeannerod, C. Mouilleron
  ISSAC'10 Proceedings, Munich, July 2010.
  Lecture complémentaire!
  Solving structured linear systems with large displacement rank (pdf)
  Alin Bostan, Claude-Pierre Jeannerod, Eric Schost.

Biblio

Ce cours porte sur des résultats souvent récents en algèbre linéaire excacte. Il n'y a donc pas de livre de référence dans le domaine. On donne ici une liste d'ouvrage et d'articles dont le contenu du cours est en partie tiré.

Transparents ayant servi de support pour ceraines séances

• Que peut-on faire exactement, avec l'algèbre linéaire flottante
• Eliminations and echelon forms in exact linear algebra

Livres

• [ACT]: Algebraic complexity theory, Burgisser, Clausen, Shohrollahi
• [MCA]: Modern Computer Algebra, von zur Gathen and Gerhard
• [MT]: Matrix Theory, vol. 1, Gantmacher
• [Cormen]: Introduction to Algorithms, Cormen, Leiserson, Rivest
• [DACA]: The Design and Analysis of Computer Algorithms, Aho, Hopcroft, Ullman

Articles

La plupart de ces articles peuvent sont en ligne. Utiliser par exemple le moteur de google scholar pour les trouver.

• [Baur Strassen 83]:The complexity of partial derivatives
  Baur, Strassen, Theoretical Computer Science 22:317-330, 1983
• [Bunch Hopcroft 74]:Triangular Factorization and Inversion by Fast Matrix Multiplication
  Bunch, Hopcroft,
• [Chen & Al 01] Efficient matrix preconditioners for blackbox linear algebra (pdf)
  Chen, Eberly, Kaltofen, Saunders, Turner and Villard. Linear Algebra and its Applications, 343-344:119-146, 2002.
• [Coppersmith & Winograd 90]: Matrix multiplication via arithmetic progessions,
  Coppersmith, Winograd, J of Symbolic Computations, 9(3):251-280, 1990.
• [Dixon 82] Exact solution of linear equations using p-adic expansions. (pdf)
  Dixon. Numer. Math. vol 40:137:141 (1982).
• [Dumas & Al 05]: Efficient computation of the characteristic polynomial(pdf))
  Dumas, Pernet, Wan, In proceedings of ISSAC'2005
• [Dumas & Al. 10]: Subspaces of matrices with special rank properties (pdf)
  Dumas, Gow, McGuire, Sheekey. Linear Algebra and its Applications 433(1):191-202, 2010.
• [Keller-Gehrig 85]: Fast algorithms for the characteristic polynomial
  Keller-Gehrig, In Theoretical Computer Science vol 36:309-317, 1985.
• [Morgenstern]: How to compute fast a function and all its derivatives(pdf)
  Morgenstern, ACM SIGACT News, 16(4):60-62, 1985
• [Nuel Dumas 10]: Sparse approaches for the exact distribution of patterns in long multi-states sequences generated by a Markov source (pdf)
  Nuel, Dumas. Rapport de Recherche IMAG-hal-00492738, arXiv: math.Pr/1006.3246. 2010.
• [Pernet Storjohann 07]: Faster algorithm for the characteristic polynomial (pdf)
  Pernet, Storjohann, In proceedings of ISSAC'2007
• [Ruà & Al. 09]: Classification of semifields of order 64
  Rúa, Combarro, Ranilla. Journal of Algebra 322(11):4011-4029, 2009
• [Storjohann 03] High order lifting and integrality certification. (pdf)
  Storjohann. Journal of Symbolic Computation, vol 36(3-4):613-648 (2003).
• [Strassen 69]: Gaussian elimination is not optimal,
  Strassen, Numerische Mathematik, 13:354-356, 1969.
• [Villard 00] Computing the Frobenius normal form of a sparse matrix (ps)
  Villard. In proceedings of CASC'00.
• [Winograd 68]: A new algorithm for the inner product,
  Winograd, IEEE transaction on computers, C-17(7):693-694, 1968.