RAIM'09 – résumés

Session Numération

Représentation des nombres et automates finis

Orateur : Jacques Sakarovitch (LTCI, CNRS / ENST)

PDF de la présentation

Résumé : Les nombres sont représentés par leur développement dans une base, et donc par des mots (finis ou infinis) sur un alphabet de chiffres. Nous nous intéresserons à la question de savoir si l'ensemble de ces développements est un langage rationnel, i.e. reconnu par un automate fini, à celle de déterminer quelles opérations sur les nombres se transmuent en des fonctions sur les développements qui sont réalisables par des transducteurs finis, et comment le choix des chiffres peut influer sur le type transducteurs obtenus. Nous commencerons par le cas classique, et néanmoins instructif, des bases entières. Le coeur de l'étude sera celui où la base est un entier algébrique, avec la description d'une nouvelle propriété caractéristique des nombres de Pisot. Dans tous ces cas, et d'ailleurs dans d'autres aussi que nous n'aurons pas le temps d'examiner, l'analyse est conduite en introduisant systématiquement l'automate (pas nécessairement fini) qui reconnaît les écritures de 0 sur un alphabet symétrique. Les différents transducteurs que l'on veut obtenir s'en déduisent ensuite facilement.

Le développement de certaines périodes exponentielles dans une base entière

Orateur : Boris Adamczewski (Institut Camille Jordan, CNRS, Université de Lyon 1)

PDF de la présentation

Résumé : Le développement binaire ou décimal de nombreuses constantes classiques telles que π, e ou √2 semble, si ce n'est aléatoire, du moins jouir d'une certaine complexité. Ce constat fait l'objet de questions délicates qui, pour la plupart, demeurent encore sans réponse. Quelques progrès ont été toutefois obtenus ces dernières années pour les nombres algébriques, puis tout récemment pour certaines périodes exponentielles comme le nombre e. L'approche utilisée combine des résultats de l'approximation diophantienne et de la combinatoire des mots. Nous dresserons un état de l'art concernant ces problèmes.

Représentation de nombres par des automates dénombrables et des langages non réguliers

Oratrice : Marion Le Gonidec (Université de Toulon)

PDF de la présentation

Résumé : En numération, de nombreux objets sont usuellement associés aux langages réguliers et aux automates finis: ensembles d'entiers k-reconnaissables, suites k-automatiques et substitutives, systèmes de représentations des entiers et/ou des réels basés sur des langages réguliers... Ces objets ont fait l'objet d'un grand nombre de travaux notamment du fait de leur implications dans différents domaines: arithmétique, dynamique, algorithmique... Nous nous intéresserons dans cet exposé à ces mêmes objets hors du cadre régulier: ensembles d'entiers reconnaissables par automates à pile et suites k-algébriques (k-context free sequences); ensembles d'entiers reconnaissables par automates dénombrables ayant un nombre fini d'états terminaux et suites k-automatiques. Quels résultats classiques et leurs applications dans le cadre régulier s'étendent à ces ensembles d'entiers et ces suites? Nous aborderons également la question suivante: si, a priori, tout langage infini peut servir de système de représentation des entiers, quelles conditions doit vérifier un langage pour fournir une bonne base de représentation des nombres réels?

Écritures de nombres en base réelle, fractals et pavages

Orateur : Wolfgang Steiner (LIAFA, CNRS, Université Paris Diderot - Paris 7)

PDF de la présentation

Résumé : L'écriture en base 2 d'un nombre réel x peut être obtenue à l'aide de la transformation T(x) = 2x − [2x], où [.] désigne la partie entière d'un nombre. Plus généralement, on peut écrire tout nombre réel dans n'importe quelle base β > 1: l'écriture s'obtient par un algorithme glouton à partir de la transformation T(x) = βx − [βx]. Une question naturelle est alors de comprendre quelles sont les propriétés des écritures de nombres qu'on obtient avec cet algorithme: qui a un β-développement purement périodique? Comment déterminer le n-ième chiffre dans le β-développement d'un nombre sans connaître les autres chiffres? Pour répondre à ces questions dans le cas où β est un nombre de Pisot unitaire, on étend la fonction T (en rajoutant des coordonnées à son graphe) de manière à obtenir une fonction inversible et exploitable. Nous illustrerons comment cette extension naturelle permet de mieux comprendre les propriétés des β-développements de réels. Nous montrerons aussi comment l'extension naturelle est étroitement liée à des ensembles dont le bord est généralement un fractal, et nous discuterons des propriétés de pavages de ces ensembles fractals.

Représentation de nombres par des fractions continues : extensions (Rosen) et algorithmes

Orateur : Benoît Rittaud (Université Paris 13)

PDF de la présentation

Résumé : Une alternative à l'écriture de nombres dans différentes bases consiste à décomposer un nombre sous forme de fractions superposées, de la forme x = a + 1 / (b + 1 / c + 1 / ...). On parle alors de développement en fractions continues. Une manière efficace pour trouver les coefficients a, b, c... (appelés quotients partiels) consiste à parcourir un arbre qui décrit toutes les fractions irréductibles. Il s'agit de l'algorithme de Stern-Brocot. Une fraction continue de Rosen consiste à complexifier un peu l'écriture des nombres en remplaçant les entiers a, b, c... par des multiples entiers (non nécessairement positifs) d'un réel λ de la forme 2 cos(π/k) (où k ≥ 3 est un entier). Dans cet exposé, nous étendons l'algorithme de Stern-Brocot des fractions continues classiques pour montrer comment les fractions continues de Rosen fournissent un équivalent hyperbolique de la numération en base k − 1. Poursuivre cette idée conduit à définir des fractions continues de Rosen généralisées qui correspondent à des systèmes de numération en base non entière.

Cours d'ouverture thématique

Accélérateurs matériels de calcul

Orateurs : David Defour et Florent de Dinechin

PDF de l'introductionPDF de la présentation de David DefourPDF de la présentation de Florent de Dinechin

Résumé : Dans cet exposé, nous survolons quelques techniques contemporaines d'accélération matérielle des calculs, essentiellement au moyen de circuits logiques reconfigurables (FPGA) et d'accélérateurs graphiques (GPU). Nous mettons l'accent sur les classes de problèmes accélérables, en particulier sur l'arithmétique de toute chose, mais aussi sur les problématiques de déplacement de données, et sur la difficulté de programmer de telles applications. Nous nous risquerons peut-être à un peu de prospective.

Session Géométrie et arithmétique

Méthodes par intervalles pour la résolution de systèmes d'équations non linéaires

Orateur : Gilles Trombettoni (Université de Nice-Sophia, équipe-projet COPRIN)

PDF de la présentation

Résumé : Cet exposé présente de manière synthétique le schéma de résolution des systèmes de contraintes (équations, inégalités) non linéaires à l'aide de méthodes à intervalles. On présentera principalement les trois catégories d'algorithmes de filtrage/contraction, c'est-à-dire de simplification de l'espace de recherche en temps polynomial: le Newton par intervalles issu de l'analyse numérique (par intervalles), les algorithmes de programmation par contraintes et la relaxation linéaire. Nous terminerons par des schémas plus généraux permettant d'approcher un ensemble infini de solutions par des boîtes extérieures et intérieures, ou de traiter les systèmes avec quantificateurs (existentiels et universels) avec des arbres et/ou des intervalles modaux ou des intervalles généralisés.

Sur le calcul de la topologie d'objets en utilisant seulement de l'arithmétique d'intervalles

Orateur : Nicolas Delanoue (Université d'Angers, LISA)

PDF de la présentation

Résumé : Durant cet exposé, on donne un algorithme numérique capable de créer une triangulation du même type d'homotopie qu'un ensemble S décrit par des inégalités (polynomiales ou non). La méthode proposée divise S en sous-ensembles qui ont été montrés contractiles avec le calcul par intervalles. Des exemples illustrent le principe de l'approche.

Un solveur de systèmes non linéaires basé sur le polytope de Bernstein

Orateur : Christoph Fünfzig (Université de Bourgogne, LE2I)

PDF de la présentation

Résumé : Les bases tensorielles de Bernstein permettent de calculer de bons encadrements des valeurs de polynômes sur des pavés, et de résoudre les systèmes polynomiaux rencontrés en synthèse d'images, en modélisation géométrique, et en résolution de contraintes géométriques. Exprimer le polynôme multivarié dans la base tensorielle de Bernstein est classique et simple, mais limité aux petits systèmes de 6 ou 7 inconnues. Cet exposé présente un nouveau solveur, qui est utilisable sur des systèmes de grande taille. Le solveur utilise la programmation linéaire avec un polytope de Bernstein pour les monômes de la base canonique.

Robustesse des algorithmes géométriques: des outils arithmétiques à l'interface utilisateur dans CGAL

Orateur : Sylvain Pion (INRIA, équipe-projet Geometrica)

PDF de la présentation

Résumé : Je présenterai rapidement les problèmes classiques de robustesse des algorithmes géométriques. J'introduirai ensuite les différents outils arithmétiques qui sont utilisés, et enfin j'expliquerai comment tous ces outils sont mis en oeuvre en pratique dans la bibliothèque CGAL.

Calcul différentiel discret par convolutions binomiales

Orateur : Remy Malgouyres (Université d'Auvergne, LAIC)

PDF de la présentation

Résumé : Le calcul différentiel sur les signaux discrets (images, sons...) se fait souvent en utilisant des convolutions par des gaussiennes et leurs dérivées. Cependant, le calcul flottant montre parfois ses limites lorsqu'on augmente la précision recherchée car les erreurs sur les opérations arithmétiques se cumulent. Les noyaux binomiaux sont une approximation des noyaux gaussiens qui sont définis par des dyadiques. Il permettent de concevoir une nouvelle approche du calcul différentiel avec une arithmétique exacte. On peut paralléliser les calculs avec RNS. Dans l'exposé, on présente des résultats d'approximation de dérivées estimées sur des données bruitées, ainsi que des calculs de dérivées partielles sur les surfaces discrètes. Des questions sur les équations différentielles et aux dérivées partielles seront évoquées.

Session Opérateurs arithmétiques

Opérateurs arithmétiques sécurisés

Orateur : Arnaud Tisserand (CNRS, IRISA, équipe CAIRN)

PDF de la présentation

Résumé : La sécurisation des circuits intégrés présents dans les systèmes embarqués est un thème de recherche en pleine croissance ces dernières années. Les attaques physiques comme les attaques par canaux cachés permettent de trouver des informations critiques (portions de clés ou de messages en clair) sur des cryptosystèmes théoriquement robustes. Nous présenterons des attaques classiques par analyse de la consommation d'énergie ou du rayonnement électromagnétique. Dans un deuxième temps, nous regarderons des contre-mesures au niveau arithmétique (représentations des nombres et algorithmes de calcul des opérations de base). Par exemple, le recodage des clés avec des systèmes de représentation des nombres particuliers est souvent proposé pour se protéger contre certaines attaques. Le niveau de sécurité d'un circuit intégré contre des attaques physiques devient un critère de conception en plus de la vitesse, la surface de silicium et la consommation d'énergie.

Calcul du produit scalaire dans un grand corps fini en arithmétique flottante

Orateur : Jérémy Jean (PEQUAN, LIP6, Université Pierre et Marie Curie Paris 6)

PDF de la présentation

Résumé : Les corps finis ont des applications particulièrement intéressantes dans beaucoup de domaines, et il est important d'avoir des modes de calculs rapides pour les manipuler. L'approche choisie consiste à représenter les grands entiers du corps dans des nombres flottants sur lesquels les calculs sont efficaces. La problématique principale est de gérer correctement les erreurs potentielles liées aux calculs flottants pour obtenir un résultat exact. En utilisant des algorithmes de transformations exactes sur des architectures récentes, on voit qu'il est possible de gérer des corps finis relativement grands de manière exacte. Je présenterai deux méthodes légèrement différentes pour le calcul du produit scalaire de deux vecteurs chacune visant à réduire le temps de calcul.

LNS sur architectures exotiques

Orateur : Sylvain Collange (DALI, ELIAUS, Université de Perpignan)

PDF de la présentation

Résumé : Bien que les GPU se transforment de plus en plus en coprocesseurs généralistes, ils offrent toujours des unités matérielles spécialisées pour le rendu graphique, notamment de filtrage de texture. Nous présenterons une manière de détourner cette unité de filtrage de son usage habituel pour lui faire évaluer des approximations polynomiales par morceaux. En particulier, nous appliquerons cette méthode pour effectuer des calculs dans le système logarithmique (LNS).

Pollard Rho sur Playstation3

Orateur : Marcelo Kaihara (EPFL)

PDF de la présentation

Résumé : Dans cet exposé, nous présentons une implémentation de haute performance sur PlayStation3 (PS3) de l'algorithme rho de Pollard pour résoudre le problème du logarithme discret sur les courbes elliptiques défini sur les corps premiers. Nous expliquerons comment nous avons établi un record mondial en résolvant, avec cette implémentation, le problème de logarithmes discrets sur courbes elliptiques défini sur un corps premier de 112 bits (avec paramètres du domaine standardisés). Nous présenterons les algorithmes arithmétiques qui ont été reconstruits pour les PS3 afin d'utiliser au maximum l'achitecture SIMD et l'ensemble des instructions des processeurs vectoriels.

Un accélérateur matériel pour le couplage de Tate en caractéristique trois à base de multiplieur Karatsuba

Orateur : Jérémie Detrey (INRIA, CACAO)

PDF de la présentation

Résumé : Introduits initialement dans le domaine de la cryptographie par Menezes, Okamoto & Vanstone (1993) puis Frey & Rück (1994) pour attaquer le problème du logarithme discret sur certaines courbes elliptiques, les couplages sont depuis quelques années à la base de nombreux protocoles utiles en cryptographie tels que la signature numérique courte ou la cryptographie basée sur l'identité. Le calcul de ces couplages reposant lourdement sur l'arithmétique sur les corps finis, leur réalisation en logiciel reste coûteuse et le développement d'accélérateurs matériels est essentiel.

Dans cet exposé, nous présentons ainsi un co-processeur dédié au calcul du couplage de Tate, conçu dans une optique de minimisation du temps de calcul et reposant pour cela sur un multiplieur rapide à la Karatsuba. Certaines des considérations algorithmiques et architecturales propres à ce travail seront abordées au cours de l'exposé.

Cours d'ouverture thématique

Arithmétique pour les applications de traitement du signal embarquées

Orateur : Daniel Ménard

PDF de la présentation

Résumé : L'objectif de cet exposé est de présenter l'arithmétique utilisée dans les systèmes embarqués pour implanter des applications de traitement du signal et de l'image (TDSI). Dans un premier temps, quelques éléments de traitement du signal seront présentés et les différents cœurs de traitement couramment utilisés en TDSI (filtres linéaires, filtres adaptatifs, transformées: FFT, DCT Wavelet...) seront décrits. Dans un second temps, les domaines d'applications du TDSI et les contraintes associées aux applications embarquées seront détaillés. Cette analyse permettra d'expliquer et de justifier l'utilisation de l'arithmétique virgule fixe pour les systèmes embarqués de TDSI. Dans un troisième temps, la problématique de conversion en virgule fixe pour des applications de TDSI sera présentée. Les différentes étapes de conversion en virgule fixe seront détaillées.

Session Validation numérique et preuve formelle

Calculs numériques et méthodes formelles

Orateur : Guillaume Melquiond (INRIA, LRI / Université Paris Sud, équipe-projet ProVal)

PDF de la présentation

Résumé : Cet exposé sera l'occasion de présenter quelques travaux à l'intersection des domaines de l'arithmétique des ordinateurs, entre autres celle à virgule flottante, et des méthodes formelles telles que la certification de programmes ou la preuve mathématique.

L'outil Gappa servira de point de départ. En effet, son utilisation permet de découvrir ou de vérifier des propriétés de codes numériques. Mais il a la particularité de générer des preuves formelles de ces propriétés, preuves dont la correction dépend de calculs effectués dans des formalismes logiques.

Partant de là, la présentation se portera sur quelques approches s'appuyant sur du calcul pour faire des preuves mathématiques dans des systèmes formels; dans le désordre: arithmétique par intervalles, polynômes de Bernstein, élimination des quantificateurs, arithmétique exacte, etc.

Preuves de programmes numériques indépendantes du compilateur et du processeur

Oratrice : Sylvie Boldo (INRIA, LRI / Université Paris Sud, équipe-projet ProVal)

PDF de la présentation

Résumé : Sur les processeurs récents, un programme numérique peut donner des réponses différentes selon l'architecture et le compilateur. Nous souhaitons ici prouver des propriétés valides quels que soient l'architecture et les choix du compilateur (dans une certaine limite). Nous utilisons pour cela une approche basée sur l'erreur d'arrondi, prouvée, et utilisable dans la plate-forme Frama-C.

Vérification formelle et arithmétique réelle exacte

Oratrice : Ioana Pasca (INRIA, équipe-projet Marelle)

PDF de la présentation

Résumé : La formalisation de l'arithmétique réelle exacte a reçu beaucoup d'attention ces dernières années. Il existe plusieurs bibliothèques basées sur différents algorithmes et formalisées dans différents assistants à la preuve. Le but de cet exposé est de faire un bref état de l'art sur trois bibliothèques d'arithmétique réelle exacte, deux écrites en Coq et une en PVS. Nous allons présenter les motivations de ces efforts de certification, les algorithmes choisis pour l'implémentation et les applications potentielles. En particulier, nous allons nous concentrer sur la vérification formelle de méthodes numériques. Comme le concept d'arrondi n'intervient pas dans l'arithmétique réelle exacte, on va pouvoir faire des calculs qui prennent en compte seulement les erreurs dues à la méthode.

Analyse statique d'algorithmes numériques

Oratrice : Sylvie Putot (CEA-LIST, équipe MEASI)

PDF de la présentation

Résumé : Cet exposé présentera une méthode d'analyse statique par interprétation abstraite de programmes numériques. Après une courte introduction à l'analyse statique, je montrerai comment nous utilisons une extension de l'arithmétique affine d'intervalles pour calculer des invariants numériques sur des programmes. Il s'agit en particulier de borner la différence, sur des ensembles d'exécutions possibles, entre calcul en arithmétiques exacte et flottante, et d'identifier les sources d'erreurs. Des exemples seront présentés, démontrant que cette analyse, implémentée dans l'outil Fluctuat, permet de borner finement l'erreur due aux arrondis et à leur propagation dans des expressions arithmétiques. Dans un second temps, nous montrerons qu'elle permet d'analyser plus généralement le bon comportement (ou non) d'un programme numérique, par exemple en détectant des éventuelles divergences de branchement entre calcul flottant et erreur (avec comme conséquence par exemple la convergence d'un algorithme itératif en nombres réels et non en nombres flottants) ou en prouvant leur absence.

Session Calcul formel

Arithmétique moderne

Orateur : Paul Zimmermann (INRIA, équipe-projet CACAO)

PDF de la présentation

Résumé : Nous présentons les principaux algorithmes permettant de calculer sur des entiers et flottants en précision arbitraire. La plupart de ces algorithmes sont dérivés d'algorithmes similaires sur les polynômes, la différence principale étant la gestion des retenues. Cet exposé est basé sur le livre Modern Computer Arithmetic.

Arithmétique rapide dans les tours d'Artin-Schreier

Orateur : Luca De Feo (INRIA et École Polytechnique)

PDF de la présentation

Résumé : Soit K un corps de caractéristique p, une extension d'Artin-Schreier est une extension de corps engendrée par un polynôme de la forme Xp − X − a. Toute extension séparable de degré p peut être exprimée comme une extension d'Artin-Schreier, en particulier toute extension de degré p sur un corps fini. Les tours d'Artin-Schreier apparaissent naturellement en théorie des nombres, par exemple dans le calcul des points de p-torsion d'une variété abélienne. On présente ici des algorithmes asymptotiquement rapides pour les opérations arithmétiques de base dans les tours d'Artin-Schreier et pour certaines opérations avancées tel le calcul du morphisme de Frobenius ou des traces. Travail en collaboration avec Éric Schost.

Réduction modulaire simultanée et substitution de Kronecker pour les petits corps finis

Orateur : Laurent Fousse (CASYS, LJK, Univ. J. Fourier, Grenoble)

PDF de la présentation

Résumé : Je présenterai des algorithmes pour réaliser efficacement des multiplications polynomiales modulaires ou des produits scalaires dans un seul mot machine. Les polynômes sont représentés en associant plusieurs coefficients dans un seul entier (par substitution de Kronecker) que l'on manipule avec l'arithmétique machine (entière ou flottante). En respectant certaines bornes sur le degré et la taille des coefficients que j'expliciterai, il est possible d'utiliser l'arithmétique machine directement et de réduire le nombre de conversions. J'expliquerai aussi comment extraire rapidement les valeurs des coefficients. Ces techniques conduisent à des gains d'un facteur constant substantiel pour la multiplication polynomiale, l'algèbre linéaire des corps premiers et l'arithmétique des corps finis de petit degré. Il s'agit d'un travail en collaboration avec Jean-Guillaume Dumas et Bruno Salvy.

Développement en séries de Tchebychev pour les solutions d'équations différentielles à coefficients polynomiaux

Orateur : Alexandre Benoit (INRIA-MSR, équipe-projet Algorithms)

PDF de la présentation

Résumé : Il est bien connu que les développements en série de Taylor de fonctions solutions d'équations différentielles linéaires à coefficients polynomiaux (ou D-finies) ont des coefficients qui vérifient une récurrence linéaire. La même propriété est vérifiée par les coefficients des développements de ces fonctions en série de Tchebychev (c'est-à-dire sur la base des polynômes de Tchebychev). Ces développements possèdent des propriétés intéressantes du point de vue de l'approximation, ce qui motive leur étude et la recherche d'algorithmes efficaces pour leur calcul. Alors que de tels algorithmes sont classiques dans le cas des séries de Taylor, les méthodes connues pour les séries de Tchebychev n'avaient pas été étudiées du point de vue de la complexité. Je montrerai une représentation des relations de récurrence vérifiées par les coefficients de séries de Tchebychev comme les numérateurs de fractions d'opérateurs de récurrence. Grâce à cette interprétation je montrerai une représentation unifiée des algorithmes existants, je comparerai leurs complexités, et je montrerai un nouvel algorithme plus rapide.