Calcul Algébrique Haute-Performance – HPAC

L'ambition de HPAC est de fournir des bibliothèques de calcul
algébrique intensif de référence au niveau international sur
architectures multi-processeurs et d'influencer les approches de
programmation parallèle pour le calcul algébrique en général.

HPAC rassemble des chercheurs travaillant sur les langages et
environnements de parallélisme, le génie logiciel au niveau
intergiciel, l'algèbre linéaire, les systèmes algébriques, la
cryptologie et les calculs vérifiés symboliques-numériques. Le
principal défi du projet est la conception et la mise en œuvre
d'algorithmes mathématiques exacts et vérifiés, adaptatifs, et à
performances garanties et pérennes.

LinBox et FGb sont deux bibliothèques dédiées de référence en calcul
mathématique.
LinBox offre un large éventail de fonctionnalités en algèbre linéaire
exacte et est utilisée notamment par le système Sage. FGb est la
référence pour les calculs de bases de Gröbner, par exemple utilisable
via Maple. Ces bibliothèques sont séquentielles et s'appuient
fondamentalement sur des noyaux de calcul matriciel hautement
performants.
L'objectif principal du projet HPAC est d'étendre leur efficacité en
parallèle sur de nouvelles architectures comme les clusters de
systèmes multi-processeurs, les multi-cartes graphiques. Ceci
permettra, en particulier, d'aborder une plus large classe de
problèmes en cryptographie à base de réseaux euclidiens et en
cryptanalyse algébrique.

Nos recherches seront conduites selon 3 axes :
- un langage parallèle spécifique (DSL,Domain Specific Language) pour
le calcul algébrique intensif ;
- des noyaux parallèles d'algèbre linéaire et des algorithmes et
bibliothèques mathématiques de plus haut niveau ;
- des outils de composition de bibliothèques et des solutions
novatrices en cryptologie.

Un point essentiel est que ces 3 axes sont étroitement liés. Chacun
d'entre eux contribue à garantir le succès des autres, par exemple :
le langage DSL sera conçu pour mettre en œuvre des programmes de plus
haut niveau qui, en retour, permettront sa validation (en particulier
au niveau efficacité) ; pour valider le DSL et pour s'attaquer aux
défis cryptologiques, notre expertise en algèbre linéaire, systèmes
algébriques et cryptologie nous permettra de veiller à ce que les
meilleurs algorithmes connus soient utilisés.

Nos objectifs conduiront aux résultats suivants :
- des briques de base (PBB, Parallel Building Blocks) en parallélisme
de données et de tâches, adaptées au calcul algébrique et dont
l'interface définira le langage parallèle ;
- une validation de l'intégrabilité des PBB dans des algorithmes de
haut niveau et de leur passage à l'échelle sur différentes
architectures ;
- une multiplication et des décompositions parallèles de matrices
denses et hybrides creuses-denses ;
- une forme échelonnée parallèle sur les corps finis pour des
dimensions et tailles adaptées à la cryptographie ;
- des solutions parallèles pour les algorithmes de type Wiedemann,
formes normales de matrices, algèbre linéaire vérifiée et réduction de
réseaux ;
- des nouvelles versions de FGb et LinBox incluant des fonctionnalités
parallèles ;
- une intégration fine de ces bibliothèques dans les systèmes de
calcul formel Sage, Maple ou Mathemagix, avec un port vers des calculs
numériques vérifiés dans des logiciels tels que Scilab et Matlab ;
- de nouveaux algorithmes d'algèbre linéaire et des publications
internationales de nos résultats ;
- de nouvelles solutions distribuées, pour des défis cryptologiques :
* estimations précises de la taille des paramètres de systèmes de
cryptographie à base de réseaux euclidiens ;
* des outils dédiés pour les problèmes d'algèbre linéaire générés au
cours de calculs de bases de Gröbner utilisées en cryptanalyse
algébrique.