Des informaticiens de l’ETH Zurich montrent que le hasard peut devenir un puissant outil de calcul lorsqu’il est utilisé avec précision. L’équipe de Rasmus Kyng développe de nouveaux algorithmes capables d’analyser beaucoup plus efficacement d’immenses réseaux, comme ceux qui décrivent Internet, les réseaux électriques, les transports, les bâtiments ou encore certains problèmes d’intelligence artificielle.
Ces réseaux peuvent souvent être traduits en équations laplaciennes. Le défi apparaît lorsque le nombre de connexions atteint des millions, voire des milliards : les méthodes classiques deviennent alors trop lentes ou trop gourmandes en mémoire. Pour dépasser cette limite, les chercheurs s’appuient sur une approche appelée Approximate Cholesky, issue de travaux théoriques en informatique.
Le principe consiste à simplifier progressivement un réseau. Dans les méthodes exactes, chaque étape de simplification crée de nombreuses nouvelles connexions qu’il faut toutes prendre en compte. Cela alourdit rapidement le calcul. L’approche de l’ETH Zurich choisit plutôt un petit échantillon aléatoire, mais soigneusement sélectionné, de ces connexions. Ce raccourci permet d’obtenir presque le même résultat que le calcul complet, mais beaucoup plus rapidement.
Selon l’ETH Zurich, le nouveau prototype s’est montré fiable sur de nombreux tests et environ cinq fois plus rapide que des versions précédentes, y compris sur des problèmes où certains logiciels existants échouent. L’équipe travaille désormais à intégrer ces avancées dans le logiciel open source apxchol, destiné aux grands calculs scientifiques sur superordinateurs.
Cette recherche illustre le passage de la théorie mathématique à l’outil concret. En maîtrisant le hasard, les informaticiens pourraient rendre accessibles des problèmes de réseaux jusqu’ici trop vastes pour être traités efficacement.