High-Performance Exact Computations Lundi, 14h00 -- 17h00 Ensimag, B001

UJF > UFR-IM²AG/ENSIMAG > M2 MSIAM > HPEC Enseignant : Jean-Guillaume Dumas

---

Crédits

Prérequis

Contenu

Déroulement

Évaluation

Références

Attestation

---

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 Certificats interactifs 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

• Séance 1 (30 novembre 2015) : Introduction
  • 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 (30 novembre 2015) : Arithmétique
  • Construction des corps finis
  • Algorithme d'Euclide
  • Racines primitives, primalité, irréductibilité, ...
• Séance 3 (7 décembre 2015): Calculs dans Z, Q, K(X) (Slides)
  • Theorème des restes chinois
  • Reconstruction rationnelle
  • Application aux Codes CRT et tolérance aux fautes
• Séance 4 (7 décembre 2015) : Exemple de modélisation : étude des séquences d'ADN (Slides)
  • Recherche de chaînes de caractères
  • Découverte de motifs
• Séance 5 (14 décembre 2015): Arithmétique rapide des Polynômes et des entier sen précision arbitraire
  • Algorithmes diviser pour règner pour la multiplication
  • Karatsuba, Toom-Cook
  • FFT

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

• Séance 6 (14 décembre 2015): Algorithmique rapide de la multiplication des matrices
  • Strassen-Winograd
  • Complexité mémoire
  • FFLAS
  • Substitution de Kronecker, redQ
  • M4RI
• Séance 7 (4 janvier 2016): Élimination de Gauss et applications: réductions au produit de matrices
  • 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 (4 janvier 2016) : Polynôme caractéristique
  • 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 9 (11 janvier 2016) : Méthodes creuses et boîtes noires (JGD)
  • Elimination creuse
  • Heuristiques combinatoires, remplissage
  • Modèle de complexité 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 10 (11 janvier 2016) :Calcul dans Z et complexités binaires
  • Evaluation/Interpolation et théorème des Restes Chinois
  • Méthode à la Newton: remontée de Dixon, remontée de haut rang
• Séance 11 (18 janvier 2016) : Forme normale de Smith entière et topologie algébrique (reconnaissance de formes, interactions moléculaires)
  • Complexes simpliciaux
  • RankSmithForm_JGDumas.pdf
• Séance 12 (18 janvier 2016) : Certificats interactifs
  • Vérifier l'agèbre linéaire en temps linéaire
  • Réductions de complexité (polynôme caractéristique, marices creuses)

Soutenances (1 février 2016)

Évaluation

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

• Time-Optimal Interactive Proofs for Circuit Evaluation (pdf).
  Justin Thaler, CRYPTO 2013.
  Lecture complémentaire : Essentially optimal interactive certificates in linear algebra (pdf). Jean-Guillaume Dumas et Erich Kaltofen. ISSAC 2014 : ACM International Symposium on Symbolic and Algebraic Computations, pages 146--153, Kobe, Japan, 23--25 Juillet 2014.


• Publicly Verifiable Delegation of Large Polynomials and Matrix Computations, with Applications (pdf).
  D. Fiore and R. Gennaro. 19th ACM Conference on Computer and Communications Security ACM CCS 2012, Raleigh, NC, USA. October 16-18, 2012. pp. 501-512.
  Lecture complémentaire : Efficient Secure and Verifiable Outsourcing of Matrix Multiplications (pdf). Y. Zhang and M. Blanton, , Information Security Conference (ISC'14), Oct. 2014.


• Fast matrix rank algorithms and applications (pdf).
  Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau. Journal of the ACM, 60(5), #31, 2013
  Lecture complémentaire : Efficient matrix preconditioners for black box linear algebra. (pdf ). L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Linear Algebra and Applications, 343-344:119-146, 2002.


• Linear independence oracles and applications to rectangular and low rank linear systems (pdf).
  Arne Storjohann and Shiyun Yang. ISSAC, Kobe, Japan, juillet 2014.
  Lecture complémentaire : A relaxed algorithm for online matrix inversion (pdf ). Arne Storjohann and Shiyun Yang. ISSAC, Bath, UK, 2015.


• 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.


• The bilinear complexity and practical algorithms for matrix multiplication (pdf)
  A. V. Smirnov. Computational Mathematics and Mathematical Physics December 2013, Volume 53, Issue 12, pp 1781-1795.
  Lecture complémentaire : Powers of Tensors and Fast Matrix Multiplication. (pdf). François Le Gall. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296-303, 2014.


• Fast computation for Smith forms of sparse matrices over local rings. (pdf)
  Mustafa ElSheik, Mark Giesbrecht, Andrew Novocin, and B. D. Saunders. Proc. 2012 Internat. Symp. Symbolic Algebraic Comput. ISSAC'12, Grenoble, France, July 22-25, pages 146-153, ACM Press, 2012.
  Lecture complémentaire : Large matrix, small rank (pdf). B. D. Saunders and B. Youse. In Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'09), pages 317--324, 2009.

Bibliographie

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 se trouver en ligne. Utiliser par exemple le moteur de google scholar pour les trouver.

• An LLL-reduction algorithm with quasi-linear time complexity(pdf).
• [Albrecht & al 08]: Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2) (pdf).
• [Baur Strassen 83]: The complexity of partial derivatives
  Baur, Strassen, Theoretical Computer Science 22:317-330, 1983
• [Berstein 09]: Optimizing linear maps modulo 2 (pdf).
• [Bostan & al 08]: Solving structured linear systems with large displacement rank (pdf)
• [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.
• [Jeannerod Mouilleron 10]: Computing specified generators of structured matrix inverses,(pdf)
• [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.
• [Parno & al. 13]: Pinocchio: Nearly Practical Verifiable Computation (pdf)
  Parno, Gentry, Howell, Raykova. IEEE Symposium on Security and Privacy, 21 May 2013.
• [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).
• [Storjohann 96]: Faster Algorithms for Integer Lattice Basis Reduction. (pdf).
• [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.