Sur le calcul et la majoration de
la discrépance à l'origine

ERIC THIEMARD
Ecole Polytechnique Fédérale de Lausanne
Département de Mathématiques
CH - 1015 Lausanne

La discrépance est une mesure de la non-uniformité d'une séquence de points distribués dans un cube unité multidimensionnel. Cette grandeur est intéressante à bien des égards, mais sa détermination s'avère particulièrement délicate. Les nouveaux algorithmes proposés dans ce travail permettent de la calculer ou de la majorer dans des cas inaccessibles jusqu'alors.

En dehors de ces résultats, cette présentation ne se limite pas à l'énoncé de quelques définitions et propriétés classiques, mais discute également certaines implications pratiques du sujet. En effet, la notion de discrépance étant liée à de nombreuses autres disciplines, un important effort de synthèse a été consenti afin de mettre en perspective quelques-unes de ces connexions. La première partie de ce document est un tour d'horizon qui commence par une introduction à la théorie de l'équirépartition, une discipline vouée à l'étude du concept d'uniformité. Puis, après une brève description de la très populaire méthode de Monte-Carlo pour l'évaluation d'intégrales multiples, la version déterministe de cette technique est discutée plus en détail. Cette dernière repose sur l'utilisation de séquences de points particulièrement bien distribuées, les suites à discrépance faible, dont quelques exemples sont donnés à la fin de cette introduction.

La seconde partie de ce travail commence par la présentation des deux méthodes connues pour le calcul de la discrépance. La complexité de ces algorithmes est exponentielle et l'impraticabilité de l'un d'entre eux est illustrée numériquement. Apparemment, ces difficultés semblent contrebalancées par l'existence de majorations pour certains types de séquences. Hélas, le nombre minimal de points menant à l'obtention d'une borne non triviale par ce biais croît de manière exponentielle avec la dimension.

Nous proposons un nouveau principe permettant de calculer des bornes inférieures et supérieures pour la discrépance. La largeur maximale de l'intervalle en question pouvant être spécifiée a priori, cette approche permet d'atteindre une précision arbitraire. Cette construction repose sur la considération de partitions du cube unité en intervalles. Deux formes de décompositions sont envisagées. Tout d'abord, dans le cas particulier des grilles, il est possible d'établir des bornes pour des séquences de très grande taille en exploitant judicieusement cette structure. En revanche, pour un même effort de calcul, le second type de partition proposé permet d'obtenir des intervalles de meilleure qualité, mais uniquement pour des ensembles de points de cardinalité plus modeste. Dans les deux cas, des techniques de comptage multidimensionnelles spécialisées ont été développées. En fin de compte, dans de nombreuses situations, cette méthode est tout simplement la seule approche connue applicable.

Nous montrons ensuite que le calcul de la discrépance peut également se ramener à la résolution d'une famille d'instances d'un problème de géométrie combinatoire qui consiste à déterminer l'intervalle ancré à l'origine de volume minimal ou maximal contenant un nombre fixé de points d'une séquence donnée. Après avoir exprimé ces problèmes sous forme de programmes linéaires en nombres entiers, leur résolution est abordée à l'aide d'heuristiques et de techniques de génération de coupes et d'énumération par séparation et évaluation. De plus, nous proposons une approche pour traiter de manière implicite une partie importante des configurations impliquées. La méthode obtenue permet de calculer la discrépance de séquences dans des cas qui n'avaient jamais été atteints auparavant. D'autre part, comme le processus consiste en une suite d'améliorations apportées à un intervalle initial, il peut être interrompu à chaque instant, fournissant alors une borne inférieure et supérieure reflétant l'effort de calcul consenti jusque-là.

On peut regretter que les techniques proposées dans ce document mènent à des algorithmes qui ne sont pas polynomiaux. Toutefois, les résultats des expériences numériques effectuées montrent qu'elles permettent de traiter des cas qui, jusqu'alors, semblaient totalement hors de portée. Ajoutons que ces méthodes n'ont certainement pas encore atteint leur version définitive. En effet, l'approche algorithmique par calcul (ou amélioration) d'intervalles introduite dans ce travail est inédite et son développement ne demande qu'à être poursuivi. Ainsi, cette thèse inaugure une voie de recherche prometteuse pour le calcul et la majoration de la discrépance.

Pour plus d'information, contactez le professeur Tom Liebling (thomas.liebling@epfl.ch).