Seminar/2015-03-11

From LRDE

Mercredi 11 mars 2015, 10h30-12h30, Salle L0 du LRDE


Généricité et efficacité en algèbre linéaire exacte avec les bibliothèques FFLAS-FFPACK et LinBox

Clément Pernet, Univ. Grenoble-Alpes, INRIA, LIP équipe AriC

Motivé par de nombreuses applications, allant de la cryptographie au calcul mathématique, le calcul formel s'est fortement développé ces dernières années tant au niveau des algorithmes que des implantations efficaces. L'efficacité des calculs repose sur celle de bibliothèques dédiées, pour certaines opérations de base, comme l'algèbre linéaire dans un corps fini ou avec des entiers multi-précision. Devant la multiplicité des domaines de calcul et des variantes algorithmiques disponibles, la conception de ces bibliothèques doit concilier une forte généricité avec l'efficacité.

Nous allons présenter comment cette problématique est abordée dans les bibliothèques d'algèbre linéaire exacte FFLAS-FFPACK (2) et LinBox (3). Après une présentation générale de ces projets, nous focaliserons la présentation sur trois aspects représentatifs:

- l'exploitation des diverses arithmétiques de base (entière, flottante, booléenne), de routines numériques optimisées et leur intégration au sein d'algorithmes génériques haut niveau ;

- l'approche boîte-noire de la bibliothèque LinBox, proposant un modèle algorithmique spécifique, particulièrement performant pour les matrices creuses ou structurées ;

- La parallélisation de code dans FFLAS-FFPACK, basée sur un langage spécifique (DSL) permettant d'utiliser de façon interchangeable différents langages et moteurs exécutifs, et de tirer parti du parallélisme de tâche avec dépendance par flot de données.

Clément Pernet est maître de conférence en informatique à l'Université Grenoble-Alpes. Sa recherche en calcul formel porte sur l'algèbre linéaire exacte tant au niveau algorithmique que logiciel. Dans le contexte de la fiabilité du calcul exact distribué, il aborde aussi la tolérance aux erreurs silencieuses via les codes correcteurs d'erreurs.

(1) http://lig-membres.imag.fr/pernet "(1) http" has not been listed as valid URI scheme., (2) http://linalg.org/projects/fflas-ffpack "(2) http" has not been listed as valid URI scheme., (3) http://linalg.org "(3) http" has not been listed as valid URI scheme.



Multiplication matrice creuse-vecteur dense exacte et efficace.

Brice Boyer, UPMC CNRS INRIA, LIP6 équipe POLSYS

Tout d'abord, nous présentons un cadre générique et rapide pour les opérations SIMD (single instruction multiple data), écrit en C++ à l'intérieur de la bibliothèque d'algèbre linéaire exacte FFLAS-FFPACK (2).

Nous montrons aussi une technique de conception (modules "helper") basée sur le patron de conception Strategy, qui permet une sélection efficace d'algorithmes récursifs, des signatures de fonctions plus simples et plus uniformes. Ensuite, nous appliquons ces techniques pour accélérer la multiplication entre matrices creuses et vecteurs denses (SpMV) sur des anneaux Z/pZ, en utilisant des formats conçus pour les opérations vectorielles et en combinant diverses représentations.

Finalement, nous généralisons ces techniques aux blocs de vecteurs (matrices denses, SpMM) et étendons nos algorithmes aux entiers de Z. Nous appliquons aussi ces briques de base au calcul du rang de grandes matrices creuses avec l'algorithme bloc-Wiedemann.

Brice Boyer (1) a effectué une thèse de doctorat sous la direction de Jean-Guillaume Dumas intitulée /Multiplication matricielle efficace et conception logicielle pour la bibliothèque de calcul exact LinBox/. Il a ensuite effectué un post-doctorat de deux ans à la North Carolina State University (USA) puis un autre à l'UPMC (Paris). Ses intérêts incluent l'algèbre linéaire exacte dense et creuse, la conception et le développement logiciels, le calcul parallèle.

(1) http://www-polsys.lip6.fr/~boyer "(1) http" has not been listed as valid URI scheme., (2) http://linalg.org/projects/fflas-ffpack "(2) http" has not been listed as valid URI scheme.