Quelles sont les raisons pour lesquelles les chercheurs en géométrie algorithmique préfèrent le modèle BSS / real-RAM?

Contexte

Le calcul sur des nombres réels est plus compliqué que celui sur des nombres naturels, puisque les nombres réels sont des objets infinis et qu'il existe un nombre incalculable de nombres réels. Par conséquent, les nombres réels ne peuvent être fidèlement représentés par des chaînes finies sur un alphabet fini.

Contrairement à la calculabilité classique sur les chaînes finies où différents modèles de calcul tels que: le calcul lambda, les machines de Turing, les fonctions récursives, ... se révèlent être équivalents (du moins pour la calculabilité sur les fonctions sur les chaînes), il existe différents modèles proposés pour le calcul nombres réels qui ne sont pas compatibles. Par exemple, dans le modèle TTE (voir aussi [Wei00]) qui est le plus proche du modèle classique de Turing, les nombres réels sont représentés à l'aide de bandes d'entrée infinies (comme les oracles de Turing) et il est impossible de décider de la comparaison. relations d'égalité entre deux nombres réels donnés (en quantité de temps finie). D'autre part dans les modèles BBS / real-RAM qui sont similaires au modèle de machine RAM, nous avons des variables qui peuvent stocker des nombres réels arbitraires, et la comparaison et l’égalité font partie des opérations atomiques du modèle. Pour cette raison et des raisons similaires, de nombreux experts affirment que les modèles BSS / RAM réelle ne sont pas réalistes (ne peuvent pas être mis en œuvre, du moins pas sur les ordinateurs numériques actuels) et préfèrent le TTE ou d'autres modèles équivalents au TTE comme un modèle théorique de domaine efficace. Modèle de Ko-Friedman, etc.

Si je comprends bien , le modèle par défaut de calcul qui est utilisé dans la géométrie computationnelle est le BSS (alias réel RAM modèle, voir [de BCSS98]).

Par ailleurs, il me semble que dans la mise en œuvre des algorithmes dans la géométrie algorithmique (par exemple, LEDA ), nous ne traitons que des nombres algébriques et qu’aucun objet ou calcul infini de type supérieur n’est impliqué (est-ce correct?). Donc, il me semble (probablement naïvement) que l'on peut également utiliser le modèle classique de calcul sur des chaînes finies pour traiter ces nombres et utiliser le modèle de calcul habituel (qui est également utilisé pour la mise en œuvre des algorithmes) pour discuter de l'exactitude et de la complexité. d'algorithmes.

Des questions:

Quelles sont les raisons pour lesquelles les chercheurs en géométrie algorithmique préfèrent utiliser le modèle BSS / real-RAM? (raisonne la géométrie de calcul spécifique pour l'utilisation du modèle BSS / real-RAM)

Quels sont les problèmes avec l'idée (probablement naïve) que j'ai mentionnée dans le paragraphe précédent? (en utilisant le modèle classique de calcul et en limitant les entrées aux nombres algébriques en géométrie algorithmique)

Addenda:

Il y a aussi le problème de la complexité des algorithmes, il est très facile de décider du problème suivant dans le modèle BSS / real-RAM:

$S$$T$
$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

Bien qu'aucun algorithme entier-RAM efficace ne soit connu pour le résoudre. Merci à JeffE pour l'exemple.

Les références:

1. Lenore Blum, Felipe Cucker, Michael Shub et Stephen Smale, "Complexity and Real Computation", 1998
2. Klaus Weihrauch, " Computable Analysis, An Introduction ", 2000

Tout d'abord, les géomètres calculateurs ne le considèrent pas comme un modèle BSS. Le modèle de RAM réelle a été défini par Michael Shamos dans sa thèse de doctorat de 1978 ( Computational Geometry ), qui a sans doute lancé le champ. Franco Preparata a révisé et étendu la thèse de Shamos dans le premier manuel de géométrie algorithmique, publié en 1985. La RAM réelle est également équivalente (à l' exception de l'uniformité; voir la réponse de Pascal! ) Au modèle d' arbre de calcul algébrique défini par Ben-Or en 1983. Blum Les efforts de, Shub et Smale ont été publiés en 1989, bien après que la real-RAM ait été établie, et ont été presque complètement ignorés par la communauté de la géométrie algorithmique.

La plupart des résultats (classiques) en géométrie algorithmique sont fortement liés à des problèmes de géométrie combinatoire , pour lesquels les hypothèses sur les coordonnées intégrales ou algébriques sont (au mieux) des distractions non pertinentes. En tant que natif, il semble tout à fait naturel de considérer des points, des lignes, des cercles, etc., comme des objets de première classe lorsqu’ils prouvent quelque chose, et donc tout aussi naturel lors de la conception et de l’analyse d’algorithmes permettant de calculer avec eux.

$p$$q$$q$$r$$q,r,s$$qr$$st$? Chacune de ces primitives est implémentée en évaluant le signe d'un polynôme de degré faible dans les coordonnées en entrée. (Ainsi, ces algorithmes peuvent être décrits dans le modèle d’arbre décisionnel algébrique plus faible .) Si les coordonnées d’entrée sont des entiers, ces primitives peuvent être évaluées exactement avec uniquement une augmentation constante du facteur facteur, et donc des durées d’exécution sur la RAM réelle et les valeurs correspondantes. les nombres entiers de RAM sont les mêmes.

Pour des raisons similaires, alors que la plupart des gens pensent sur les algorithmes de tri, ils ne se soucient pas ce qu'ils sont le tri, tant que les données proviennent d'un univers totalement ordonné et deux valeurs peut être comparé à temps constant.

La communauté a donc développé une séparation des préoccupations entre la conception d’algorithmes géométriques «réels» et leur mise en œuvre pratique; D'où le développement de packages tels que LEDA et CGAL. Même pour les personnes travaillant sur le calcul exact, il existe une distinction entre l' algorithme réel , qui utilise l'arithmétique réelle exacte dans le modèle sous-jacent, et la mise en œuvre , qui est forcée par les limitations par ailleurs non pertinentes des dispositifs informatiques physiques à utiliser le calcul discret.

$\times$

Il existe quelques algorithmes géométriques qui reposent réellement sur le modèle d'arbre de calcul algébrique et ne peuvent donc pas être mis en œuvre de manière précise et efficace sur des ordinateurs physiques. Un bon exemple est celui des chemins à liaisons minimales dans de simples polygones, qui peuvent être calculés en temps linéaire sur une RAM réelle, mais nécessitent un nombre quadratique de bits dans le cas le plus défavorable pour être représentés exactement. Un autre bon exemple est celui des découpages hiérarchiques de Chazelle , qui sont utilisés dans les algorithmes les plus efficaces connus pour la recherche de gamme simplex.. Ces découpes utilisent une hiérarchie d'ensembles de triangles, où les sommets des triangles à chaque niveau sont des points d'intersection de lignes traversant des arêtes de triangles aux niveaux précédents. Ainsi, même si les coordonnées en entrée sont des entiers, les coordonnées de sommet de ces triangles sont des nombres algébriques de degré non borné; Néanmoins, les algorithmes de construction et d'utilisation des découpes supposent que les coordonnées peuvent être manipulées avec précision en temps constant.

Voici donc ma réponse brève et impartiale: TTE, la théorie des domaines, Ko-Friedman et d’autres modèles de calcul «réaliste» de nombres réels abordent tous des problèmes auxquels la communauté de la géométrie algorithmique ne se soucie généralement pas. .

Il n'est pas tout à fait vrai que le modèle RAM / BSS réel est équivalent au modèle d'arbre de calcul algébrique. Ce dernier est plus puissant car un arbre de profondeur polynomial peut être de taille exponentielle. Cela laisse beaucoup de place pour coder des informations non uniformes. Par exemple, Meyer auf der Heide a montré que les arbres de décision algébriques (même linéaires) peuvent résoudre efficacement des problèmes difficiles, tels que la somme de sous-ensembles, mais que cela est (conjecturalement) impossible dans le modèle réel RAM / BSS.

Voici un commentaire sur l'excellente réponse de Jeff:

Des notions de condition, d'approximation et d'arrondi ont été proposées pour combler l'écart de complexité (combinatoire par rapport à continu) des algorithmes de programmation linéaire. La condition d'une instance problématique estime l'effet de petites perturbations de l'entrée sur la précision de la sortie. La notion de condition a été introduite pour la première fois par Alan Turing. Jim Renegar a introduit la notion de condition d'un programme linéaire.

L. BLUM, Calcul sur les réels: À la rencontre de Newton , AVIS DE L'AMS, VOLUME 51, NUMÉRO 9, (2004), 1024-1034

A. TURING, Erreurs d’arrondis dans les processus matriciels, Quart. J. Mech. Appl. Math. 1 (1948), 287-308

J. RENEGAR, Intégration des nombres de conditions dans la théorie de la complexité de la programmation linéaire, SIAM J. Optim. 5 (1995), 506-524

F. CUCKER et J. PEÑA, Algorithme primal-double pour la résolution de systèmes coniques polyhédraux avec une machine à précision finie, SIAM Journal on Optimization 12 (2002), 522–554.