UN DISQUE PLEIN EMPRUNTÉ REND L'ORDINATEUR PLUS RAPIDE

Certains problèmes sont économes en temps mais gourmands en mémoire, d’autres l’inverse. Pour quelques tâches de base, les théoriciens ont prouvé des limites dures à ce compromis : avec une petite mémoire de travail, on ne peut pas être rapide. Un nouvel article montre qu’une ressource étrange, une mémoire déjà pleine qu’il faut rendre intacte, fait sauter ces limites.

Le disque dur emprunté

Le modèle s’appelle le calcul catalytique, introduit en 2014 par Buhrman, Cleve, Koucký, Loff et Speelman. Un algorithme reçoit une minuscule mémoire propre, de l’ordre de log n bits pour une entrée de taille n, plus une immense mémoire sale, déjà remplie de données arbitraires qu’il n’a pas choisies. Il peut utiliser les deux comme il veut, mais quand il s’arrête, chaque bit de la mémoire sale doit être exactement comme avant.

Les auteurs reprennent l’image habituelle : on emprunte l’énorme disque dur d’un ami, plein de précieux souvenirs numériques, pour faire un calcul. On ne veut pas perdre un ami, donc on remet chaque bit en place à la fin.

Le modèle devait d’abord prouver qu’une telle mémoire ne sert à rien. Intuitivement, pour tout restaurer, il faut garder toute l’information, donc on ne libère jamais de place. Surprise : c’est l’inverse. Une mémoire pleine permet de résoudre des problèmes que personne ne sait résoudre avec la seule mémoire propre. Mais ces résultats portaient sur l’espace, et les algorithmes étaient extrêmement lents.

Plus rapide que ce qui est prouvé possible

Adelmo Morrison Orozco, Nathan Sheffield et Ryan Williams (MIT) s’intéressent maintenant à la vitesse. Avec une mémoire propre logarithmique et une quantité polynomiale de mémoire empruntée, ils donnent des algorithmes qui :

• trient une liste et calculent une transformée de Fourier discrète en temps n^(1+o(1)), presque linéaire ;
• multiplient des matrices en temps n^(ω+o(1)), aussi vite que la meilleure méthode connue avec une mémoire illimitée.

Sans le disque emprunté, il est démontré que le produit du temps et de la mémoire doit être au moins de l’ordre de n² pour le tri et la transformée de Fourier, et de n³ pour la multiplication de matrices. Ces algorithmes catalytiques atteignent donc des vitesses hors de portée de tout algorithme ordinaire à petite mémoire. Les auteurs parlent de première démonstration inconditionnelle que les algorithmes catalytiques surpassent leurs équivalents non catalytiques.

Basculer, lire, défaire

L’ingrédient clé est une courte astuce combinatoire. Supposons qu’un algorithme puisse faire basculer une portion de la mémoire empruntée entre une valeur inconnue τ et τ + x, où x est le résultat qui l’intéresse. Dans une grande table « auxiliaire », elle aussi empruntée, on ajoute 1 à un ensemble d’entrées bien choisi. L’entrée en position τ augmente d’un si et seulement si x appartient à un ensemble donné. Puis on rejoue chaque étape à l’envers, et le disque redevient comme avant, sauf le bout de réponse que l’on voulait.

En empilant cette astuce couche après couche, on évalue vite des circuits peu profonds. Les auteurs réécrivent ensuite les réseaux de tri, les transformées de Fourier rapides et la multiplication rapide de matrices sous forme de tels circuits. En arithmétique, seules les couches qui multiplient deux inconnues coûtent cher ; les couches purement linéaires sont presque gratuites.

Une comparaison équitable

Une objection : les limites classiques supposent qu’on écrit la réponse une seule fois, de gauche à droite, sur une bande de sortie séparée, alors que les algorithmes catalytiques écrivent leur réponse dans le disque emprunté. L’article y répond. Les auteurs montrent que leurs algorithmes peuvent écrire la réponse en deux passes sur une bande de sortie, et que, pour des algorithmes ordinaires, deux passes n’aident pas plus qu’une. Les limites s’appliquent donc toujours, et la séparation tient. Ils prouvent aussi qu’une seule passe ne suffit pas, même avec le disque emprunté : le tri bute alors sur la même barrière en n².

Une longue liste de bénéficiaires

Les mêmes outils donnent des algorithmes catalytiques rapides pour multiplier de grands entiers et des polynômes, compter les triangles et trouver des cliques dans des réseaux, détecter chemins et cycles, et rechercher des motifs de texte avec jokers. Leurs temps de calcul égalent, à de petits facteurs près, les meilleurs algorithmes connus qui disposent de toute la mémoire voulue. Dans chaque cas, la mémoire empruntée doit toujours revenir exactement comme elle a été prêtée.