Lineaire vergelijkingen een miljard keer sneller

Onderzoekers aan de Carnegie Mellon University hebben een algoritme ontwikkeld dat het oplossen van complexe lineaire vergelijkingen tot een miljard keer zou moeten versnellen.

Computersimulaties en beeldbewerking

Volgens de wetenschappers heeft hun theoretische doorbraak enorm veel potentieel in de praktijk. Veel computersimulaties van dingen uit de echte wereld als transport, telecommunicatie, energieopwekking of productiemechanismes gebruiken namelijk lineaire systemen om hun simulatie te bewerkstelligen.

Het algoritme richt zich met name op diagonaal dominante systemen, die bijvoorbeeld worden gebruikt in de aanbevelingsmechanismes van webshops als Bol.com of Wehkamp, maar ook in beeldbewerkingsprogramma's. Volgens de Amerikanen is hun algoritme zo efficiënt dat "het binnenkort mogelijk is om een vergelijking met miljarden variabelen binnen enkele seconden op te lossen met een desktopcomputer".

Geen enkel algoritme komt in de buurt

De wetenschappers bereiken die efficiëntie door eerst een vereenvoudigde som op te lossen. Dat kan snel worden gedaan en de uitkomst van die som kan vervolgens dienen als een "pre-conditioner" om vervolgstappen naar de uiteindelijke uitkomst te nemen.

Volgens Daniel Spielman, professor in de toegepaste wiskunde en informatica aan de Yale University, is het algoritme van de wetenschappers geweldig. Hij prijst in het verslag van de onderzoekers zowel de snelheid als de eenvoud van het systeem dat de Amerikanen ontwikkelde.

"Er is geen enkel ander algoritme dat ook maar in de buurt komt van deze snelheid. In feite zal het zelfs onmogelijk zijn om een algoritme te ontwerpen dat nog veel sneller is", stelt de professor die de uitkomsten van de wetenschappers toetste.