L'Arithmétique modulaire pour les prédicats géométriques
|
| L'Arithmétique modulaire pour les prédicats géométriques |
|
L'arithmétique modulaire permet d'effectuer des calculs exacts, à faible coût, pour certains types de calculs simples. Cela inclut la plupart des tests géométriques, qui ont besoin d'être effectués de manière exacte, en particulier les signes de déterminants et d'expressions polynomiales plus générales.
Le principe de base du calcul modulaire est le théorème des restes Chinois, qui énonce que pour calculer une expression entière, il suffit de la calculer modulo plusieurs entiers (premiers entre eux), les modulis. A partir des résidus du résultat, on peut retrouver sa valeur entière, mais aussi simplement son signe, de manière simple et efficace.
Le principal inconvénient de l'arithmétique modulaire est sa nature statique, qui nécessite d'avoir une borne sur le résultat pour être sûr de la consistence du calcul (on peut difficilement tester le dépassement de capacité en cours de calcul). Plus cette borne connue est petite, moins il y a de calculs à effectuer.
Nous avons développé un certain nombre d'outils efficaces pour traiter ces problèmes, et nous proposons une approche filtrée, c'est-à-dire un calcul approché en flottant, dont on calcule l'erreur, débouchant en cas de non-certitude, sur un calcul modulaire de l'expression, dont on connait une borne grâce au calcul d'erreur. Le travail théorique a été effectué en commun par Hervé Brönnimann, Ioannis Z. Emiris, Victor Pan et Sylvain Pion. Voir la bibliographie pour les détails.
Pour le moment, seuls les outils pour calculer sans filtre sont disponibles. Le but et maintenant de construire un compilateur automatique, produisant des tests géométriques exacts suivant ce schéma: filtre + calcul modulaire. Cette approche n'est pas forcément optimale dans tous les cas, mais elle a l'avantage d'être simple à mettre en oeuvre dans de nombreux tests géométriques usuels, car elle est suffisamment générale.
En ce qui concerne l'implantation, le package Modular contient des routines de calcul de signes de déterminants, ainsi que d'expressions polynomiales, utilisant l'arithmétique modulaire. Il est d'ores et déjà utilisable, pour calculer des signes de déterminants, en dimension quelconque avec des entrées entières de moins de 53 bits. Le travail à venir consiste à faire précéder le calcul modulaire d'un filtre flottant.
Ici les sources en C du package. Il compile une bibliothèque de fonctions, utilisables aussi en C++. La version courante est 2.4, datée du 4 Février 1998. Pour installer le package, il suffit de faire: "gunzip -c modular.tar.gz | tar xvf -" (ou plus simplement "tar zxvf modular.tar.gz", avec GNU-tar), puis lire les instructions du fichier README. Pour tout problème ou question, n'hésitez pas à contacter l'auteur par mail (Sylvain.Pion at sophia.inria.fr).
Consultez le papier accepté à la conférence ACM 1997 à Nice, ainsi que les transparents (en anglais) correspondant à la présentation de ce papier.