Projet Arénaire - Réunions d'équipe

Eleonora Guerrini (LIP)

Jeudi 9 février 10h15-11h15 en salle 117 :

Une caractérisation algébrique pour les codes correcteurs systématiques

Dans cet exposé un modèle algébrique pour la caractérisation des codes correcteurs systématiques est présentée. L'intérêt pour cette famille dérive de la volonté de généraliser les codes linéaires afin de rechercher des codes qui soient optimaux du point de vue de la distance. En fait, il est possible démontrer que tout code linéaire est équivalent à un code systématique, mais il existe des codes systématiques non-linéaires à distance plus grande de tout linéaire qui partage les mêmes paramètres n (longueur) k (dimension). A la base de cette approche, le fait que tout code systématique est en correspondance avec la base de Groebner réduites de son idéal d'annulation. Grâce à cette correspondance, nous décrivons un algorithme qui, étant donnés n,k,d entiers, fournit la car- actérisation des codes systématiques avec paramètres n,k et distance au moins d. Le point central de l'algorithme est le calcul de la base de Groebner d'un certain idéal B(n,k,t) qui est invariant sous l'action d'un groupe de permuta- tions et présente de propriétés d'inclusions dans d'autres idéaux du même type (par ex. dans B(n+1,k,t+1) et B(n+1,k+1,t)). Avec des techniques similaires, il est possible aussi de formuler un algorithme pour le calcul de la distribution des distances d'un code systématique et une nouvelle borne pour la distance de ces codes.

2011-2012

Eleonora Guerrini (LIP)

Jeudi 9 février 10h15-11h15 en salle 117 :

Une caractérisation algébrique pour les codes correcteurs systématiques

Philippe Langlois (DALI/LIRMM, Univ. Perpignan)

Jeudi 2 février 10h15-11h15 en salle 117 :

Sur les algorithmes de sommation précise ou correcte et leurs
performances réelles

Résumé: Il est fascinant qu'un problème a priori aussi simple que calculer la somme de N nombres flottants soit l'objet d'autant d'algorithmes. L'enjeu est (au moins) double : être précis tout en étant rapide. En matière de précision de la somme calculée, on distingue les algorithmes inverses stables, ceux qui améliorent la précision obtenue mais qui continuent à dépendre du conditionnement (simulation d'une précision arbitraire de calcul) et enfin ceux qui calculent (presque toujours) le meilleur résultat possible. Des publications récentes proposent plusieurs exemples de cette dernière catégorie -- qui correspond en quelque sorte au Graal en la matière. La meilleure précision étant atteinte, la rapidité devient discriminante. Nous nous intéresserons à cet aspect. Nous expliciterons pourquoi les résultats publiés et visant à "prouver que mon algorithme est plus rapide que les précédents" ne sont pas entièrement satisfaisants. Nous présenterons des pistes, des outils et des résultats permettant une meilleure appréciation du réel potentiel de performance de ces algorithmes précis.

Florent de Dinechin (LIP)

Jeudi 26 janvier 10h15-11h15 en salle 115 (attention: ce n'est pas la salle habituelle) :

All you ever wanted to know about division by 3 (for various values of 3)

Quite often, application-specific architectures have to divide by a small constant, for example when computing a running average over a window of size 3 or 9, or for binary/decimal conversion. There has been a lot of research on multiplication by a constant, and of course these works can be also be applied to division by a constant. We will present two original methods specific to division by a small constant.

The first observes that a constant like 1/3 is periodic, and tries to exploit it systematically in several classical constant multiplication techniques. This can be generalized to multiplication by arbitrary rational constants.

The second is based on the classical division iteration, which when the constant is small can be implemented as a small look-up table. This is a perfect match for the fine structure of an FPGA. In both case we will present architectures for integer and floating-point implemented in FloPoCo. For floating-point, we will also show that correct rounding to the nearest, for the two algorithms, is for free.

Valérie Berthé (CNRS/Liafa)

Jeudi 12 janvier 10h15-11h15 en salle 117 :

Title: Droites discrètes et calculs de pgcd : une vision dynamique

Abstract: Cet exposé est motivé par la question de la construction effective d'approximations de droites discrètes dans l'espace. Nous présentons un mode de construction qui repose sur des algorithmes unimodulaires de calcul de pgcd. Parmi ces derniers, on peut trouver des méthodes définies à partir d'algorithmes de réduction dans les réseaux, ou encore d'algorithmes type Euclide qui permettent d'approcher une direction par des suites de cônes emboîtés engendrés par les colonnes de matrices unimodulaires à entrées entières. Nous allons considérer plus particulièrement ces dernières méthodes et les systèmes dynamiques associés, afin de tenter de les comparer.

Sylvie Boldo (INRIA/Proval et LRI)

Jeudi 5 janvier 10h15-11h15 en salle 117 :

Title: Preuve de programmes d'analyse numérique

Abstract: Cet exposé montrera les résultats du projet FOST: nous avons formellement prouvé un programme C implémentant un schéma numérique simple pour la résolution de l'équation des ondes acoustiques en dimension 1. Nous avons annoté ce programme et l'avons complètement prouvé. Cela inclut l'absence d'erreur à l'exécution, la majoration mathématique usuelle de l'erreur de méthode due au schéma numérique et bien sûr une borne sur les erreurs d'arrondi.

Jingyan Jourdan-Lu (LIP/Arénaire et STMicroelectronics)

Jeudi 15 décembre 10h15-11h15 en salle 117 :

Title: Software for squaring floats on ST231: a case study in bringing floating-point to VLIW integer processors

Abstract: In this talk we will consider the problem of computing IEEE floating-point squares by means of integer arithmetic. We will show how the specific properties of squaring can be exploited in order to design and implement algorithms that have much lower latency than those for general multiplication, while still guaranteeing correct rounding.
Our algorithm descriptions are parameterized by the floating-point format, aim at high instruction-level parallelism (ILP) exposure, and cover all rounding modes.
We will show further that their C implementation for the binary32 format yields efficient codes for targets like the ST231 VLIW integer processor from STMicroelectronics, with a latency at least 1.75x smaller than that of general multiplication in the same context. We will conclude by examining the impact of such special operators on some FFT-related floating-point applications. The speedup is around 1.28x to 1.46x.

Key words: squaring, binary floating-point arithmetic, correct rounding, IEEE 754, instruction level parallelism, C software implementation, VLIW integer processor.

Sylvain Collange

Jeudi 8 décembre 10h15-11h15 en salle 117 :

Title: Single-Instruction, Single-Data, Multiple-Thread: how to kill 32 birds with one stone.

Abstract: Parallel applications running on GPUs are made of thousands of fine-grained threads that run in parallel. We show that control-flow, computations and memory accesses are highly correlated between threads: neighbor threads often perform similar computations on close values.
This effect can be leveraged in many ways to improve the energy efficiency of parallel architectures, thanks to hardware mechanisms such as SIMD execution, memory access coalescing, instruction sharing, cache and memory compression.
In particular, we will examine how execution units and memory access units can be optimized when the high-order bits or the floating-point exponents of their parallel inputs are the same.

Christoph Lauter (LIP6, équipe Péquan)

Jeudi 1er décembre 10h15-11h15 en salle 117 :

Title: Arrondis fidèle et correct de la norme L2 d'un vecteur de longueur n (travail commun avec S. Graillat, S. Oishi et N. Yamanaka)

Abstract:

En partant des travaux présentés par Brisebarre et al. à ARITH 20 sur l'arrondi correct de la norme de vecteurs de longueur 2, nous allons analyser la faisabilité d'un arrondi fidèle, voire correct, de la norme L2 de vecteurs de flottants de longueur n. Il est évident qu'à cause de la longueur variable du vecteur, ces travaux ne peuvent pas se baser sur une recherche de pires cas mais doivent exploiter le caractère algébrique de la fonction "norme".

Une analyse montre que la racine carrée correctement arrondie
* de l'arrondi correct de sum x_i^2 donnerait un arrondi fidèle de la norme
* et que celle d'un arrondi fidèle de sum x_i^2 ne donne pas d'arrondi fidèle de la norme.
Pourtant, il n'est pas nécessaire d'extraire la racine carré d'une approximation de sum x_i^2 en double-double pour obtenir un arrondi fidèle de la norme. La somme intermédiaire d'un algorithme de sommation compensé peut être arrondie à un seul flottant avant l'extraction de la racine carrée.

Cette analyse permet alors de présenter plusieurs algorithmes de calcul de la somme sum x_i^2 adaptés au problème de la norme. Ces algorithmes compensés se comportent plus ou moins bien sur les processeurs pipelinés et parallels actuels, ce que nous investiguons.

L'arrondi fidèle forme la base pour l'arrondi correct de la norme d'un vecteur. On montre qu'un algorithme naïf peut être obtenu facilement par une simple composition d'algorithmes de sommation connus. Cet algorithme serait pourtant très inefficace: il nécessiterait jusqu'à trois parcours de la somme des x_i^2, rendue cancellante par un rajout de l'opposé du carré de l'arrondi fidèle de la norme.

Pour réduire ce nombre de parcours, on présente une modification du test d'arrondi de Ziv, utilisé traditionnellement pour les fonctions élémentaires. Le test modifié décide non seulement si l'arrondi correct est déjà possible, mais calcule aussi le milieu des deux flottants autour duquel l'arrondi change. Ainsi, il sera possible de réduire le nombre des parcours de la somme à un seul dans la plupart des cas et à deux dans les quelques cas difficiles à arrondir.

Marc Mezzarobba (LIP/Arénaire)

Jeudi 24 novembre 10h15-11h15 en salle 117 :

Title: Autour de l'évaluation numérique des fonctions D-finies

Abstract: Je proposerai une synthèse de mes travaux de thèse, qui ont comme thème commun l'évaluation numérique des fonctions dites D-finies. Les fonctions D-finies sont les solutions d'équations différentielles linéaires à coefficients polynomiaux. Il s'agit de développer des outils pour leur évaluation (et divers problèmes apparentés) qui travaillent à partir d'une équation différentielle accompagnée d'un jeu convenable de conditions initiales.
Le leitmotiv est de proposer des méthodes à la fois générales (couvrant autant que possible toutes les fonctions D-finies), garanties (bornes d'erreur rigoureuse) et efficaces (tant en pratique que du point de vue de la complexité). Les travaux présentés explorent trois principales directions.

1. Le calcul de *majorants fins* sur les suites solutions de récurrences linéaires à coefficients polynomiaux, qui comprennent comme cas particulier les développements en série entière de fonctions D-finies. Les bornes obtenues interviennent à de multiples reprises pour garantir la précision des calculs numériques.

2. La mise en pratique d'un algorithme de *prolongement analytique numérique* à grande précision, proposé par Chudnovsky et Chudnovsky à la fin des années 1980 puis étendu par van der Hoeven. Sans être le plus rapide à petite précision, cet algorithme sert de base à une approche efficace et garantie pour évaluer une fonction D-finie quelconque en n'importe quel point de son domaine de définition et à des précisions pouvant atteindre des millions de chiffres décimaux.

3. Le calcul de *polynômes d'approximation*. La question est ici d'obtenir à faible coût un polynôme de degré imposé qui approche bien une fonction D-finie donnée, au sens de la norme uniforme sur un segment, ainsi qu'une borne sur l'erreur d'approximation. De tels polynômes sont utiles, par exemple, pour évaluer la fonction à précision modérée en plusieurs points du segment.

En ce qui concerne les deux premiers points, on s'attache à couvrir le cas des points singuliers réguliers des équations différentielles. La plupart des algorithmes en jeu sont implémentés, notamment dans le module Maple NumGfun présenté au groupe de travail Arénaire fin 2010. Certains de ces travaux ont été menés en collaboration avec Alexandre
Benoit, Mioara Joldeş ou Bruno Salvy.

Nicolas Brunie (LIP/Arénaire et Kalray)

Jeudi 17 novembre 10h15-11h15 en salle 117 :

Title: Deep integration of reconfigurable fabrics

Abstract: FPGAs have triggered a great interest for reconfigurable computing. However their integration into complete systems often appears as the new bottleneck. To overcome this difficulty, deeply integrated reconfigurable fabrics have been proposed. Such fabrics are located closer to the CPU than external FPGAs, and can use it for control and memory access purposes.
Our work focuses on a massively parallel architecture and proposes a new reconfigurable architecture for high performance dataflow-oriented computing on this platform.
We will study the system (work in progress) with the low-level compilation framework, the reconfigurable structure and its application to the Advanced Encryption Standard, focusing on the arithmetic specificities of the reconfigurable fabric needed to efficiently support this cryptographic application.

Markus Püschel (ETH Zürich)

Vendredi 4 novembre 10h15-11h15 en salle 116 :

Spiral: Can We Teach Computers to Write Fast Libraries?

Writing fast software has become extraordinarily difficult. For optimal performance, programs and their underlying algorithms have to be adapted to take full advantage of the platform’s parallelism, memory hierarchy, and available instruction set. To make things worse, the best implementations are often platform-dependent and platforms are constantly evolving, which quickly renders libraries obsolete.

In this talk we present Spiral (www.spiral.net), a domain-specific program generation system for important functionality used in signal processing, communication, and scientific computing including linear transforms and filters, Viterbi decoders, and basic linear algebra routines. Spiral completely replaces the human programmer. For a desired function, Spiral generates alternative algorithms, optimizes them, compiles them into programs, and “intelligently” searches for the best match to the computing platform. The main idea behind Spiral is a mathematical, declarative, domain-specific framework to represent algorithms and the use of rewriting systems to generate and optimize algorithms at a high level of abstraction. Optimization includes parallelization for vector architectures, shared and distributed memory platforms, and even FPGAs. Experimental results show that the code generated by Spiral competes with, and sometimes outperforms, the best available human-written code. Spiral has been used to generate part of Intel’s commercial libraries IPP and MKL.

Laurent-Stéphane Didier (LIP6, en CRCT au sein d'Arénaire)

Jeudi 20 octobre 10h15-11h15 en salle 117 :

Estimation d'intervalles dynamiques par méthodes statistiques

En pratique, les concepteurs d'applications embarquées construisent leurs modèles numériques, les testent et les simulent en virgule flottante. Ils les portent ensuite sur les architectures qu'ils ciblent. Il s'agit généralement de matériels n'ayant pas d'unité flottante. Dans ce contexte, la représentation la plus adaptée est la virgule fixe. Afin de correctement dimensionner la représentation à virgule fixe utilisée, deux étapes sont nécessaires. La première consiste à déterminer les intervalles dynamiques dans lequels vont
évoluer les variables, la seconde la précision avec laquelle on peut effectuer les calculs. Dans ce travail, les concepteurs d'applications embarquées ont rarement les moyens d'estimer rapidement et simplement ces deux éléments.
Dans cet exposé un modèle statistique pour estimer les intervalles dynamiques de variables est proposé ainsi que quelques exemples pratiques.

Arne Storjohann (University of Waterloo)

Jeudi 13 octobre 10h15-11h15 en salle 117 :

Inverting integer and polynomial matrices

The exact inverse of an integer or polynomial matrix of dimension n can require a factor of n more space to write down than the input matrix. Traditional inversion methods, such as
Chinese remaindering or Newton iteration, cost a factor of n more than this. In this talk I survey three recent improvements in computing and representing the inverse. The first is the double-divide and conquer method of Jeannerod & Villard (2005), the first nearly optimal algorithm in the case of generic polynomial matrices. The second is the sparse inverse expansion formula, which gives a representation as a straight line formula whose size is only a logarithmic factor larger than the input matrix. Finally, I will discuss the outer product adjoint formula, which gives a Las Vegas algorithm to compute the exact inverse of a well conditioned integer matrix in nearly optimial time.

Jean-Michel Muller (CNRS, LIP/Arénaire)

Jeudi 6 octobre 10h15-11h15 en salle 117 :

Some issues related to double roundings

Double rounding is a phenomenon that may occur when different floating-point precisions are available on a same system, or when performing scaled operations whose final result is subnormal. Although double rounding is, in general, innocuous, it may change the behavior of some useful small floating-point algorithms. We analyze the potential influence of double roundings on the Fast2Sum and 2Sum algorithms, and on some summation algorithms. We also show how to handle possible double roundings when performing scaled Newton-Raphson division iterations (to avoid possible underflow problems).

Didier Henrion (LAAS-CNRS, University of Toulouse, France, and Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic)

Mardi 27 septembre 10h15-11h15 en salle 117 :

Polynomial optimisation, LMI and dynamical systems

The first part of the talk surveys achievements of the last decade on polynomial optimisation and semidefinite programming (linear matrix inequalities, LMI) with a focus on the generalised problem of moments and existing software tools. The second part of the talk deals with a recent extension of these techniques to analysis of nonlinear ordinary differential equations and polynomial optimal control.

Jean-François Biasse (University of Calgary).

Jeudi 15 septembre 10h15-11h15 en salle 117 :

Réduction de bases sur un module et application au décodage en liste.

Nous nous intéresserons au calcul d'une pseudo-base d'un R-module de dimension finie. Un tel calcul peut s'effectuer via la mise sous forme pseudo-HNF d'une pseudo-matrice tel que l'a décrit Cohen dans "Advanced topics in computational number theory". Après avoir défini cette généralisation de la forme canonique de Hermite, ainsi que les algorithmes permettant son calcul, nous présenterons un algorithme récent dû à Fieker et Stehlé permettant le calcul de bases réduites. Nous étudierons le lien entre ces algorithmes et le décodage en liste de codes basés sur les corps de nombres. L'encodage de ces codes s'effectue via la réduction du message modulo des idéaux premiers entre eux, de manière analogue à celle des codes basés sur les restes chinois (codes CRT), des codes de Reed-Solomon, ainsi que des codes Algébriques-géométriques. Contrairement à leurs analogues, les codes basés sur les corps de nombres n'étaient jusqu'à présent pas décodable en temps polynomial. Je présenterai un algorithme décrit en collaboration avec Guillaume Quintin permettant de réaliser ce défi.

2010-2011

Xiao-Wen Chang (McGill University).

Mardi 12 juillet 13h30-14h30 en salle 117 :

Lecture 1: Characterizing Matrices That Are Consistent with Given Solutions.

This lecture is about 'backward' problems for linear systems Fy = b. Specifically, given two vectors y and b we want to find the sets of all matrices F such that y is the exact solution, the ordinary least squares (OLS) solution, the data least squares (DLS) solution, and the scaled total least square (STLS) solution. A unified unitary transformation approach to handling these problems will be presented.

Jeudi 21 juillet 10h15-11h15 en salle 117 :

Lecture 2: Backward Perturbation Analysis of Linear Systems .

Give an approximate solution to the linear equations, the OLS problem, the DLS problem and the STLS problem, this lecture gives backward perturbation analyses to find a perturbation in the data of minimal size such that the approximation solution is the exact solution of the corresponding perturbed problems by using the results derived in Lecture 1. The results are useful in two aspects. One is to check if a computed solution is a backward stable solution. The other is to design effective stopping criteria for the iterative solution of large sparse problems.

Jeudi 16 juin 2011 à 10h15 en salle 118 :

Marine Minier (INSA de Lyon, laboratoire CITI).

New LFSRs and FCSRs representations for stream ciphers hardware and software design.

In this talk, we will sum up our recent research results concerning the introduction of a new representation for FCSRs based upon a known LFSRs representation. This matrix based representation allows to construct FCSRs with a more compact hardware representation and a quicker diffusion while preserving the usual and proven good properties (good periods, l-sequences, good statistical behaviors, etc.). Moreover, this new approach circumvents the weaknesses of the Fibonacci and Galois representations. We also show how to extend the LFSRs representation to a particular LFSR case called the windmill case.

LFSRs are well-known primitives used in cryptography especially for stream cipher design. However they have some drawbacks when looking at their resistance against algebraic attacks because of their linearity. In the contrary, FCSRs are inherently resistant to algebraic attacks due to the non-linearity of the update function. Using the new representation, we propose two new stream ciphers based on the so-called "ring" FCSR representation. The first proposal called F-FCSR is dedicated to hardware applications whereas the second proposal called X-FCSR is designed for software purposes but is also efficient in hardware.

Jeudi 9 juin 2011 à 10h15 en salle 118 :

Laurent Fousse (Université Joseph Fourier de Grenoble, équipe CASYS, LJK).

Le chiffrement homomorphe « dense » de Benaloh revu et corrigé.

En 1994, Josh Benaloh a décrit un chiffrement homomorphe probabiliste « dense », qui améliore notablement le facteur d'expansion du chiffrement de Goldwasser et Micali. De nombreux articles ont ensuite utilisé ce chiffrement dans des applications diverses (vote électronique, calcul de confiance dans un réseau, partage de secret non-interactif...). Je montrerai que ce chiffrement, tel qu'il est décrit dans l'article de Benaloh, est en fait incorrect, et certains choix malheureux de clef publique peuvent conduire à un déchiffrement ambiguë. J'illustrerai l'impact de cette erreur sur des applications concrètes, et je donnerai une analyse du problème via le calcul de la probabilité d'apparition de paramètres incorrects; ainsi qu'une version corrigée (et prouvée) du chiffrement.

Il s'agit d'un travail en commun avec Pascal Lafourcade et Mohamed Alnuaimi qui sera présenté à AFRICACRYPT 2011.

Mardi 31 mai 2011, à 15h en salle 117 :

Bruno Salvy (INRIA, EPI Algorithms).

Itération de Newton combinatoire et applications.

De nombreuses familles d'objets discrets définis récursivement peuvent être modélisées par des systèmes d'équations combinatoires. L'itération de Newton s'étend à ce contexte. Elle mène à une méthode d'itération quadratique pour calculer des structures. En conséquence, l'énumération de ces objets peut être effectuée en complexité quasi-optimale. De plus, cette itération se traduit en un schéma numérique important pour la génération aléatoire efficace. L'exposé donnera une introduction à ce domaine et ses idées. Il s'agit d'un travail en commun avec Carine Pivoteau et Michèle Soria.

Jeudi 26 mai 2011 à 10h15 en salle 118 :

Alexandre Kouyoumdjian (Arénaire).

Caches compressés sur GPU .

Les processeurs graphiques (GPU) exécutent des applications massivement parallèles. Ils maintiennent en vol plus de 10000 threads concurrents pour masquer les latences mémoire. Ce parallélisme extrême limite fortement la quantité de données locales dont chaque thread peut disposer, en particulier en ce qui concerne les caches.

On observe cependant que les données temporaires des applications de calcul généraliste sur GPU présentent des motifs réguliers : les vecteurs affines. On peut tirer parti de cette régularité pour compresser les caches des GPU, et ainsi augmenter virtuellement leur capacité. Cela permet de réduire le trafic vers la mémoire externe, améliorant la performance et/ou la consommation d'énergie des GPU.

Jeudi 12 mai 2011 à 10h15 en salle 118 :

San Ling (School of Physical and Mathematical Sciences, Nanyang Technological University, Singapor).

On the Construction of Asymmetric Quantum Error-Correcting Codes.

Quantum error-correcting codes were introduced to protect quantum information from decoherence and quantum noise. Ever since their introduction in the mid 1990's, much progress has been made on their construction. A rather prevalent idea that has proved to be very useful is to construct quantum codes using classical error-correcting block codes.

More recently, it was also established from experiments that, in many quantum systems, phase-flip errors happen more frequently than bit-flip errors. Asymmetric quantum error-correcting codes, which take advantage of this asymmetry, have been introduced as a result (as opposed to the more established symmetric ones which do not distinguish between these two types of errors).

As in the case for classical error-correcting block codes, there are known bounds constraining the parameters of quantum codes. One such bound is the quantum Singleton bound, and the codes whose parameters satisfy this bound are known as maximum distance separable (MDS) quantum codes. An interesting problem is to construct optimal quantum codes, in the sense that codes of better parameters can be proved not to exist. Of course, a code that attains some known bound on the parameters is therefore naturally optimal.

In this talk, we will focus on the construction of optimal asymmetric quantum codes using suitable classical error-correcting block codes, via purely mathematical approaches (i.e., no physics!). In particular, many MDS quantum codes and some other optimal ones are constructed. No pre-requisite knowledge of error-correcting codes will be assumed. Essential ideas and facts in coding theory will be introduced.

Résumé disponible au format pdf.

Jeudi 31 mars 2011 à 10h15 en salle 118 :

Stéphane Gaubert (INRIA et CMAP, École Polytechnique).

Aspects tropicaux des problèmes de valeurs propres: un tour d'horizon

On présentera ici un tour d'horizon de la théorie spectrale max-plus ou ``tropicale'' en dimension finie, en mettant en exergue ses relations avec la théorie spectrale classique. Les valeurs propres tropicales apparaissent en effet quand on s'intéresse à des problèmes de perturbation de valeurs propres, ou bien à des asymptotiques ``à température nulle'' (matrices de transfert). Elles permettent d'obtenir par des algorithmes de nature combinatoire (résolution d'un problème d'affection paramétrique) les ordres de grandeur (valuations de séries de Puiseux) de valeurs propres de matrices ou de faisceaux perturbés. Cette approche permet de résoudre des cas singuliers dans la théorie des perturbations de Lidskii, qui traite de perturbations plus ou moins génériques de blocs de Jordan. On obtient par la même approche des mises à l'échelle (scalings) qui peuvent être mises à profit pour calculer numériquement les valeurs propres de matrices ou de polynômes matriciels, en réduisant l'erreur ``backward'' (on améliore ainsi un scaling proposé par Fan, Lin et Van Dooren). Nous donnerons aussi un aperçu des correspondances entre problèmes spectraux, éventuellement non-linéaires, et problèmes de jeux à somme nulle. Cet exposé s'appuie sur des travaux communs avec Marianne Akian et Ravindra Bapat (pour la partie relative aux perturbations) et avec Meisam Sharify (pour l'application au calcul numérique).

Jeudi 10 mars 2011 à 10h00 en salle 118 :

Dan Bates (Colorado State University)

Adaptive precision and lattice basis reduction in algebraic geometry

There is a growing trend to use numerical (or symbolic-numeric) methods to compute quantities and structures of interest to algebraic geometers. The core computation of this sort is the use of homotopy methods to approximate solutions of polynomial systems. In this talk, I will briefly describe how these methods work (without assuming any prior knowledge of algebraic geometry), including the use of adaptive precision linear algebra and parallel computation. I will also briefly indicate two places where lattice basis reduction methods have an impact in algebraic geometry. I will not make any assumptions about prior knowledge of algebraic geometry or numerical algebraic geometry.

Takeshi Ogita (Tokyo Woman's Christian University)

Robust inverse matrix factorizations

Recently, several algorithms for inverse matrix factorizations have been proposed by the author, which include inverse LU, QR, Cholesky and SVD. In this talk a framework for such algorithms and concrete altorithms are introduced. Numerical results are presented showing the effectiveness of the proposed algorithms.

Jeudi 24 février 2011 à 10h15 en salle 118 :

Xavier Pujol, Arénaire

Analyse de BKZ / Analysis of BKZ

La réduction forte de réseaux est la clé de la plupart des attaques contre les cryptosystèmes basés sur les réseaux. Entre la réduction HKZ, forte mais trop coûteuse, et la réduction LLL, plus faible mais rapide, existent plusieurs tentatives d'obtenir des compromis efficaces. Celle qui semble atteindre le meilleur rapport temps/qualité est la réduction BKZ, introduite par Schnorr et Euchner en 1991. Cependant, aucune borne de complexité raisonnable sur cet algorithme n'était connue jusqu'à maintenant. Nous prouvons qu'après O~(n3/k2) appels à une routine de HKZ-réduction, BKZ_k renvoie une base telle que la norme du premier vecteur est bornée par ~= gamma_k^(n/(2(k-1))) * (det L)^(1/n). Le principal outil de la preuve est l'analyse d'un système dynamique linéaire associé à cet algorithme.

Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner in 1991 seems to achieve the best time/quality compromise in practice. However, no reasonable time complexity upper bound was known so far for BKZ. We give a proof that after O~(n3/k2) calls to a k-dimensional HKZ reduction subroutine, BKZ_k returns a basis such that the norm of the first vector is at most ~= gamma_k^(n/(2(k-1))) * (det L)^(1/n). The main ingredient of the proof is the analysis of a linear dynamic system related to the algorithm.

Jeudi 3 février 2011 à 10h15 en salle 118 :

Martin Langhammer et Steven Perry, Altera

Jeudi 20 janvier 2011 à 10h15 en salle 118 :

Thi Minh Tuyen NGUYEN (INRIA Saclay - Île-de-France, EPI PROVAL).

Hardware-independent proofs of numerical programs

On recent architectures, a numerical program may give different answers depending on the execution hardware and the compilation. Our goal is to formally prove properties about numerical programs that are true for multiple architectures and compilers. We propose an approach that states the rounding error of each floating-point computation whatever the environment and the compiler choices. This approach is implemented in the Frama-C platform for static analysis of C code. A small case study using this approach will be presented.

Mercredi 19 janvier 2011 à 10h15 en salle 118 :

Siegfried M. Rump (Institute for Reliable Computing, Hamburg University of Technology).

Structured perturbations for matrices and pseudospectra

Important structured perturbations of matrices are, for example, symmetric or Toeplitz or circulant perturbations. We show that in many cases the unstructured and strucutred condition number coincide. In particular an extension of the famous Eckart/Young/Gastinel/Kahan Theorem is proved, namely that the reciprocal of the (structured) condition number and the (structured) distance to the nearest singular matrix coincide. This is true for normwise perturbations, but changes completely for componentwise perturbations. In the latter case a problem can be perfectly well-conditioned (condition number one) for structured perturbations, whereas it is arbitrarily sensitive to unstructured perturbations.

Jeudi 13 janvier 2011 à 10h15 en salle 118 :

Fabien Laguillaumie (GREYC, Université de Caen).

NICE : une cryptanalyse imaginaire et une cryptanalyse réelle

NICE est un algorithme de chiffrement basé sur l'arithmétique des corps quadratiques ayant pour principal intérêt son déchiffrement en temps quadratique. Dans cet exposé, nous montrerons les cryptanalyses totales des versions imaginaire et réelle. En particulier, nous présenterons un algorithme original de factorisation des entiers de la forme pq^2 utilisant des résultats classiques sur les formes quadratiques et des techniques de recherche de petites racines de polynômes. Cet algorithme est déterministe et sa complexité, en générale exponentielle, dépend essentiellement du régulateur du corps quadratique de discriminant p. Les systèmes NICE fournissent des données permettant de rendre la complexité de notre algorithme polynomiale sur ces entrées et donc de retrouver la clé secrète en quelques secondes sur un PC standard.

Travail en commun avec G. Castagnos, A. Joux et P. Nguyen

Jeudi 6 janvier 2011 à 10h15 en salle 118 :

Nicolas Estibals (CARAMEL, LORIA).

Accélérateur matériel compact pour le calcul du couplage de Tate sur des courbes supersingulières de 128 bits de sécurité

Les couplages interviennent dans des protocoles cryptographiques de plus en plus nombreux tel que le chiffrement basé sur l'identité ou la signature courte. Dès lors, fournir une implémentation efficace des couplages cryptographique pour un grand nombre de supports, et plus spécialement les systèmes embarqués, devient un chalenge intéressant.

Nous présentons une nouvel méthode pour concevoir des accélérateurs matériels compacts pour le cacul du couplage de Tate sur des courbes supersingulières de petite caractéristique. Du fait de leur degré de plongement (embedding degree) limité, ces courbes ne sont généralement pas utilisées pour atteindre la sécurité standard de 128 bits. En effet, la taille du corps fini de définition d'une courbe à ce niveau de sécurité est très grande. Afin de palier cet effet, nous considérons des courbes supersingulières définies sur des corps finis de de degré d'extension modérément composé (F_p^nm avec n «petit» et m premier). Ces courbes deviennent alors vulnérables aux attaques basées sur la descente de Weil mais une analyse fine de celles-ci nous permet de montrer que leur impact reste limité et que nous pouvons maintenir la sécurité au-dessus de 128 bits.

Nous appliquons alors cette méthode à une courbe supersingulière définie sur F_3^5.97 et décrivons ainsi une implémentation FPGA d'un accélérateur pour le calcul de couplage à 128 bits de sécurité. Sur FPGA de gamme moyenne (Xilinx Virtex-4 FPGA), cet accélérateur cacule le couplage en 2.2 ms sur une surface limitée à 4755 slices.

Jeudi 16 décembre 2010 à 10h15 en salle 118 :

Ioana Pasca (Arénaire, LIP).

Vérification formelle pour les méthodes numériques.

Dans cet exposé, je présenterai les principales contributions de ma thèse, préparée sous la direction d'Yves Bertot au sein du projet Marelle de l'INRIA Sophia Antipolis, et soutenue le 23 novembre 2010.

Cette thèse s'articule autour de la formalisation de mathématiques dans l'assistant à la preuve Coq dans le but de vérifier des méthodes numériques. Plus précisément, elle se concentre sur la formalisation de concepts qui apparaissent dans la résolution des systèmes d'équations linéaires et non-linéaires.

Dans ce cadre, on a analysé la méthode de Newton, couramment utilisée pour approcher les solutions d'une équation ou d'un système d'équations. Le but a été de formaliser le théorème de Kantorovitch qui montre la convergence de la méthode de Newton vers une solution, l'unicité de la solution dans un voisinage, la vitesse de convergence et la stabilité locale de la méthode. L'étude de ce théorème a nécessité la formalisation de concepts d'analyse multivariée. En se basant sur ces résultats classiques sur la méthode de Newton, on a montré qu'arrondir à chaque étape préserve la convergence de la méthode, avec une corrélation bien déterminée entre la précision des données d'entrée et celle du résultat. Dans un travail commun avec Nicolas Julien nous avons aussi formellement étudié les calculs avec la méthode de Newton effectués dans le cadre d'une bibliothèque d'arithmétique réelle exacte.

Pour les systèmes linéaires d'équations, on s'est intéressé aux systèmes qui ont une matrice associée à coefficients intervalles. Pour résoudre de tels systèmes, un problème important qui se pose est de savoir si la matrice associée est régulière. On a fourni la vérification formelle d'une collection de critères de régularité pour les matrices d'intervalles.

Voir aussi le lien vers le manuscript.

Jeudi 9 décembre à 10h15 en salle 118 :

Alexandre Benoit et Marc Mezzarobba (Algorithms, INRIA Rocquencourt).

Generalized Fourier Series for Solutions of Linear Differential Equations (A. Benoit)

Chebyshev polynomials, Hermite polynomials, Bessel functions and other families of special functions each form a basis of some Hilbert space. A Generalized Fourier Series is a series expansion in one of these bases, for instance a Chebyshev series. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a general algorithm for computing this recurrence, and a simple view of existing algorithms for several specific function families.

Joint work with Bruno Salvy.

NumGfun : calculs numériques et analytiques sur les fonctions D-finies (M. Mezzarobba)

L'objet de cet exposé est de présenter NumGfun, un module Maple consacré à la manipulation « analytique » des solutions d'équations différentielles linéaires à coefficients polynomiaux (fonctions dites D-finies ou holonomes). Les principales fonctionnalités de NumGfun concernent l'évaluation numérique des fonctions D-finies, et le calcul symbolique de bornes « asymptotiquement fines » qui permettent de contrôler leur comportement. En particulier, NumGfun contient ce qui semble être la seule implémentation générale des algorithmes de prolongement analytique numérique des fonctions D-finies donnés par D.V. et G.V. Chudnovsky à la fin des années 1980. Je ferai une démonstration de l'utilisation de NumGfun, et je renviendrai sur quelques-uns des algorithmes sur lesquels il s'appuie, notamment pour assurer la connexion numérique entre points ordinaires et points singuliers réguliers des équations différentielles.

Jeudi 2 décembre 2010 à 10h15 en salle 118 :

Romain Cosset (CARAMEL, LORIA).

Calcul d'isogénies entre courbes de genre 2

Les isogénies sont un outil très important pour la cryptographie basée sur les courbes. Elles permettent, entre autre, de transférer le calcul du logarithme discret vers un groupe où il est plus facile. Les formules de Vélu permettent de les calculer pour les courbes de genre 1. Dans cet exposé, je décrirai un algorithme permettant de les calculer entre n'importe quelle variété abélienne et en particulier entre les jacobiennes de courbes hyperelliptiques de genre 2.

Ceci est un travail commun avec Gaëtan Bisson, David Lubicz et Damien Robert.

Jeudi 25 novembre 2010 à 10h15 en salle 118 :

David Monniaux (CNRS).

On using sums-of-squares for exact computations without strict feasibility.

In order to prove that a system of real polynomial inequalities has no solution, the usual method is to compute a cylindrical algebraic decomposition (CAD) of that system, which yields a false/true answer - for instance, using Mathematica's Reduce function. CAD implementations, especially those that implement optimizations necessary to go beyond toy examples, are notoriously complex and trusting such a massive amount of code for applications such as proving mathematical theorems or proving safety-critical programs is methodologically disputable.

Instead of trusting a complex implementation, or building a certified version thereof, we would prefer the complex algorithm produces an easily checkable "witness" of its answer. For systems of polynomials inequalities, the Positivstellensatz theorems ensure the existence of witnesses made of sums of squares of polynomials. As a particular case, a nonnegative polynomial can often be expressed as a sum of squares of polynomials, and can always be expressed as a quotient of sums of squares of polynomials.

Such sums of squares are solutions of a semidefinite programming feasibility problem (that is, given F_0, ..., F_n symmetric matrices, finding y_i such that -F_0 + \sum_i y_i F_i is semidefinite positive, that is, has no negative eigenvalues). Unfortunately, direct application of semidefinite programming numerical methods is only possible if the solution set has nonempty interior. This is not the case in general.

We propose a workaround for this problem, based on LLL lattice reduction.

Jeudi 18 novembre, à 10h15 en salle 118.

Guillaume Melquiond (INRIA, EPI Proval, LRI).

Flocq: A Unified Library for Proving Floating-point Algorithms in Coq.

Several formalizations of floating-point arithmetic have been designed for the Coq system, a generic proof assistant. Their different purposes have favored some specific applications: program verification, high-level properties, automation. Based on our experience using and/or developing these libraries, Sylvie Boldo and I have built a new system that is meant to encompass the other ones in a unified framework. It offers a multi-radix and multi-precision formalization for various floating- and fixed-point formats. This fresh setting has been the occasion for reevaluating known properties and generalizing them. This talk will present the Flocq system: a library easy to use, suitable for automation yet high-level and generic.

Vendredi 8 octobre 2010 à 10h15 en salle 117 :

Peter Kornerup (SDU/Odense University).

Floating Point Arithmetic on Round-to-Nearest Representations.

Joint work with Jean-Michel Muller and Adrien Panhaleux

During any composite computation there is a constant need for rounding intermediate results before they can participate in further processing. Recently a class of number representations denoted RN-Codings were introduced, allowing an un-biased rounding-to-nearest to take place by a simple truncation. In this paper we investigate a particular encoding of the binary representation which is essentially an ordinary 2's complement representation with an appended round-bit, allowing rounding to nearest by truncation. Not only is this round-to-nearest a constant time operation, so is also sign inversion, both of which are at best log-time operations on ordinary 2's complement representations. A significant benefit of this representation is that problems with ``double-roundings'' are avoided, i.e., the effect of two (or more) subsequent roundings is identical to a single rounding to the final precision. Addition and multiplication on such fixed-point representations are defined in such a way that rounding information can be carried along in a meaningful way, at minimal cost. Based on the fixed-point encoding we define a floating point representation, and describe details of a possible implementation of a floating point arithmetic unit employing this representation.

Jeudi 23 septembre 2010 à 10h15 en salle 118 :

Pascal Molin (IMB - Université Bordeaux 1 ).

Intégration numérique rapide et prouvée par les fonctions à décroissance doublement exponentielle.

La méthode d'intégration numérique dite double-exponentielle est une méthode de quadrature extrêmement efficace, utilisée dans la plupart des logiciels (Maple, Mathematica, sage... mais surtout PARI/gp). On présentera brièvement une théorie de cette méthode et des résultats de convergence prouvée qui la rendent pertinente en théorie des nombres, en particulier comme algorithme sous-jacent au calcul de certaines fonctions définies par des intégrales. On essaiera surtout de donner une intuition du champ d'application et de ses limites, et diverses techniques d'amélioration de la convergence.

Jeudi 16 septembre 2010 à 10h15 en salle 116 :

Vadim Lyubashevsky (Foundations of Computing group at Tel-Aviv University).

Public-Key Cryptographic Primitives Provably as Secure as Subset Sum.

Building a provably-secure public key cryptosystem based on the hardness of the subset sum problem has been an intriguing problem since the late 1970's. In this work, we give a very simple construction of such a scheme. In addition to the simplicity of the construction and the security proof, the hardness assumption of our scheme is weaker than that of all other existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). This is joint work with Adriana Palacio and Gil Segev that appeared at the Theory of Cryptography Conference (TCC) 2010.

2009-2010

Jeudi 17 juin 2010 à 10h15 :

Pascal Giorgi (Université de Montpellier 2, LIRMM, ARITH).

On Polynomial Multiplication using Chebyshev basis.

In this talk, we will present a novel method to handle the multiplication of polynomials represented in the Chebyshev basis. The main concern of this work is to reduce the complexity of polynomial multiplication using Chebyshev basis to the one of the polynomial multiplication in monomial basis. Another point of this work is to see practical benefit of such reduction to achieve better performances.

Jeudi 10 juin 2010 à 10h15, en salle 118 :

Jean-Michel Muller (CNRS, LIP, Arénaire).

Quelques aspects de la conversion décimal-binaire en virgule flottante.

On s'intéresse à la conversion d'un format virgule flottante binaire vers un format décimal (et réciproquement), avec deux buts différents: soit la conversion pour elle même (correctement arrondie), soit pour implanter une fonction en décimal en faisant appel aux programmes en arithmétique binaire. Ceci demande à examiner différents problèmes: "midpoints" (nombres d'un format qui sont le milieu exact de deux nombres consécutifs de l'autre format), valeurs "difficiles à arrondir", etc. On propose également un algorithme rapide de conversion nécessitant la disponibilité d'une instruction de type "fused multiply and add".

Jeudi 3 juin 2010 à 10h30, en salle 118 :

Andrew Novocin (INRIA, LIP, Arénaire).

State of the art univariate polynomial factorization.

This talk presents some recent and on-going work on factoring polynomials in Z[x]. The goal of this work is to arrive at a practical, implementable, and efficient algorithm for which we can prove a tight complexity bound (which should be the best existing complexity bound). We give the overall structure of our algorithm with insights into the practical and theoretical issues which guide the design. We also present the behavior of the algorithm in theory and give some early running times of our implementation.

Jeudi 6 mai 2010 à 10h15, en salle 118 :

Alfredo Buttari (CNRS, IRIT, Toulouse).

Mixed Precision Iterative Refinement Techniques for the Solution of Linear Systems.

On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. The approach presented here can apply not only to conventional processors but also to other technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the STI Cell BE processor. Results on modern processor architectures and the STI Cell BE are presented.

Vendredi 30 avril 2010 à 14h, en salle 118 :

Friedrich Eisenbrand (EPFL, Lausanne).

Diophantine Approximation and Real-time Scheduling.

Real-Time Scheduling problems deal mostly with the arrangements of periodic tasks on machines such that all deadlines of the periodically released jobs are respected. The area is of increasing importance since many safety and liveness critical control mechanisms are replaced by software-driven systems that are based on principles from Real-Time scheduling. In this talk I will address the similarities of some problems in Real-Time scheduling and Diophantine approximation. I will outline how this similarity could be exploited to provide proofs of longstanding open complexity problems in the area of Real-Time Scheduling.

The talk is based on joint work with Thomas Rothvoss.

Jeudi 8 avril 2010 à 10h15, en salle 118 :

Hadi Parandeh Afshar (Processor Architecture Laboratory, EPFL, Lausanne).

Reducing the Existing Gap Between FPGAs and ASICs in Arithmetic Oriented Circuits.

Due to high non-recurring engineering costs, Application Specific Integrated Circuits (ASICs) are not economically feasible for low-volume product lines. Moreover, long time to market in ASIC designs makes them less attractive for fast growing and ever-changing products. One potential alternative for ASIC is Field Programmable Gate Array (FPGA). FPGAs offer many advantages including reduced non-recurring engineering and shorter time to market. However, these advantages come at the cost of a decrease in performance, an increase in silicon area, and an increase in power consumption when designs are implemented on FPGAs. This talk will summarize some of our contributions in reducing the mentioned gaps for arithmetic oriented circuits. My presentation will have two parts. First, I will discuss a new synthesis method targeting FPGAs as they exist today. Then, I will present a number of FPGA architectural improvements including a new FPGA logic block with carry chains that are specialized for carry-save arithmetic and a new DSP block specialized for the same purpose.

Biography: Hadi P. Afshar received the B.S., M.S. degrees in Computer Engineering and Computer Architecture from University of Tehran in 2001 and 2004, respectively. Since 2007, he has been a doctoral scholar with the Processor Architecture Laboratory (LAP) at the Ecole Polytechnique Federale de Lausanne (EPFL), one of the two Swiss Federal Institutes of Technology. His research interests span a number of fields, including: reconfigurable computing, application-specific processors and their design tools, computer arithmetic and computer architecture. He was the recipient of the best paper award at the International Conference on Field Programmable Logic and Applications (FPL), 2009.

Jeudi 25 mars 2010 à 10h30, en salle 118 :

Clément Pernet (Laboratoire LIG lab, projet INRIA-MOAIS, Université Joseph Fourier).

Décodage adaptatif pour les systèmes multimodulaires redondants.

Dans le contexte de calcul distribué sur ressources non-sûres (architectures de calcul globales, pair à pair, ...), des noeuds de calculs malicieux peuvent engendrer des erreurs de type byzantine qu'il faut être capable de détecter et corriger pour assurer la sécurité et la fiabilité d'un calcul par des algorithmes tolérants aux pannes (ABFT: algorithm based fault tolerance).

Dans le domaine du calculs exact (dans les anneaux des entiers ou de polynômes à coefficients dans un corps), la parallélisation repose fortement sur l'algorithme des restes chinois où chaque calcul modulaire est une tâche indépendante. En ajoutant quelques calculs modulaires supplémentaires, les codes arithmétiques introduisent une redondance permettant de reconstruire le résultat, malgré des erreurs non localisées dans certains des calculs modulaires. Ces codes peuvent être présentés de manière unifiée pour les systèmes de résidus redondants sur les polynômes et les entiers, et généralisant les codes de Reed-Solomon.

Nous présenterons plusieurs variantes de l'application de l'algorithme d'Euclide étendu, rendant le taux de correction adaptatif. Différents critères de terminaison permettent l'utilisation de ces codes sans connaissance à priori de leur paramètres et par conséquent de décoder au mieux avec la redondance disponible. Ils permettent en outre de combiner la tolérance aux pannes avec les approches de terminaison anticipée.

Jeudi 11 mars 2010 à 10h30, en salle 118 :

Mioara Joldes (Arénaire, LIP).

Chebyshev Interpolation Polynomial-based Tools for Rigorous Computing

Performing numerical computations, yet being able to provide rigorous mathematical statements about the obtained result, is required in many domains like global optimization, ODE solving or integration. Taylor models, which associate to a function a pair made of a Taylor approximation polynomial and a rigorous remainder bound, are a widely used rigorous computation tool. This approach benefits from the advantages of numerical methods, but also gives the ability to make reliable statements about the approximated function.

A natural idea is to try to replace Taylor polynomials with better approximations such as minimax approximation, Chebyshev truncated series or interpolation polynomials. Despite their features, an analogous to Taylor models, based on such polynomials, has not been yet well-established in the field of validated numerics. In this talk we propose two approaches for computing such models based on interpolation polynomials at Chebyshev nodes.

We compare the quality of the obtained remainders and the performance of the approaches to the ones provided by Taylor models. We also present two practical examples where this tool can be used: supremum norm computation of approximation errors and rigorous quadrature.

This talk is based on a joint work with N. Brisebarre.

Jeudi 4 mars 2010 à 10h30, en salle 118 :

Jordan Ninin (IRIT, Toulouse).

Technique de reformulation affine appliquée à l'optimisation globale.

Les algorithmes de branch and bound par intervalles ont réalisé d'énormes progrès depuis ces trente dernières années, en montrant notamment leur efficacité à résoudre, de manière exacte et robuste, des problèmes d'optimisation globale non-convexes en dimensionnement de machines électriques.

Notre technique de reformulation affine (ART) est une méthode de relaxation linéaire applicable à n'importe quel problème non-convexe (dont les expressions sont explicites); ART génère, de manière robuste, un problème linéaire de petite taille sans aucune variable ajoutée.

De nombreux tests viennent confirmer notre approche, ainsi qu'une comparaison avec l'algorithme GlobSol de Kearfott (intégrant une autre méthode de relaxation linéaire).

Jeudi 11 février 2010 à 10h15, en salle 118 :

Alin Bostan (Projet Algorithms, INRIA Paris-Rocquencourt).

The complete generating function for Gessel walks is algebraic.

The aim of the talk is to show how a difficult combinatorial problem has been recently solved using an experimental-mathematics approach combined with (rather involved) computer algebra techniques. More precisely, let g(n,i,j) denote the number of lattice walks in the quarter plane which start at the origin, end at the point (i,j), and consist of n unit steps going either west, south-west, east, or north-east. In the early nineties, Ira Gessel conjectured that the sequence of excursions g(n,0,0) is holonomic. We will present the computer-driven discovery and proof of the following generalization, obtained in August 2008 together with Manuel Kauers: the trivariate generating series of the sequence (g(n,i,j))_{n,i,j} is an algebraic function.

Jeudi 21 janvier 2010 à 10h30, en salle 118 :

Bogdan Pasca (Arénaire, LIP).

Pipelined FPGA adders.

Integer addition is an elementary building block (multiplication as well) of complex arithmetic operators. This study presents a binary integer addition operator generator. Based on resource estimations, our generator selects the best design out of an extensible set of proposed adder operator designs. The addition operator is presented in the context of FloPoCo, a core generator for FPGAs, and is the building blocks of more complex operators: floating-point addition, multiplication, squaring, square-root and other.

Jeudi 17 décembre à 10h30, en salle 118 :

Bruno Grenet (MC2, LIP).

Difficulté du résultant multivarié.

Le résultant d'un système (générique) de polynômes f_1,...,f_n est un polynôme en les coefficients des f_i qui s'annule si et seulement si les f_i admettent une racine commune. Dans le cas de deux polynômes à une variable, le résultant est le déterminant de la matrice de Sylvester et est donc calculable en temps polynomial.

Le cas qui nous intéressera est celui d'un système de n polynômes homogènes en n variables. Canny a donné en 1987 un algorithme en espace polynomial pour calculer ce résultant, mais la complexité exacte reste inconnue. Nous verrons dans cet exposé que le problème de décision associé (décider de la nullité du résultant) est dans la hiérarchie polynomiale (classe AM, au deuxième niveau de la hiérarchie), et qu'il est NP-difficile.

Si le temps le permet, je parlerai également d'un problème relié qui est le calcul du déterminant de matrices de grande taille admettant une description polynomiale.

Jeudi 10 décembre à 10h30, en salle 118 :

David Coeurjolly (LIRIS, CNRS, Université de Lyon).

Géométrie Arithmétique Discrète

La géométrie discrète est un domaine de l'informatique à la croisée de l'analyse d'images, de la géométrie algorithmique, de l'arithmétique, de la combinatoire ou encore de la théorie des nombres. L'objectif de ce séminaire est de faire une petite introduction à ces problématiques avec un regard particulier sur l'utilisation de principes arithmétiques élémentaires pour accélérer les algorithmes d'analyse.

Jeudi 3 décembre à 10h30, en salle 118 :

Javier Bruguera (Grupo de Arquitectura de Computadores, Universidade de Santiago de Compostela).

Trying to improve the performance of floating-point computations

The floating-point representation is the standard representation for real numbers and widely used in today processors and engineering and scientific applications. This representation outperforms other alternative representations that are kept limited to specific applications. However, some computations can result in a loss of accuracy because of the accumulation of rounding errors in the floating-point operations. This loss of accuracy can be mitigated by an increase in the precision of the representation but this requires a larger amount of storage and more complex and slower operations. We explore a modification of the floating-point representation to handle some of the above-mentioned issues.

Alternatively, the error introduced can be computed and used to determine if the result is accurate enough for the application being implemented. Traditional approaches for the error estimation are software-based, which result in complex implementations. We introduce a hardware error estimate that can be implemented concurrently with the standard floating-point operations.

Jeudi 26 novembre à 10h30, en salle 118 :

Michel Kieffer (L2S - CNRS - Supélec - Université Paris-Sud).

Efficient 16-bit floating point interval processor for embedded applications

Résumé disponible au format pdf.

Mardi 24 novembre à 15h00, en salle 115 :

William B. Hart (Mathematics Institute, University of Warwick, Coventry, UK).

FLINT : Fast Library for Number Theory

I will describe the library FLINT which is being developed to make low level routines such as polynomial arithmetic and linear algebra fast. I will give some indication of the recent developments, both algorithmic and computational, in FLINT, and give some comparisons with other similar projects.

Jeudi 19 novembre à 10h30, en salle 118 :

Vincent Lefèvre (Arénaire).

Preuves par tests exhaustifs en basse précision

Je présenterai des exemples de preuves conçues à l'aide de tests exhaustifs effectués en basse précision. Je montrerai tout d'abord comment prouver l'optimalité (sous certaines conditions) de l'algorithme TwoSum dans une précision fixée p ≥ 12 par un test de tous les algorithmes potentiels, et comment cette preuve permet de déduire l'optimalité de cet algorithme pour toute précision p ≥ 12. Je présenterai ensuite la bibliothèque SIPE (Small Integer Plus Exponent) que j'ai écrite afin de pouvoir effectuer efficacement ce genre de tests. Je mentionnerai une seconde application de SIPE, permettant de conjecturer une borne d'erreur optimale de l'algorithme DblMult, dans le but de prouver cette borne par la suite (travail en cours).

Jeudi 5 novembre à 10h30, en salle 118 :

Christophe Mouilleron (Arénaire).

Calculs rapides avec des matrices denses structurées.

De nombreux problèmes peuvent se résoudre par l'intermédiaire de calculs matriciels. Parfois, les matrices qui apparaissent lors de la résolution d'un problème peuvent être codées avec beaucoup moins de n² coefficients. C'est notamment le cas pour les matrices Toeplitz, Vandermonde et Cauchy.

Dans cet exposé, on va présenter un cadre général pour couvrir ces matrices dites « denses structurées ». On se concentrera ensuite sur le problème de la multiplication par un vecteur, puis sur celui de l'inversion. Après un survol des algorithmes rapides présents dans la littérature, on exhibera un nouvel algorithme d'inversion plus direct et moins coûteux en mémoire pour les structures usuelles.

Jeudi 22 octobre à 10h30, en salle des thèses :

Laurent Théry (EPI Marelle, INRIA Sophia).

Calculer efficacement pour prouver.

Des exemples comme le théorème des 4 couleurs ou la conjecture de Kepler (prouvée par Thomas Hales) illustrent comment la puissance de calcul des ordinateurs peut être mise à profit pour établir de nouveaux résultats mathématiques. De tels exemples semblent donc très attractifs pour les assistants de preuve comme Coq qui permettent de formaliser les mathématiques. Malheureusement la puissance de calcul proposée par ces assistants est souvent très faible. Par exemple, Coq ne permet que d'écrire des programmes dans un cadre de programmation très restrictif: la programmation fonctionnelle pure. Dans cet exposé, on présentera nos efforts pour augmenter la puissance de calcul de Coq tout en conservant la sûreté des résultats obtenus.

Jeudi 15 octobre à 10h30, en salle 118 :

Hong Diep Nguyen (Arénaire, LIP-ENS Lyon).

Implantation efficace pour le produit de matrices intervalles.

Résumé : Dans cet exposé, nous rappellerons la définition et le coût du produit de matrices par intervalles par l'algorithme « naïf ». L'idée pour obtenir une implantation efficace pour le produit de matrices intervalles est de tirer pleinement parti des bibliothèques qui sont bien optimisées pour le produit de matrices flottantes. Nous étudierons quelques cas particuliers que nous utiliserons pour mettre au point un algorithme utilisant peu de produits de matrices ponctuelles (c'est-à-dire des matrices dont les éléments sont des réels, ou, pour l'implantation, des flottants). Sous certaines conditions particulières, cet algorithme fournit un résultat exact (en arithmétique exacte). En général, il fournit un résultat sur-estimant le résultat exact, le facteur de surestimation au pire sera également donné lors de cet exposé.

Jeudi 8 octobre à 10h30, en salle 118 :

Álvaro Vázquez Álvarez (Arénaire, LIP-ENS Lyon).

Hardware units for decimal arithmetic.

Current financial, e-commerce and user-oriented applications make an intensive use of integer and fractional numbers represented in decimal radix. This makes an attractive opportunity for microprocessor manufactures to provide a dedicated DFU (decimal floating-point unit) in their new high-end microprocessors. This interest is supported by the recent approval of the revision of the IEEE 754 floating-point standard (IEEE 754-2008), which incorporates a specification for decimal arithmetic.

In this context, this presentation deals with the research and design of new algorithms and high-performance architectures for DFX (decimal fixed-point) and DFP (decimal floating-point) to evaluate in hardware the basic arithmetic operations, that is, add/sub, multiplication (and fused multiply-add) and division. Moreover, a decimal new CORDIC unit for computing transcendentals is also detailed. These units are suitable for implementing in high-end VLSI microprocessors. A discussion about the benefits/costs of decimal hardware VLSI vs. FPGA and software implementations of the IEEE 754-2008 standard is also provided.

The structure of this presentation is as follows:

The new demands for decimal arithmetic.
Hardware solutions vs. software libraries
Decimal specification in the IEEE 754-2008 standard.
Decimal fixed and floating-point hardware units for the basic arithmetic operations.

Addition/subtraction
Multiplication
Fused Multiply-Add (FMA)
Division

Decimal CORDIC unit for the evaluation of elementary functions.
Conclusions and open questions.

Jeudi 1er octobre à 10h15, en salle 118 :

Nicolas Louvet (UCBL, EPI Arénaire, LIP-ENS Lyon).

Calcul ou estimation du conditionnement d'un problème par différentiation automatique.

Le nombre de conditionnement d'un problème permet de mesurer la sensibilité de sa solution à des perturbations de ses données. Lorsqu'une solution approchée est calculée en arithmétique flottante, la combinaison d'une analyse d'erreur inverse et du nombre de conditionnement du problème permet en particulier de déduire une borne d'erreur valable au premier ordre. Même si le calcul du conditionnement ne permet pas en général de certifer l'erreur entachant la solution approchée, au sens où la borne obtenue n'est valable qu'au premier ordre, il s'agit d'un outil indispensable afin de comprendre la qualité des bornes d'erreurs certifiées.

Dans cet exposé, nous présenterons l'état de nos travaux en cours sur le calcul du conditionnement à l'aide de la différentiation automatique. Lorsqu'un algorithme exact est connu pour calculer la solution d'un problème donné, nous verrons en effet que la différentiation automatique permet de calculer ou d'encadrer très précisément le conditionnement de ce problème. Mais ce calcul peut s'avérer être plus coûteux, de plusieurs ordres de grandeurs, que l'algorithme de résolution du problème. Nous montrerons donc également comment estimer le conditionnement, pour un coût multiple du coût de l'algorithme de résolution employé.

2008-2009

Lundi 6 juillet à 10h15, en amphi B :

Jean-Paul Allouche (CNRS, LRI, Orsay).

Ubiquité de la suite de Thue-Morse.

La suite de (Prouhet-)Thue-Morse peut être définie comme la limite de la suite de mots obtenus en partant de 0 et en itérant la substitution 0 → 01, 1 → 10

0
01
0110
01101001
...

Cette suite a des propriétés d'ubiquité que nous nous proposons de parcourir. Elle et ses cousines serviront de fil conducteur à une promenade à travers plusieurs domaines des mathématiques ou de la physique : théorie des nombres (transcendance, séries de Dirichlet), itération des fonctions continues réelles, combinatoire des mots, opérateurs de Schrödinger discrets et quasicristaux, ...

Nous ferons aussi allusion à certaines compositions musicales, à des Kolam indiens (dessins rituels qu'on retrouve aussi dans la tradition des dessins sur le sable aux îles Vanuatu), ainsi qu'à des résultats récents sur les développements en base non-entière.

Un Kolam indien

Voir aussi : http://www.lri.fr/~allouche/lyon.html.

Vendredi 3 juillet à 12h45, en amphi B :

Ping Tak Peter Tang (D. E. Shaw Research, LLC).

A Novel Approach to Tight Bounds and Statistical Information of Rounding Errors.

Obtaining bounds on rounding errors are difficult in practice in the sense that bounds can be overly pessimistic or simplistic. In this talk, I will present some work on automatically generating information for fixed point computation of linear transforms. The resulting information includes not only worst case error bound but also probability distributions of errors.

Jeudi 25 juin à 10h15, en amphi A :

Damien Stehlé (CNRS, currently seconded to the Universities of Sydney and Macquarie).

Chiffrer à l'aide des réseaux idéaux.

Il y a un peu plus de 10 ans, le cryptosystème NTRU a démontré l'efficacité de la cryptographie reposant sur des réseaux structurés. Malheureusement, la sécurité de NTRU est seulement heuristique. Construire un cryptosystème efficace utilisant des réseaux structurés et admettant une preuve de sécurité reposant sur la difficulté d'un problème établi était donc une question ouverte importante ; d'autant plus qu'il s'agit d'une des alternatives les plus prometteuses à la cryptographie moderne dans l'hypothèse d'un environnement post-quantique.

Dans cet exposé, je décrirai un schéma de chiffrement à clé publique résistant aux attaques à clair choisi, dont la sécurité repose de manière rigoureuse sur la difficulté des instances les plus difficiles du problème du plus court vecteur restreint à un certain type de réseaux, appelés réseaux idéaux. Sous l'hypothèse que la résolution de ces instances requiert un temps exponentiel, y compris avec un ordinateur quantique, notre schéma de chiffrement résiste à toute attaque sous-exponentielle et possède une efficacité (quasi-)optimale : si n est le paramtère de sécurité, les clés sont de tailles softO(n), et le coût amorti du chiffrement et du déchiffrement est softO(1) par bit de message.

Il s'agit d'un travail en commun avec Ron Steinfeld, Keisuke Tanaka et Keita Xagawa.

Jeudi 18 juin à 10h15, salle de conseil du LIP :

Adrien Panhaleux (Arénaire).

Midpoints et exact-points de quelques fonctions usuelles

Lors de l'implantation d'une fonction mathématique f avec arrondi correct en arithmétique flottante, il est souvent intéressant de savoir s'il existe des flottants x pour lesquels f(x) est - soit équidistant de deux flottants consécutifs (i.e. f(x) est un "midpoint"), - soit exactement un flottant (i.e. f(x) est un "exact-point"). En effet, la connaissance des midpoints et des exact-points d'une fonction permettra souvent de simplifier le test d'arrondi correct, et d'obtenir ainsi une implantation plus efficace. Dans le cas de l'arrondi au plus proche par exemple, l'absence de midpoints simplifie considérablement le test d'arrondi final. Le but de ce travail est d'étudier les midpoints et les exact-points de quelques fonctions usuelles. Nous avons regroupé les résultats connus, valides essentiellement en base 2. Nous étendons ces résultats en considérant de nouvelles fonctions, en traitant le cas de la base 10, mais aussi en prenant en compte des formats d'entrée et de sortie différents. L'exposé se concentrera sur deux fonctions (l'inverse et l'inverse de la norme 2D), ce qui permettra de présenter la plupart des mécanismes de preuve utilisés.

Jeudi 4 juin 2009 à 10h15, salle du conseil du LIP :

Matthieu Martel (Equipe DALI, Laboratoire ELIAUS, Université de Perpignan).

Amélioration de l'implantation de formules mathématiques en arithmétiques fixe et flottante

Cet exposé porte sur des techniques permettant d'estimer et d'améliorer la qualité numérique de calculs effectués dans différentes arithmétiques des ordinateurs. La méthode proposée est indépendante de l'arithmétique utilisée et sera appliquée aux cas des systèmes à virgules fixes et flottantes. Nous nous intéresserons tout d'abord à mesurer globalement la qualité de l'implantation d'une formule vis-à-vis d'une certaine mesure. Pour l'arithmétique à virgule flottante, cette mesure concernera la distance entre le résultat exact et le résultat arrondi, dans le pire cas. Pour l'arithmétique à virgule fixe, cette mesure concernera le nombre de bits nécessaires pour représenter tous les résultats intermédiaires. Nous verrons ensuite comment les opérations responsables des principales dégradation de la qualité d'une implémentation peuvent être identifiées automatiquement. Cette information est utile pour améliorer manuellement la qualité des programmes. Enfin, nous proposerons une technique entièrement automatique pour transformer une formule en une autre formule, mathématiquement équivalente à l'originale et de meilleure qualité par rapport au critère considéré.

Lundi 18 mai 2009 à 13h00, amphi B :

Mioara Joldes (Arénaire)

Certified and fast computation of supremum norms of approximation errors

In many numerical programs there is a need for a high-quality floating-point approximation of useful functions f, such as exp, sin, erf. In the actual implementation, the function is replaced by a polynomial p, which leads to an approximation error (absolute or relative) eps = p-f or eps = p/f-1. The tight yet certain bounding of this error is an important step towards safe implementations. The problem is difficult mainly because that approximation error is very small and the difference p-f is subject to high cancellation. Previous approaches for computing the supremum norm in this degenerate case, have proven to be unsafe, not sufficiently tight or too tedious in manual work. We present a safe and fast algorithm that computes a tight lower and upper bound for the supremum norms of approximation errors. The algorithm is based on a combination of several techniques, including enhanced interval arithmetic, automatic differentiation and isolation of the roots of a polynomial. We have implemented our algorithm and give timings on several examples.

Jeudi 14 mai 2009 à 10h15, amphi B (3ème étage du bâtiment GN1) :

Richard Brent (Australian National University)

Factoring and testing irreducibility of sparse polynomials over small finite fields

We consider algorithms for testing irreducibility and (if they are not irreducible) finding factors of polynomials over finite fields. In the talk we consider the case of characteristic 2, but the algorithms generalise to other small positive characteristics. The algorithms are efficient for sparse polynomials of high degree. They have been applied to find primitive trinomials whose degree is the exponent of a Mersenne prime, including the (largest known) case of degree 43112609. [Joint work with Paul Zimmermann.]

Jeudi 7 mai 2009 à 10h15, salle du conseil du LIP :

Joris van der Hoeven (Équipe d'analyse harmonique, Dpt de mathématiques d'Orsay, Université Paris 11)

Calcul rapide et fiable avec des séries en grande précision

Dans l'exposé, on rappellera d'abord la technique du calcul détendu sur les séries formelles, qui permet d'obtenir un grand nombre de coefficients d'une série en temps presque linéaire. On s'intéressera plus particulièrement aux séries à coefficients flottants, ce qui nécessite de techniques supplémentaires pour assurer une bonne stabilité numérique. Enfin, on considérera le cas où les coefficients sont des boules (ou intervalles), et on exposera des méthodes pour borner les restes des séries sur des boules.

Jeudi 30 avril 2009 à 10h15, salle du conseil du LIP :

Pedro Echeverría (Universidad Politécnica de Madrid)

Single floating point libraries Development and Comparison

Floating Point standard is mainly though for software machine and the fixed wordlength of the memories used in that environments. However, when implementing floating point operators on FPGA, we can take advantage of FPGA flexibilities to implement floating point operators with a better performance than just applying directly the standard. This way, we have developed a series of different libraries of single floating point operators (addition-substraction, multiplication, division, square root, exponential, logarithm and powering) where we have introduced some simplifications to the standard. In the first library we have implemented the floating point standard without any substantial simplification while in another three libraires we have gradually introduced the following simplifications:

Denormalized numbers simplification.
Truncation rounding.
Hardware representation.

A final comparison of the results obtained for the four libraries (and when possible with Xilinx floating point Core) shows the very important improvements obtained for the final library containing the three simplifications with respect to the standard library:

Improvements in speed and use of resources.
Decrease in the number of pipeline stages.
General simplification of the architectures needed for each operand.

Inverse CDF function for FPGA's with Quintic Hermite Interpolation

Inverse cumulative distribution function (ICDF) is very important in the field of Random Number Generators (RNG) as it allows to implement a RNG with any distribution using an uniform RNG and de ICDF of the target distribution.
The main problem of this approach is how to implement the ICDF. One very interesting possibility is to use the Quintic Hermite interpolation that is a high quality interpolation method to implement ICDFs. In this method the input range of a ICDF [0,1] is segmented and in each segment the function is interpolated with a five degree polynomial that has different coefficients for each of the segment. We have proposed how to implement these type of functions specially for FPGA's to obtain high performance with a throughput of one data per cycle. Our implementation includes tailored arithmetic, non-uniform non hiereachical segments and an adapted search algorithms (they are needed to search for the corresponding segment for an input) to avoid software multicycle search.

Jeudi 23 avril 2009 à 10h00, en amphi K :

Siegfried M. Rump (Univ. Tech. de Hambourg)

Ultimately fast algorithms for summation and dot products

In the past years we developed fast algorithms for the summation of floating-point numbers as well as the dot product of two vectors. Such problems are ubiquitous in scientific computations. We have algorithms producing a result as if computed with some specified precision as well as algorithms producing a result with a specified accuracy. These seem to be the fastest known algorithms for these tasks. They extensively use so-called error-free transformations of floating-point operations. Now we can present an additional improvement of these algorithms of up to 25 % computing time. Numerical examples, in particular for the inversion of extremely ill-conditioned matrices and large sparse matrix-vector multiplication will demonstrate the behaviour of our algorithms.

Stef Graillat (PEQUAN, LIP6, Univ. Paris 6)

Calcul précis de racines simples de polynômes en précision finie

Dans cet exposé, nous présenterons tout d'abord l'algorithme de Horner compensé qui permet d'évaluer un polynôme avec une précision similaire à celle qu'on aurait obtenue si on avait effectué les calculs en précision doublée. Nous utiliserons ensuite cet algorithme pour calculer le résidu dans l'algorithme de Newton pour le calcul d'une racine simple. Nous montrons que la précision du calcul d'une racine simple est similaire à celle qu'on aurait obtenue si on avait effectué les calculs dans l'algorithme de Newton en précision doublée.

Vendredi 20 mars 2009 à 10h15, salle du conseil du LIP :

Florent de Dinechin et Honoré Takeugming (Arénaire)

Traitement du signal pour les transmissions optiques à 40Gb/s

Pour augmenter jusquà 40Gb/s, et peut-être 100Gb/s, le débit d'information qu'on peut faire passer sur les fibres optiques des générations précédentes, l'approche la plus pertinent actuellement est le multiplexage en polarisation. Le projet ANR TCHATER a pour but la réalisation d'un démonstrateur pour de telles transmissions. On présentera essentiellement la partie traitement du signal, qui est en cours d'implémentation sur FPGAs, et les challenges (pas seulement arithmétiques) que nous rencontrons.

Mercredi 11 mars 2009 à 13h30, salle du conseil du LIP. Exposé de Jean-Luc Beuchat (Univ. Tsukuba, Japon) : Hardware Operators for Pairing-Based Cryptography.
Résumé. Originally introduced in cryptography by Menezes, Okamoto & Vanstone (1993) then Frey & Rück (1994) to attack the discrete logarithm problem over a particular class of elliptic curves, pairings have since then been put to a constructive use in various useful cryptographic protocols such as short digital signature or identity-based encryption. However, evaluating these pairings relies heavily on finite field arithmetic, and their computation in software is still expensive. Developing hardware accelerators is therefore crucial.
So far, we proposed a hardware co-processor designed to accelerate the computation of the Tate pairing in characteristics 2 and 3. We tried to reduce the silicon footprint (or in our case the usage of FPGA resources) of the circuit to ensure scalability, while trying to minimize the impact on the overall performances. In this talk, we will focus on the other end of the hardware design spectrum. We will describe another co-processor architecture, designed to achieve much lower computation times, at the expense of hardware resources.

Jeudi 5 mars 2009 à 10h15, salle 118 (1er étage du bâtiment GN1 de l'ENSL). Exposé de Richard Leroy (IRMAR, Univ. Rennes 2) : Certificats de positivité dans la base de Bernstein multivariée.
Résumé. On étudiera lors de cet exposé la positivité des polynômes réels sur un simplexe. Plus adaptée à ce contexte, on utilisera la base de Bernstein plutôt que la base traditionnelle des monômes. Les propriétés géométriques de la base de Bernstein permettent d'obtenir un algorithme qui décide si un polynôme f donné est positif, et qui, le cas échéant, fournit un certificat de positivité, i.e. une expression de f qui rend triviale sa positivité. Deux méthodes seront présentées : l'élévation du degré et la subdivision du simplexe. Des résultats récents d'approximation garantissent la correction de l'algorithme, qui est de plus certifié. Nous donnerons également une borne sur sa complexité.

Jeudi 26 février 2009 à 13h30, salle A2 (4ème étage du bâtiment GN1 de l'ENSL). Exposé d'Ivan Morel (Arénaire) : H-LLL : Un LLL flottant vectoriel.
Résumé. La réduction de réseaux a d'importantes applications dans divers domaines, comme la cryptologie, la théorie algorithmique des nombres, l'arithmétique des ordinateurs, etc.. L'algorithme LLL permet de réduire une base quelconque d'un réseau en une 'bonne' base en temps polynomial. Cependant, la taille des entiers manipulés dans l'algorithme rend ce dernier inutilisable en pratique dans sa version exacte quand la dimension ou la taille des entrées augmente. Il est donc naturel de se tourner vers le calcul flottant, particulièrement pour le calcul des coefficients de Gram-Schmidt dont le coût domine le coût total de l'algorithme. Je présenterai ainsi une nouvelle variante flottante de l'algorithme LLL, H-LLL, utilisant l'algorithme de Householder flottant pour calculer la décomposition matricielle QR et ainsi obtenir les coefficients de Gram-Schmidt. J'introduirai les enjeux d'une telle approche, ainsi que ses avantages/inconvénients par rapport aux techniques existantes.

Jeudi 19 février 2009 à 13h, Amphi B (3ème étage du bâtiment GN1). Exposé de Micaela Mayero (LIPN, Univ. Paris 13) : Des preuves et des nombres.
Résumé. La manipulation des nombres nous semble naturelle dès lors que ceux-ci sont associés à la notion de calcul. Les preuves formelles soulèvent la problématique supplémentaire de la formalisation de ces nombres et de la préservation de leurs propriétes. Nous nous intéresserons en particulier aux nombres entiers, relatifs, réels, flottants, dans différents assistants de preuves, puis en nous appuyant sur divers exemples, nous tenterons de présenter différentes approches pour gérer ces nombres.

Jeudi 5 février 2009 à 10h15, salle du conseil du LIP. Exposé de Sylvain Collange (DALI, ELIAUS, Université de Perpignan Via Domitia) : L'arithmétique sur GPU en 2009.
Résumé. En l'espace de dix ans, les processeurs graphiques (GPU) ont vu leurs unités de calcul évoluer progressivement depuis un format virgule fixe sur 5 bits jusqu'à la double précision IEEE-754, au point de « dépasser » aujourd'hui les processeurs généralistes. En effet, le GTX 280 de Nvidia intègre une unité FMA, traite les flottants dénormalisés en matériel et permet de changer de mode d'arrondi instantanément, contrairement aux processeurs x86 courants.
L'absence d'existant et les contraintes spécifiques aux tâches graphiques ont conduit à des choix souvent différents de ceux effectués pour les CPU généralistes.
Nous analyserons les approches suivies par les principaux constructeurs pour leurs implantations matérielles respectives, et les conséquences sur le développement logiciel des opérateurs non présents en matériel, sur une plate-forme en évolution où le pire côtoie souvent le meilleur.

Jeudi 29 janvier 2009 à 14h, salle du conseil du LIP. Exposé d'Andrew Novocin (ARITH, LIRMM) : A brief history of factoring polynomials.
Résumé. In this talk I will outline the algorithm's for factoring polynomials in Z[x] with an eye on arriving at my Ph.d result: a new algorithm which is both the fastest algorithm in theory and the fastest algorithm in practice.

Vendredi 16 janvier 2009 à 13h30, Salle du conseil du LIP. Exposé de Jean-Yves L'Excellent (Graal, LIP, ENS Lyon) : Some numerical issues in sparse direct solvers.
Résumé. Sparse direct solvers, thanks to their robustness, are methods of choice to solve large sparse systems of linear equations of the form A x = b, where A is a large sparse matrix. One of the main requirements from applications consists in solving larger and larger problems efficiently (memory usage, performance) but also accurately. This objective in turn necessitates addressing certain numerical issues through a careful design and implementation of numerical functionalities.
In this talk, I will first introduce sparse direct solvers, then focus on a few numerical issues that we have been confronted with in the MUMPS project: error analysis, numerical pivoting, iterative refinement, maximum weighted matching, preselection of pivots, scaling, null pivots, rank detection, etc. If time permits, I will also show how parallelism and out-of-core storage complexify these issues. More information on MUMPS can be obtained from the http://graal.ens-lyon.fr/MUMPS and http://mumps.enseeiht.fr URLs.

Vendredi 12 décembre 2008 à 10h15, salle du conseil du LIP. Exposé de Marcelo Kaihara (École Polytechnique Fédérale de Lausanne) : Algorithms for Modular Arithmetic in Public-key Cryptology.
Résumé. Processing public-key cryptologic systems requires a huge amount of computation, and, there is therefore, a great demand for developing dedicated hardware to speed up the computations. Modular multiplication and division are the basic operations which are intensively used in cryptology and number theoretic applications. In this talk, we will see fast modular multiplication and division algorithms over integers for public-key cryptology. The talk is mainly focused in algorithms where computations are performed manipulating huge integers with simple operations such as redundant addition/subtractions and shifts; in particular we will see the mixed radix-4/2 hardware algorithm for modular multiplication/division and the bipartite modular multiplication method (BMM method). At the end of the talk, we will see some contributions to the RNS Montgomery multiplication, a different approach where large integers are decomposed into smaller integers and are processed using more sophisticated operations.

Vendredi 5 décembre 2008 à 10h15, salle du conseil du LIP. Exposé de Marc Mezzarobba (Algorithms, INRIA Paris-Rocquencourt) : Suites et fonctions holonomes : évaluation numérique et calcul automatique de bornes.
Résumé. Une famille d'algorithmes dus (dans leur version générale) à David et Gregory Chudnovsky permet d'évaluer numériquement à grande précision - pour fixer les idées, mille ou dix mille décimales - les fonctions analytiques solutions d'équations différentielles linéaires à coefficients polynomiaux. Le point de départ est un algorithme efficace pour « dérouler » certaines suites récurrentes. Je présenterai ces différents algorithmes, devenus pour la plupart classiques, ainsi que quelques remarques sur leur complexité et leur implémentation.
Par ailleurs, je décrirai un procédé de calcul de bornes sur les suites satisfaisant des récurrences linéaires à coefficients polynomiaux. Dans le contexte des algorithmes précédents, celui-ci permet de contrôler finement le nombre de termes des développements de Taylor à prendre en compte pour garantir une certaine précision lors du prolongement analytique numérique. Il s'agit d'un travail en cours avec mon directeur de thèse Bruno Salvy.

Vendredi 28 novembre 2008 à 10h15, amphithéatre B (3ème étage du bâtiment principal de l'ENS). Exposé de Xiaoye Sherry Li (Computational Research Division, Lawrence Berkeley National Laboratory) : High Precision Software and Application in Numerical Linear Algebra
Résumé. We have developed a number of portable high precision floating-point arithmetic software packages, including double-double precision, quad-double precision, and arbitrary precision. We will give an overview of the data structures and the implementation techniques used in these software. As an application, we will present the algorithms, error bounds, and numerical results of extra-precise iterative refinement for linear systems and linear least squares problems. The algorithms require only limited use of extra precision and add only O(n²) work to the O(n³) cost of LU, or O(m n) work to the O(m n²) cost of QR. Our algorithms reduce the forward normwise and componentwise errors to O(ε) unless the system is too ill-conditioned. The extra precision is facilitated by the new extended-precision BLAS standard in a portable way, and the algorithms will be included in a future release of (Sca)LAPACK.
Joint work with David Bailey, Jim Demmel, Yozo Hida, Jason Riedy, Brandon Thompson, and Meghana Vishvanath.

Mercredi 26 novembre 2008 à 14h, salle 116 (premier étage du bâtiment principal de l'ENS Lyon). Exposé de Francisco Rodríguez-Henríquez (Centro de investigación y de Estudios Avanzados del I.P.N) : Inverse Frobenius and Frobenius Operator Computation over GF(p^m).
Résumé. Where we have found some formulations and associated complexity costs for the computation of the inverse Frobenius and Frobenius operator of elements A of GF(p^m). We give explicit formulae when the finite field has been constructed using trinomials and tetranomials in characteristic two and three, respectively.
This is a joint work with Omran Ahmadi.

Vendredi 21 novembre 2008 à 10h15, salle du conseil du LIP. Exposé de Guillaume Revy (Arénaire) : A new binary floating-point division algorithm and its implementation in software.
Résumé. We propose a new approach for software implementation of binary floating-point division. This approach is based on the fast and accurate evaluation of a particular bivariate polynomial. First, we will introduce some sufficient conditions on approximation and rounding errors to ensure correct rounding. Then we will explain how to generate in an automatic way an efficient evaluation program for this particular polynomial. We will also show how the resulting program has been automatically validated using Sollya and Gappa.
Further, we will demonstrate the practical interest of our approach with an insight into our implementation for the binary32 format (single precision) and into some experiments done with the ST200 compiler from STMicrolelectronics.

Vendredi 7 novembre 2008 à 10h15, salle du conseil du LIP. Exposé de Jean-Michel Muller (Arénaire) : On the computation of correctly-rounded sums.
Résumé. The computation of sums appears in many domains of numerical analysis. We show that among the set of the algorithms with no comparisons performing only floating-point operations, the 2Sum algorithm introduced by Knuth is optimal, both in terms of number of operations and depth of the dependency graph. We also show that, under reasonable conditions, it is impossible to always obtain the correctly rounded-to-nearest sum of n>= 3 floating-point numbers with an algorithm without tests performing only round-to-nearest additions/subtractions. Boldo and Melquiond have proposed an algorithm to compute the rounded-to-nearest sum of three operands, introducing a new rounding mode unavailable on current hardware, rounding to odd; but their simulation of rounding to odd requires tests. We show that rounding to odd can be be realized using only floating-point additions/subtractions performed in the standard rounding modes and a multiplication by the constant 0.5, thus allowing the rounded-to-nearest sum of three floating-point numbers to be determined without tests. Starting from the algorithm due to Boldo and Melquiond, we also show that the sum of three floating-point values rounded according to any of the standard directed rounding modes can be determined using only additions/subtractions, provided that the operands are of the same sign.

Vendredi 17 octobre 2008, soutenance de thèse de Christoph Lauter (Arénaire) à 14h en salle des thèses : Arrondi correct de fonctions mathématiques - fonctions univariées et bivariées, certification et automatisation.
Résumé. Cette thèse élargit l'espace de recherche accessible en pratique pour des implantations de fonctions mathématiques correctement arrondies en virgule flottante. Elle passe d'abord de l'arrondi correct de fonctions univariées comme log à des familles de fonctions univariées xⁿ, puis à la fonction bivariée x^y. Une approche novatrice pour la détection de cas de frontière d'arrondi de x^y à l'aide d'une information partielle sur les pires cas de cette fonction est proposée. Cette innovation provoque un gain en vitesse conséquent.
Ensuite, cette thèse propose des approches automatiques pour certifier une implantation de fonction correctement arrondie. Pour la certification des bornes d'erreur d'approximation, un nouvel algorithme pour le calcul de normes infinies certifiées est présenté et mis en pratique. Puis les erreurs d'arrondi dans une implantation de fonction mathématique sont analysées par des techniques développées pour l'outil de preuve formelle Gappa.
Finalement, des algorithmes sont développés qui permettent l'automatisation de l'implantation de fonctions. Une première mise en œuvre dans l'outil Sollya permet de générer et certifier, sans aucune intervention humaine, le code pour évaluer une fonction mathématique. À l'aide d'un tel outil automatique, de larges espaces de recherches peuvent être parcourus afin d'optimiser une implantation. Au futur, une intégration de ces techniques dans un compilateur est envisageable.

Vendredi 17 octobre 2008 à 10h15, amphithéatre B. Exposé de Marius Cornea (Intel, Portland) : Intel(R) MKL Overview.
Abstract. The Intel(R) Math Kernel Library is a collection of highly optimized and parallelized mathematical functions for scientific, engineering, and financial applications. It covers several function domains, mostly in areas where performance is critical and users want to exploit Intel Architecture resources as much as possible. Linear algebra, Fourier transforms, vector math functions, and vector statistical functions are just some of the areas covered. The presentation will cover functionality and performance aspects of the library, as well as possible future directions of development.

Vendredi 10 octobre 2008 à 10h15, salle du conseil du LIP. Exposé de Sylvain Chevillard (Arénaire) : Approximation rationnelle efficace pour le matériel.
Résumé. Pour implémenter une fonction mathématique en matériel, on passe souvent par une approximation polynomiale de la fonction. C'est cette approximation polynomiale qui est évaluée par la suite. On utilise préférentiellement un polynôme parce qu'il s'agit d'un objet bien maîtrisé et qu'on sait évaluer très efficacement. Par contre, l'approximation par des fractions rationnelles est peu utilisée : l'évaluation d'une fraction nécessite une division ; c'est une opération trop coûteuse en général pour qu'une approximation rationnelle se révèle intéressante. Dans les années 70, M. Ercegovac a proposé une méthode permettant d'évaluer sans division certaines fractions rationnelles. Cependant, la fraction rationnelle qui minimise l'erreur d'approximation à une fonction donnée n'a aucune raison de satisfaire les contraintes imposées par la méthode d'Ercegovac. Aussi, cette méthode a été peu utilisée en pratique.
Dans cet exposé, nous reviendrons sur la méthode en question, et nous verrons un algorithme permettant de trouver de très bonnes approximations rationnelles satisfaisant ces contraintes particulières.
Il s'agit d'un travail en collaboration avec N. Brisebarre, M. Ercegovac (UCLA), J.-M. Muller et S. Torres.

Vendredi 26 septembre 2008 à 10h15, salle du conseil du LIP. Exposé de Laurent Fousse (CASYS, LJK, Univ. J. Fourier, Grenoble) : Réduction modulaire simultanée et substitution de Kronecker pour les petits corps finis.
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.

2007-2008

Vendredi 11 juillet 2008 à 10h15, salle du conseil du LIP. Exposé de Hong Diep Nguyen (Arénaire) : Résoudre et certifier la solution d'un système linéaire.
Résumé. Je présenterai une approche pour résoudre un système linéaire et simultanément certifier la solution calculée. Par certifier, on entend calculer un encadrement garanti de l'erreur. Pour cela, nous passons de l'arithmétique flottante à l'arithmétique par intervalles et nous résolvons le système linéaire satisfait par le résidu. Cela nous donne une borne garantie de l'erreur sur le résultat exact.
Nous avons adapté une méthode de raffinement itératif pour le calcul de la borne d'erreur. La combinaison de ces deux composantes de base, à savoir la résolution en arithmétique flottante d'un système linéaire et le raffinement itératif de la borne d'erreur en utilisant l'arithmétique par intervalle, produit une solution plus précise dotée d'une borne d'erreur. Cette borne d'erreur nous permet d'estimer en outre le nombre de chiffres corrects de la solution approchée.
Notre approche est implantée en utilisant les bibliothèques MPFR et MPFI. Ces deux bibliothèques nous permettent d'adapter la précision utilisée à chaque étape. Cela nous a permis d'étudier aussi l'effet de la précision utilisée pour le calcul du résidu sur la qualité du résultat calculé. Les résultats expérimentaux illustrent le gain au niveau de la qualité de la solution et de la borne d'erreur lié à la précision utilisée pour les calculs.

Lundi 30 juin 2008 à 15h, salle du conseil du LIP. Exposé de Francisco José Jaime Rodríguez (Universidad de Málaga, Departamento de Arquitectura de Computadores) : SIMD instructions & range reduction architectures.
Résumé. This speech is divided in two well differentiated parts:
On one hand, we will see some new SIMD instructions which have been devised in order to work in conjunction with existing multimedia extensions like MMX or 3DNow!, among others. These new instructions are aided by a specialized look-up table in their purpose to improve computation performance for multimedia applications.
On the other hand, we will also see an example of adapting an ASIC architecture for a range reduction calculation into another architecture intended to be implemented into an FPGA. We will have an overview of the specific range reduction algorithm we are going to implement and how can we change the ASIC architecture looking for an efficient FPGA implementation by: (a) using hardware components which better suits into an FPGA, and (b) making a low level design and placing those components at the best places for a particular FPGA.

Vendredi 27 juin 2008 à 10h15, salle du conseil du LIP. Exposé de Ned Nedialkov (McMaster University, Canada) : An overview on interval methods for ordinary differential equations.
Résumé. An interval method for initial value problems (IVPs) in ordinary differential equations (ODEs) has two important advantages over approximate ODE methods: when it computes a solution to an ODE problem, it (1) proves that a unique solution exists and (2) produces rigorous bounds that are guaranteed to contain it. Such bounds can be used to ensure that this solution satisfies a condition in a safety-critical calculation, to help prove a theoretical result, or simply to verify the accuracy and reliability of the results produced by an approximate ODE solver.
We overview interval methods and software for IVP ODEs, discuss applications of these methods, and present the author's interval ODE solver VNODE-LP.
Computing rigorous bounds in IVPs for differential-algebraic equations (DAEs) is a substantially more challenging task than in ODEs. A promising approach is Pryce's structural analysis combined with Taylor series methods. We outline this approach and discuss recent developments.

Vendredi 13 juin 2008 à 10h15, salle B1 (4ème étage). Exposé de Frédéric Messine (ENSEEIHT-IRIT) : Optimisation Globale basée sur l'Arithmétique d'Intervalles et l'Arithmétique Affine.
Résumé. L'analyse d'intervalles est un outil introduit par R.E. Moore en 1966 pour contrôler les erreurs numériques générées par les calculs flottants sur ordinateur. Depuis les années 1980, cet outil est largement utilisé avec des méthodes de type Branch and Bound pour la résolution de problèmes d'optimisation globale continus avec ou sans contraintes. Dans cet exposé, je présenterai diverses techniques dérivées de l'arithmétique d'intervalles pour calculer des bornes d'une fonction considérée sur un hypercube. Notamment l'arithmétique affine et ses extensions seront exposées en détail. Je montrerai comment ces techniques peuvent être utilisées avec efficacité pour résoudre des problèmes sans contrainte. Dans le cas de problèmes avec contraintes, j'exposerai les principes de propagation de contraintes issues des CSP (Constrained Satisfaction Programming) continus et je montrerai leur impact sur un exemple industriel simple. Très récemment, nous avons utilisé l'aritmétique affine dans les problèmes avec contraintes afin de générer automatiquement des programmes linéaires relâchés et dont la résolution par C-Plex donne des bornes très précises du problème primal considéré. Je conclurai en présentant des premiers résultats numériques de cette nouvelle technique de reformulation linéaire.

Vendredi 6 juin 2008 à 10h15, salle du conseil du LIP. Exposé d'Ivan Morel : D'une base LLL-réduite à une autre.
Résumé. La réduction de réseaux a d'importantes applications dans divers domaines aussi bien en mathématiques qu'en informatique : algèbre computationnelle, cryptologie, théorie algorithmique des nombres, communications, arithmétique des ordinateurs, etc. L'algorithme LLL permet de réduire une base quelconque d'un réseau en une 'bonne' base en temps polynomial. Cependant la qualité de la base obtenue dépend directement d'un paramètre auxiliaire : delta (le facteur 3/4 de l'algorithme original). Comme présenté par LaMacchia dans sa thèse, une technique intéressante de réduction consiste à réduire la base avec un delta petit (de manière à obtenir une réduction aussi rapide que possible), puis à augmenter la valeur de delta afin d'obtenir la qualité maximale atteignable par LLL. Je présenterai ainsi un algorithme qui améliore la qualité d'une base LLL- réduite en augmentant la valeur de delta, dont la complexité, de même exposant global que celle de l'algorithme LLL, est essentiellement indépendante de la taille binaire des coordonnées.

Jeudi 15 Mai 2008 à 14h30, salle du conseil du LIP. Exposé de Siegfried M. Rump (Institute for Reliable Computing, Hamburg University of Technology) : Computer-assisted proofs and self-validating methods.
Résumé. Methods will be discussed how the computer can aid in mathematical proofs or, more general, how undoubtedly true results can be obtained with the aid of digital computers. In particular we will discuss methods from computer algebra and so-called self-validating methods. The latter can be accessed via INTLAB, the Matlab toolbox for reliable computing. If time permits, some demonstration will be given.

Mercredi 30 avril 2008 à 10h15, salle du conseil du LIP. Exposé de Nicolas Louvet : Algorithmes compensés pour l'évaluation de polynômes.
Résumé. Comment améliorer la précision d'un résultat calculé en arithmétique flottante, tout en conservant de bonnes performances pratiques ? La compensation des erreurs d'arrondis commises par un algorithme en arithmétique flottante est l'une des approches permettant de répondre à cette question récurrente. Dans cet exposé, je passerai en revue les différents résultats que nous avons obtenus concernant l'évaluation de polynômes par des algorithmes compensés. Je présenterai également une étude du parallélisme d'instructions présent dans le schéma de Horner compensé, étude qui permet d'en expliquer les bonnes performances pratiques.

Vendredi 25 avril 2008 à 10h15, salle du conseil du LIP. Exposé de Guillaume Melquiond (Projet Composants Mathématiques, Laboratoire INRIA-Microsoft Research) : L'arithmétique flottante comme outil de preuve formelle.
Résumé. Dans certains systèmes formels, les mécanismes de conversion et de réflexion permettent l'évaluation "rapide" de fonctions et l'utilisation de leur valeurs au sein de preuves. Ces mécanismes peuvent alors remplacer avantageusement l'approche déductive traditionnelle en substituant des calculs aux applications de théorème.
Afin d'adapter cette approche aux preuves manipulant des nombres réels, une bibliothèque d'arithmétique flottante a été développée pour l'assistant de preuves Coq. Elle fournit les opérateurs arithmétiques de base et quelques fonctions élémentaires, le tout en multi-précision et en base quelconque. Les calculs sont effectifs et réalisés au sein du formalisme de Coq.
Une bibliothèque d'arithmétique d'intervalles a été construite par dessus. En conjonction avec des méthodes de différentiation, elle offre à l'utilisateur des tactiques Coq permettant de prouver automatiquement des inégalités sur des expressions à valeurs réelles.

Vendredi 18 avril 2008 à 10h15, salle du conseil du LIP. Exposé de Nicolas Meloni (Groupe de Recherche en Informatique et Mathématiques, Université de Toulon) : Chaînes d'additions différentielles et multiplication de point sur les courbes elliptiques.
Résumé. Depuis leur introduction au milieu des années 80, les courbes elliptiques sont devenues l'un des principaux outils de la cryptographie moderne. La principale opération (en termes de temps de calcul) de tout protocole utilisant les courbes elliptiques est la multiplication de point par un scalaire: le calcul de k*P=P+...+P, où k est un entier et P un point de la courbe. Afin d'effectuer cette opération de la manière la plus efficace possible, de nombreuses méthodes ont été proposées. Elles reposent, en général, sur l'algorithme dit "double-and-add" consistant à effectuer des séries de doublements entrecoupées d'additions, en fonction de la représentation binaire du scalaire k.
Dans cet exposé nous allons sortir des sentiers battus en nous intéressant à des méthodes de multiplication de point basées sur les chaînes d'additions différentielles. Celles-ci ont la particularités d'être principalement composées d'additions (au lieu de doublements), entrainant un plus grand nombre d'étapes de calcul, compensé par le fait qu'il est possible d'obtenir, sous certaines conditions, une addition plus efficace qu'un doublement. Nous verrons que cette approche apparait comme très prometteuse de prime abord, mais que certains problèmes (concernant la taille des chaînes notamment) restent à résoudre afin d'envisager une utilisation concrête.

Vendredi 11 avril 2008 à 10h15, salle du conseil du LIP. Exposé de David Defour (Laboratoire ELIAUS, Équipe DALI, Université de Perpignan). Gestion des threads dans le G80 et le R600 et évaluation polynomiale dans l'unité de filtrage.
Résumé. Les processeurs graphiques ou GPU sont composés, au sein de ce que l'on appelle le pipeline graphique, de plusieurs unités spécialisées paramétrables et/ou programmables (vertex shader, pixel shader, interpolateur, unité de filtrage, ...). L'exploitation du pipeline graphique implique une gestion de plusieurs milliers de threads concurrents destinés à tirer parti du parallélisme de données présent naturellement dans les applications graphiques. Nous présenterons comment les architectures G80 de chez Nvidia et R600 d'AMD gèrent en matériel ces threads et les problèmes liés. Enfin nous verrons comment détourner un type d'unité spécialisé dans le filtrage de texture, pour évaluer en matériel un polynôme de degré 3.

Vendredi 4 avril 2008 à 10h15, salle du conseil du LIP. Exposé de Peter Kornerup (Dept. of Math. & Comp. Science, SDU/Odense University) : Correcting the Normalization Shift of Redundant Binary Representations
Résumé. An important problem in the realization of floating point subtraction is the identification of the position of the first non-zero digit in a radix represented number, since the significand usually is to be represented left normalized in the part of the word(s) allocated for representing its value. There are well-known log-time algorithms for determining this position for numbers in non-redundant representations, which may also be applied to suitably (linear-time) transformed redundant representations. However, due to the redundancy in the latter case the position thus determined may need a correction by one. When determination of the shift amount is to be performed in parallel with conversion to non-redundant representation (the subtraction), it must be performed on the redundant representation. This is also the case when the significand is to be retained in a redundant representation until the final rounding. This talk presents an improved algorithm for determining the need for a correction of the normalization shift amount, which can be run in parallel with the algorithm finding the ``approximate'' position.

Vendredi 28 mars 2008 à 10h15, salle du conseil du LIP. Exposé de Nathalie Revol : Adaptation automatique de la précision de calcul.
Résumé. Lorsqu'un calcul donné ne fournit pas le résultat avec la précision voulue, on peut effectuer ce calcul (soit le recommencer, soit le poursuivre) avec une précision plus grande. Une question qui se pose alors tout naturellement est de savoir comment augmenter la précision de calcul afin de minimiser le surcoût en temps de calcul. La base de la comparaison est le temps du calcul effectué en supposant que l'on utilise la précision optimale requise.
Kreinovich et Rump ont montré que lorsque l'on recommence complètement les calculs, alors le surcoût minimal est un facteur 4. Dans cette présentation, nous étudierons le cas où le calcul peut se poursuivre en utilisant des résultats obtenus avec une précision inférieure. Nous montrerons tout d'abord que l'on peut obtenir un surcoût inférieur à 4 dans un tel cas : par exemple le surcoût est de 2 pour l'algorithme de Newton. Ensuite nous présenterons une stratégie asymptotiquement optimale pour adapter la précision de calcul dans ce cas où les résultats précédents peuvent être réutilisés, qui a un surcoût qui tend vers 1 lorsque la précision optimale (inconnue a priori) tend vers l'infini.

Mercredi (attention, ce n'est pas un vendredi) 26 mars 2008 à 10h15, salle du conseil du LIP. Exposé de Thomas Plantard (University of Wollongong, Australia). Cryptographie basée sur CVP en norme infinie.
Résumé. In Crypto 1997, Goldreich, Goldwasser and Halevi (GGH) proposed a lattice analogue of McEliece public key cryptosystem, which security is related to the hardness of approximating the closest vector problem (CVP) in a lattice. Furthermore, they also described how to use the same principle of their encryption scheme to provide a signature scheme. Practically, this cryptosystem uses the euclidean norm, Euclidean norm, which has been used in many algorithms based on lattice theory. Nonetheless, many drawbacks have been studied and these could lead to cryptanalysis of the scheme. We present a novel method of reducing a vector under the max-norm and propose a digital signature scheme based on it. Our scheme takes advantage of the max-norm to increase the resistance of the GGH scheme and to decrease the signature length.

Vendredi 14 mars 2008 à 10h15, salle du conseil du LIP. Exposé de Vincent Lefèvre : Approximation d'une fonction f par des polynômes pour le calcul approché des valeurs successives f(0), f(1), f(2)...
Résumé. Je présenterai comment approcher efficacement une fonction f par des polynômes en vue d'en calculer les valeurs approchées successives f(0), f(1), f(2)..., pour un très grand nombre d'arguments (par exemple, 2^40). Pour que le calcul soit rapide, le degré des polynômes doit être petit (et même en pratique égal à 1 pour l'application visée, qui est la recherche des pires cas pour l'arrondi correct de la fonction). Mais pour que le temps total de calcul des approximations ne soit pas trop grand, il faut que les intervalles d'approximation soient grands. Je montrerai comment satisfaire ces deux contraintes a priori contradictoires. Je montrerai également comment représenter les coefficients approchés, décrirai l'arithmétique utilisée, et donnerai des exemples obtenus en pratique.

Vendredi 7 mars 2008 à 10h15, salle 117 (attention, ce n'est pas la salle du conseil). Exposé de Florent de Dinechin : Autour de la multiplication par une constante, présentation du projet FloPoCo.
Résumé. Nos travaux sur FPLibrary ont montré les limites du langage VHDL pour décrire des opérateurs matériels complexes, notamment des fonctions élémentaires. Depuis quelques années, on écrit des générateurs de VHDL. FloPoCo (pour Floating-Point Cores) est une tentative de ramener dans un seul cadre logiciel tous ces prototypes de générateurs que nous avions à droite ou à gauche: HOTBM, les générateurs d'exp et de log par réduction d'argument itérative, etc. Au passage, on va y ajouter de nouveaux opérateurs. Je prendrai l'exemple de la multiplication par une constante entière, flottante ou même réelle.

Vendredi 29 février 2008 à 10h15, salle du conseil du LIP. Exposé d'Olivier Bouissou (LIX, CEA Saclay) : Utilisation de l'intégration garantie pour la vérification de systèmes hybrides.
Résumé. La présence sans cesse croissante de programmes informatiques (i.e. de systèmes discrets) dans les systèmes embarqués (i.e. communicant avec un environnement continu) a rendu nécessaire l'étude et l'analyse de systèmes hybrides. Dans cet exposé, nous expliquerons comment on peut étendre l'analyse statique classique de programmes pour les systèmes hybrides en prenant en compte ses interactions avec le milieu continu.
Pour analyser la partie continue, il est nécessaire de calculer des bornes garanties sur les solutions d'équations différentielles. La théorie de l'intégration garantie apporte les outils nécessaires pour cela. Nous présenterons les principes généraux qui fondent cette théorie puis nous décrirons en détail la méthode GRKLib, un nouvel algorithme basé sur la méthode de Runge-Kutta d'ordre 4. Nous insisterons notament sur les techniques utilisées pour prouver la correction de la méthode en présence de nombres flottants. Enfin, nous comparerons GRKLib à VNODE, l'outil d'intégration garantie le plus utilisé.

Vendredi 15 février 2008 à 10h15, salle du conseil du LIP. Exposé de Claude-Pierre Jeannerod : Algorithmes parallèles pour l'évaluation précise de certaines fonctions algébriques.
Résumé. Dans cet exposé, je présenterai une approche relativement uniforme pour l'évaluation avec arrondi correct des fonctions algébriques de base : inversion, division, racines k-ièmes et leurs inverses. Cette approche, qui repose sur l'évaluation de polynômes bivariés particuliers, permet d'exprimer davantage de parallélisme que les approches plus classiques, à base d'itérations ou de polynômes univariés. En pratique, on verra que cela peut conduire à des algorithmes d'évaluation polynomiale à la fois efficaces et suffisamment précis pour garantir l'arrondi correct des fonctions en question.

Vendredi 8 février 2008 à 10h15, salle du conseil du LIP. Exposé de Nicolas Julien (Marelle, INRIA Sophia) : Arithmétique réelle exacte certifiée.
Résumé. La co-induction en Coq fournit un cadre de travail confortable pour décrire des algorithmes certifiés pour l'arithmétique réelle exacte. La bibliothèque que nous décrivons s'inspire d'expériences précédentes utilisant des séquences infinies de chiffres redondants en base 2 et les généralise par l'utilisation de bases entières arbitraires. L'objectif est de pouvoir utiliser les opérations rapides des entiers natifs et de fournir ainsi des calculs efficaces sur les nombres réels à l'interieur du système Coq.
Nous décrirons la représentation utilisée ainsi que quelques algorithmes, en particulier une technique de calcul des series entières convergentes.

Vendredi 1er février 2008 à 10h15, salle du conseil du LIP. Exposé de Sylvie Boldo (ProVal, INRIA Saclay - Île-de-France) : Annotations flottantes et applications.
Résumé. Dans cet exposé, je présenterai la plate-forme Why et l'outil Caduceus permettant de spécifier précisément un programme. Ces spécifications ont pour but d'être transformées en obligations de preuves. Une fois prouvées, cela garantit la validité de la spécification du programme.
Je montrerai la syntaxe des annotations flottantes visant à spécifier les programmes utilisant les calculs flottants. Ces annotations seront ensuite utilisées sur quelques applications.

Vendredi 18 janvier 2008 à 10h15, salle du conseil du LIP. Exposé de Jean-Michel Muller : Devisons sur la division.
Résumé. Plusieurs itérations utilisées pour implanter la division (itérations de Newton-Raphson, de Goldschmidt, de Markstein...) sont équivalentes en théorie (on passe de l'une à l'autre par un changement de variable simple), mais ont un comportement numérique très différent. On discutera des avantages et inconvénients de chaque itération, en proposant des stratégies consistant à passer de l'une à l'autre au cours du calcul.

Vendredi 21 décembre 2007 à 10h15, salle de conférences de l'IXXI. Exposé de Sylvain Chevillard et Serge Torres : Synthèse de bons approximants polynomiaux sous contraintes.
Résumé. Lorsqu'on évalue une fonction en logiciel ou en matériel, on a très fréquemment recours à de bonnes approximations (au sens de la norme sup dans notre contexte) polynomiales de ces fonctions. On impose en général certaines contraintes à leurs coefficients telles qu'un nombre de bits imposé pour leur taille, un format particulier ou des valeurs fixées pour certains coefficients. Dans cet exposé, on présentera un processus général, utilisant des outils de réduction de réseaux euclidiens et de programmation linéaire, permettant de déterminer efficacement de bonnes approximations sous contraintes et visant à montrer que les approximations produites sont très proches de l'optimal (que l'on pourra déterminer dans certains cas). Notre méthode sera illustrée par plusieurs exemples.

Jeudi 20 décembre 2007 à 10h15, salle du conseil du LIP. Exposé de David Monniaux (CNRS, VERIMAG, Univ. Grenoble 1) : Analyse statique de programmes en virgule flottante.
Résumé. Des programmes comportant des calculs en virgule flottante sont maintenant utilisés dans des applications critiques. Nous évoquerons comment on peut donner de ces programmes une sémantique correcte et comment approximer cette sémantique. Nous finirons par des techniques (encore en cours de développement) sur la génération mécanisée d'analyseurs.

Vendredi 14 décembre 2007 à 10h15, salle du conseil du LIP. Exposé de Jean-Claude Bajard (LIRMM, Univ. Montpellier 2) : Comment accommoder les restes.
Résumé. Les systèmes de représentation basés sur les restes modulaires offrent des caractéristiques intéressantes pour certaines applications comme la cryptographie. Nous montrons comment les utiliser sur les corps finis.
Dans le cadre des corps "premiers" (GF(p)), nous retrouvons l'arithmétique modulaire pour laquelle les Residue Number Systems, systèmes basés sur le théorèmes des restes chinois, offrent une alternative intéressante autant sur le plan des performances que sur celui de la robustesse aux fuites.
En ce qui concerne, les corps finis définis comme des extensions (GF(p^k)), nous avons plusieurs possibilités: si p > 2k, nous pouvons utiliser des systèmes basés sur l'interpolation de Lagrange, sinon, comme en caractéristique 2 (GF(2^k)), nous retrouvons des systèmes plus directement inspirés des RNS.

Vendredi 7 décembre 2007 à 10h15, salle du conseil du LIP. Exposé de Thibault Hilaire (R2D2, IUT de Lannion) : Implémentation de filtres/régulateurs : à la recherche d'une réalisation optimale.
Résumé. On s'intéresse ici à la mise en oeuvre numérique d'une loi de contrôle/commande (filtre ou régulateur, linéaire à paramètres invariants dans le temps) dans un calculateur, sous contrainte de précision. En effet, les ressources et puissances limitées des "calculateurs" imposent que les calculs soient de précision finie et souvent très limitée, et le processus d'implémentation amène de nombreuses dégradations de la loi, tant temporelles que numériques. Ces dernières ont pour origine les bruits de quantification dans les calculs et la quantification des coefficients.
La dégradation dépend de la précision allouée à chaque élément de calcul et est très fortement liée au choix de la réalisation (algorithme mis en oeuvre pour calculer les sorties en fonctions des entrées) : en effet, de nombreuses réalisations, toutes équivalentes en précision infinie, existent (formes directes, treillis, espace d'état, avec opérateur retard, opérateur delta, décomposition en cascade, en parallèle, etc... ) mais leur robustesse à l'implémentation diffère.
Après avoir montré sur un exemple différentes structures d'algorithmes possibles, ainsi qu'un formalisme pour les représenter algébriquement, je présenterai différentes mesures permettant d'évaluer l'impact général de l'implémentation (impact sur la fonction de transfert, sur les poles du systèmes, en boucle ouverte et en boucle fermée, et aussi la puissance de l'erreur de sortie) :
- tout d'abord, des mesures de "sensibilité" (sans préjuger de l'implémentation réelle) adapté au contrôle/commande
- ensuite, dans le cadre d'une implémentation virgule fixe (schéma d'implémentation particulier), ces mesures sont affinées (il serait aussi possible d'adapter cela à la virgule flottante). Enfin, le problème de recherche de réalisation optimale (et réalisation structurée optimale) sera exhibé (recherche de la réalisation, parmi toutes réalisations équivalentes, qui minimise une de nos mesures) et traité sur un exemple.

Mercredi 28 novembre 2007 à 17h15, salle du conseil du LIP. Exposé de Clément Pernet (Symbolic Computation Group, Univ. Waterloo, Canada) : Algèbre linéaire dense dans des petits corps finis : théorie et pratique.
Résumé. Depuis l'introduction du produit matriciel de complexité sous-cubique, des algorithmes par bloc ont été conçus pour réduire la complexité de la plupart des problèmes classiques d'algèbre linéaire à celle du produit de matrice : O(n^w). Cependant, jusqu'à récemment, le meilleur algorithme pour le calcul du polynôme caractéristique exigeait un nombre logarithmique de produits matriciels, impliquant une complexité de O(n^w log n) opérations dans le corps de base. Nous présenterons un nouvel algorithme probabiliste de type Las Vegas, calculant le polynôme caractéristique dans un corps suffisamment grand. Grâce à un nouveau type de réduction, il atteint la complexité O(n^w).
Les réductions au produit matriciel sont par ailleurs d'un grand intérêt pratique car elles permettent l'utilisation d'implantations particulièrement efficaces pour cette opération (combinant optimisation de cache, algorithme sous-cubique,...). Nous présenterons quelques aspects des techniques mises en oeuvre pour le développement de la bibliothèque FFLAS-FFPACK d'algèbre linéaire dense dans un corps fini : un schéma de réduction efficace en temps et en mémoire pour les formes triangulaires et échelonnées, ainsi qu'une étude d'ordonnancements efficaces en mémoire pour l'algorithme de Strassen-Winograd.
Dans ce contexte, une implémentation du nouvel algorithme de calcul du polynôme caractéristique permet d'améliorer radicalement les temps de calcul des meilleures implantations existantes.

Lundi 5 novembre 2007 à 10h15, salle du conseil du LIP. Exposé de Christophe Doche (Centre for Advanced Computing - Algorithms and Cryptography, Macquarie University) : DBNS et cryptographie sur courbes elliptiques.
Résumé. nous présentons le DBNS (Double-Base Number system) et ses applications à la cryptographie, en particulier pour accélérer la multiplication scalaire sur courbes elliptiques.
Après une brève introduction, nous détaillerons 2 applications pratiques :
* un algorithme de multiplication scalaire rapide pour des courbes génériques lorsque des précalculs sont autorisés.
Ce travail repose sur le concept de DBNS étendu qui est une généralisation naturelle du DBNS.
* le premier algorithme de multiplication scalaire de complexité sous-linéaire. Cette méthode exploite une généralisation du DBNS aux courbes de Koblitz.

Lundi 29 octobre 2007 à 10h15, salle du conseil du LIP. Exposé de Guillaume Hanrot (CACAO, LORIA, INRIA Nancy - Grand Est) : Aspects arithmétiques de la méthode de scindage binaire
Résumé. La méthode de scindage binaire est une technique pour calculer efficacement des approximations de la somme de séries Σ_{n
≥ 0} a(n) s(n), où s(n) est un polynôme à coefficients entiers et a(n) est hypergéométrique, i.e. a(n+1) / a(n) est une fraction rationnelle en n à coefficients entiers.
L'idée est, plutôt que d'ajouter les termes de la série un par un, de décomposer la série tronquée en moitié haute et moitié basse, et on recommence récursivement, obtenant ainsi la somme partielle sous forme fractionnaire. Une difficulté consiste à éliminer les facteurs communs entre numérateur et dénominateur au cours de l'algorithme, pour éviter une croissance inutile des entiers manipulés. Nous expliquerons comment cela peut se faire et dans quels cas cela a un intérêt.

Vendredi 12 octobre 2007 à 10h15, salle du conseil du LIP. Exposés d'Ivan Morel, Estimation de complexité en calcul certifié et Hong Diep Nguyen, Calcul scientifique précis et efficace sur le processeur CELL.
Résumé de l'exposé d'Ivan Morel. Les calculs effectués en multiprécision étant extrêmement coûteux, une alternative intéressante est de calculer un résultat approché et une borne d'erreur certifiant ce résultat. On s'intéressera donc au problème de la complexité de la certification en algèbre linéaire, et je présenterai les différents résultats obtenus jusqu'a présent dans ce domaine : les résultats théoriques de Demmel, Diament et Malajovich ainsi que les techniques introduites par Rump pour développer des algorithmes auto-certifiés (ce sont des algorithmes qui calculent à la fois une approximation et une certification, dans le but de dissimuler le coût de la certification). Enfin je présenterai un certificat pour la décomposition QR et l'implémentation que j'ai réalisée en MatLab de ce certificat.
Résumé de l'exposé de Hong Diep Nguyen. Le thème de mon stage de M2 était l'implémentation d'opérateurs à virgule flottante en précision étendue sur le processeur CELL. Ce processeur permet d'atteindre plus de 200 GFLOPs en simple précision mais avec uniquement un mode d'arrondi vers zéro et quelques autres restrictions par rapport à la norme IEEE 754. La simple précision ne permet pas toujours résoudre tous les problèmes numériques, il est nécessaire d'utiliser des précisions étendues sur 64, 128 ou 256 bits.
Je présenterai les travaux que j'ai réalisé pendant ce stage : j'ai développé une bibliothèque double simple précision et une bibliothèque quad simple précision sur le modèle de la bibliothèque proposée par Yozo Hida et al. L'implémentation était réalisée en exploitant des caractéristiques spécifiques du processeur CELL, dont les plus importants sont le processeur SIMD, le jeu d'instructions complètement pipelinées en simple précision et la fonction FMA.
L'exposé se terminera par une étude des performances et des précisions respectives de ces deux bibliothèques. Les résultats obtenus permettent de constater que les bibliothèques implémentées double-simple et quad-simple sont précises à 42 bits et à 94 bits respectivement. La performance de crête du double-simple est de 2.56 GFLOPs, cependant la performance de crête du quad-simple est de 206 MFLOPs.
Notre travail atteindra son objectif lorsque le consortium IBM, Toshiba, Sony proposeront un processeur CELL avec un SIMD 64 bits. On pourra alors atteindre la précision étendue à 256 bits.

Vendredi 5 octobre 2007 à 10h15, salle 116. Réunion EVA-Flo. Démonstration de arenaireplot par Christoph Lauter
et Illustration des premiers échanges en format XML par Nicolas Jourdan.

Vendredi 28 septembre 2007, 14h30, salle des thèses. Soutenance de thèse de Francisco José Cháves : Utilisation et certification de l'arithmétique d'intervalles dans un assistant de preuves.
Résumé. De plus en plus de calculs de surveillance, contrôle etc. sont effectués de façon logicielle. Notre objectif est de prouver formellement des calculs numériques qui offrent déjà un premier niveau de garantie sur leurs résultats, comme des calculs par intervalles, et en particulier des calculs avec des modèles de Taylor. Cette thèse présente la construction d'une bibliothèque de modèles de Taylor pour l'assistant de preuves PVS. Nous avons développé les modèles de Taylor pour les opérations d'addition, soustraction, multiplication par un scalaire, multiplication, élévation au carré, puissance et racine carrée. Nous avons également développé les modèles de Taylor pour l'exponentielle, le sinus, l'arctangente et les sinus et cosinus hyperboliques. Nous avons demontré dans PVS que les opérations et fonctions définies dans notre bibliotheque préservent la propriété d'inclusion, travail de preuve qui n'avait pas été fait auparavant dans les implantations des modèles de Taylor. Nous avons développé une stratégie PVS pour certifier des inégalités ou bornes d'expressions. Quand on utilise un assistant de preuves pour démontrer une inégalité il peut être nécessaire de guider l'assistant pas à pas dans la démonstration. Pour cette raison, les utilisateurs effectuent rarement la démonstration. Donc, simplifier la façon de prouver les inégalités et bornes d'expressions facilite l'utilisation de PVS.

Lundi 24 septembre 2007 à 14h, salle du conseil du LIP. Exposé de Damien Stehlé : Énumération de vecteurs courts dans un réseau euclidien.

Lundi 24 septembre 2007 à 11h, salle du conseil du LIP. Exposé de Cong Ling (Imperial College, Londres, Royaume-Uni) : Lattice Decoding for Digital Communications: Where Minkowski Meets Shannon.

2006-2007

Jeudi 28 juin 2007, 14h, amphi A. Soutenance d'habilitation à diriger des recherches de Florent Dupont de Dinechin : Matériel et logiciel pour l'évaluation de fonctions numériques. Précision, performance et validation.
Ce mémoire reprend quelques résultats obtenus entre 2000 et 2007 au sein du projet Arénaire du LIP. La problématique centrale est l'évaluation de fonctions numériques : étant donnée une fonction réelle, par exemple un polynôme, un sinus, une exponentielle ou toute autre fonction utile, il s'agit de construire un opérateur pour l'évaluer. Pour cela, on dispose de quelques règles du jeu et de quelques briques de bases: pour le matériel, on peut utiliser, avec un parallélisme arbitraire, des additions et multiplications entières et des tables précalculées. Pour le logiciel, on dispose en plus d'opérateurs de calcul en virgule flottante, mais avec un modèle d'exécution séquentiel. Dans les deux cas, on est contraint à des approximations dont on cherche à minimiser l'erreur. La question de la précision, notamment des calculs intermédiaires, est ici intimement liée à celle de la performance. Pour gérer tous ces paramètres et obtenir des implémentations de qualité, il faut de plus en plus d'automatisation. De plus, pour que cette qualité soit garantie, il faut se rapprocher du monde de la preuve formelle. Ces différents aspects seront évoqués, ainsi que des applications de ces travaux aux accélérateurs de calcul reconfigurables et à la normalisation de la virgule flottante.

Jeudi 28 juin 2007, 9h30, amphi A. Soutenance de thèse de Nicolas Veyrat-Charvillon : Opérateurs arithmétiques matériels pour des applications spécifiques.
Résumé. L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Ma thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions pour des applications spécifiques en traitement du signal et des images et en cryptographie. Une partie de mes travaux porte sur des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. J'étudie aussi la génération automatique d'opérateurs à base d'additions et décalages (type SRT) pour l'évaluation de certaines fonctions algébriques. Enfin, j'ai eu l'occasion de travailler sur une implantation efficace et compacte des fonctions de hachage cryptographique de la famille SHA-2. Les différents opérateurs proposés ont tous été validés sur des circuits FPGA.

Mardi 19 juin à 15h30. Exposé de J.-L. Beuchat (Univ. Tsukuba, Japon) : Arithmetic Operators for Pairing-Based Cryptography .
Résumé : Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area. In this talk, we first describe an accelerator for the η_T pairing over F₃[x]/(x⁹⁷ + x¹²+2). Our architecture is based on a unified arithmetic operator which performs addition, multiplication, and cubing over F_3⁹⁷. This design methodology allows us to design a compact coprocessor (1888 slices on a Virtex-II Pro~4 FPGA) which compares favorably with other solutions described in the open literature. We then describe ways to extend our approach to any characteristic and any extension field.

Vendredi 8 juin 2007, 10h. Exposé de Octavian Cret et Lucia Vacariu, de l'université technique de Cluj-Napoca, Roumanie : Calcul reconfigurable pour une application biomédicale.

Vendredi 27 avril 2007 de 15h30 à 16h30. Exposé de G. Revy : Racine carrée simple précision sur un processeur entier.

Mercredi 11 et jeudi 12 avril 2007. Première réunion EVA-Flo avec toutes les équipes partenaires : Arenaire, Dali, Fluctuat, Tropics.

Vendredi 6 avril 2007 de 13h30 à 15h30. Exposé de G. Villard, ou alors discussion suite à l'exposé de V. Lefèvre, dans le cadre d'EVA-Flo.

Vendredi 23 mars 2007 de 13h30 à 15h30. Exposé de V. Lefèvre dans le cadre d'EVA-Flo.

Vendredi 9 mars 2007 de 15h30 à 17h00. Exposé de Claus Schnorr (Universite de Francfort): "Hot Topics on LLL and Lattice Basis Reduction".

Vendredi 8 février 2007 de 15h30 à 17h00. Exposé de C. Lauter et S. Chevillard sur leur outil "arenaire tools".

Vendredi 19 janvier 2007 de 13h30 à 15h00. Groupe de travail "EVA-Flo" : estimation et majoration d'erreur, en salle de conseil du LIP. Suite du tour de table.

Jeudi 21 décembre 2006 à 13h00. Exposé: Florent de Dinechin "Du matériel pour logarithme et exponentielle en virgule flottante", en salle de conseil du LIP.

Vendredi 20 octobre 2006 à 13h30. Groupe de travail "EVA-Flo" : estimation et majoration d'erreur.

Mercredi 18 octobre 2006 à 13h30. Groupe de travail "Norme infinie" (présentations de S. Chevillard et C. Lauter) suivi du groupe de travail "Remez".

2005-2006

Vendredi 17 février 2006. Exposé : Francisco Cháves "A library of Taylor Models for PVS automatic proof checker".

Vendredi 21 octobre 2005. Exposé : Christoph Quirin Lauter "Procédures de calcul pour un format triple double".

2004-2005

Jeudi 21 avril 2005. Exposé : Saurabh Kumar Raina "Bibliothèque virgule flottante pour processeurs entiers".

Mercredi 13 avril 2005. Exposé : Arnaud Tisserand "Petites approximations polynomiales avec des coefficients sur 3 bits et estimations des puissances de x".

Jeudi 16 décembre 2004. Exposé : Jean-Luc Beuchat et Jean-Michel Muller "Rn-codes : définitions et algorithmes d'addition, de multiplication et d'élévation au carré".

Jeudi 9 décembre 2004. Exposé : Guillaume Melquiond "When double rounding is odd".

Jeudi 25 novembre 2004. Exposé : Jérémie Detrey "Second order function approximation using a single multiplication on FPGAs".