Matrixvermenigvuldiging: de rekenmachine achter kunstmatige intelligentie
Matrixvermenigvuldiging is een rekenkundige bewerking waarbij twee rechthoekige rasters van getallen — matrices genoemd — volgens een vaste regel worden gecombineerd tot een nieuw raster. Denk aan een matrix als een uitgebreid spreadsheet: rijen en kolommen vol cijfers, zonder namen of formules erbij, puur getallen. Vermenigvuldig je twee van zulke rasters, dan reken je voor elk vakje in het resultaat een rij uit de ene matrix en een kolom uit de andere tegen elkaar weg: je vermenigvuldigt de bijbehorende getallen en telt ze op.
Een concreet voorbeeld: stel dat een bakkerij drie soorten brood verkoopt, en je hebt een matrix met hoeveel meel, gist en zout elk brood nodig heeft, en een tweede matrix met de prijs van meel, gist en zout bij drie verschillende leveranciers. Door deze twee matrices te vermenigvuldigen, reken je in één keer uit wat elk brood bij elke leverancier aan grondstoffen kost — zonder dat je alle combinaties apart hoeft na te rekenen. Deze simpele, mechanische rekenstap blijkt de wiskundige motor te zijn achter onder meer 3D-graphics, weersvoorspellingen en, actueler, de neurale netwerken die kunstmatige intelligentie aandrijven.
Wat is het precies?
Een matrix heeft een aantal rijen en een aantal kolommen; een matrix met 3 rijen en 4 kolommen heet een 3×4-matrix. Om twee matrices te mogen vermenigvuldigen, moet het aantal kolommen van de eerste gelijk zijn aan het aantal rijen van de tweede. Het resultaat krijgt dan het aantal rijen van de eerste matrix en het aantal kolommen van de tweede.
De rekenregel zelf is simpel maar arbeidsintensief: voor elk getal in het resultaat neem je een volledige rij uit de eerste matrix en een volledige kolom uit de tweede, vermenigvuldig je de overeenkomstige getallen paarsgewijs, en tel je die producten bij elkaar op. Voor twee matrices van elk n bij n getallen betekent dit ruwweg n³ (n tot de derde macht) vermenigvuldigingen — bij een matrix van honderd bij honderd al een miljoen bewerkingen, bij duizend bij duizend een miljard.
Die snelle groei is precies waarom informatici al decennia zoeken naar slimmere methodes. In 1969 ontdekte de Duitse wiskundige Volker Strassen dat het sneller kan door de matrices op te delen in kleinere blokken en met een geraffineerde truc twee vermenigvuldigingen te "besparen" ten koste van wat extra optellingen. Dat klinkt marginaal, maar bij herhaalde toepassing op steeds grotere matrices levert het een fundamenteel lagere groeisnelheid op dan n³. Sindsdien wordt in de theoretische informatica gejaagd op de zogeheten omega-exponent (ω): het laagst haalbare groeitempo van matrixvermenigvuldiging. Bij de naïeve methode is ω gelijk aan 3; Strassens methode bracht het terug tot ongeveer 2,807. Latere, steeds complexere algoritmes duwden dit getal in kleine stapjes verder omlaag, richting de theoretische ondergrens van 2 — al is onzeker of die grens ooit echt gehaald wordt.
Wat wil men ermee bereiken?
Het uiteindelijke doel is simpel: rekenwerk dat overal in wetenschap en techniek voorkomt, sneller en met minder energie uitvoeren. Matrixvermenigvuldiging duikt op bij het draaien van 3D-graphics in games, het simuleren van weer en klimaat, structurele berekeningen in de bouw, signaalverwerking en cryptografie. Maar de belangrijkste aanjager van recent onderzoek is kunstmatige intelligentie: een neuraal netwerk is in de kern niets anders dan een lange keten van matrixvermenigvuldigingen, waarbij de "gewichten" van het netwerk in matrices worden opgeslagen en invoerdata daar telkens doorheen wordt vermenigvuldigd.
Omdat het trainen en gebruiken van grote taalmodellen en andere AI-systemen inmiddels enorme hoeveelheden rekenkracht en elektriciteit vergt, heeft elke procent winst in de snelheid van matrixvermenigvuldiging direct gevolgen voor de kosten, de wachttijd en het energieverbruik van AI-toepassingen. Zowel theoretische wiskundigen die op zoek zijn naar slimmere algoritmes, als chipfabrikanten die gespecialiseerde hardware bouwen, werken in feite aan hetzelfde probleem vanuit een andere hoek.
Voorbeelden uit de praktijk
Strassens algoritme (1969) was de eerste doorbraak: door slimmer te rekenen in plaats van harder, verlaagde Strassen de theoretische groeisnelheid van matrixvermenigvuldiging voor het eerst onder n³. Het wordt nog steeds gebruikt in sommige wiskundige softwarebibliotheken voor zeer grote matrices.
BLAS en LAPACK zijn softwarebibliotheken die sinds de jaren zeventig en tachtig de standaard vormen voor snel matrixrekenwerk in wetenschappelijke software. Ze worden nog altijd gebruikt in weermodellen, technische simulaties en onderzoekssoftware wereldwijd, vaak zonder dat gebruikers het merken.
Google's Tensor Processing Unit (TPU), voor het eerst ingezet in 2016, is een chip die specifiek is ontworpen om matrixvermenigvuldigingen razendsnel uit te voeren via een zogeheten systolic array: een rooster van rekeneenheden die data ritmisch langs elkaar doorschuiven. TPU's draaien onder meer achter Google Translate, Zoeken en het trainen van grote AI-modellen.
NVIDIA's Tensor Cores, geïntroduceerd met de Volta-architectuur in 2017, zijn gespecialiseerde rekeneenheden binnen NVIDIA-videokaarten die kleine matrixvermenigvuldigingen in één bewerking uitvoeren. Ze vormen de hardwarebasis van vrijwel alle moderne AI-training buiten Google's eigen datacenters.
AlphaTensor van DeepMind, gepubliceerd in het wetenschappelijke tijdschrift Nature in oktober 2022, liet een kunstmatig-intelligentiesysteem via zogeheten reinforcement learning — een trainingsmethode waarbij een systeem zelf strategieën ontdekt door te experimenteren en beloond te worden voor goede uitkomsten — zelf op zoek gaan naar nieuwe, snellere manieren om matrices te vermenigvuldigen. Voor 4×4-matrices vond het systeem een methode met 47 vermenigvuldigingen in plaats van de 49 van Strassens klassieke aanpak (voor een specifiek type rekenkunde, modulo 2). Kort na publicatie verbeterden de wiskundigen Manuel Kauers en Jakob Moosbauer van de Johannes Kepler Universität Linz dit resultaat handmatig verder, wat illustreert dat mens en machine elkaar op dit terrein afwisselend voorbijstreven.
Hoe ver is de techniek?
Op theoretisch vlak gaat de vooruitgang traag maar gestaag: sinds Strassen in 1969 is de omega-exponent in kleine stapjes gezakt, en stond deze medio jaren 2020 in gepubliceerd onderzoek rond de 2,37. De exacte laatste decimalen verschuiven regelmatig door nieuwe publicaties van onderzoeksgroepen wereldwijd, dus specifieke cijfers verouderen snel — het is een actief maar traag veld, en niemand weet zeker of en wanneer de ondergrens van 2 ooit bereikt wordt.
Belangrijk is dat deze theoretische winst grotendeels academisch blijft: de meeste geavanceerde algoritmes met een lage omega-exponent zijn pas voordeliger bij matrices die vele malen groter zijn dan wat in de praktijk wordt gebruikt, en kampen bovendien met numerieke instabiliteit (kleine afrondingsfouten die zich opstapelen). Daardoor wordt in de praktijk, ook bij AI-training, meestal nog gewoon de klassieke methode gebruikt — maar dan wel uitgevoerd op speciaal ontworpen hardware.
Op dat praktische vlak gaat de ontwikkeling juist hard: fabrikanten als NVIDIA, Google en AMD brengen periodiek nieuwe generaties chips uit die matrixvermenigvuldiging met steeds meer parallelle rekeneenheden en lagere energie per bewerking uitvoeren. De grootste versnelling van de afgelopen jaren komt dan ook niet uit nieuwe wiskunde, maar uit gespecialiseerde hardware en slimmer geheugenbeheer.
Wie werken eraan?
Aan de theoretische kant houden onderzoeksgroepen aan onder meer het Massachusetts Institute of Technology (MIT) — met informatica-hoogleraar Virginia Vassilevska Williams als een van de bekendste namen op dit terrein — en de Johannes Kepler Universität in het Oostenrijkse Linz zich bezig met het steeds verder verlagen van de omega-exponent.
Aan de kant van kunstmatige intelligentie en algoritme-ontdekking is DeepMind, het Londense AI-onderzoekslab van Google, verantwoordelijk voor AlphaTensor. Op hardwaregebied zijn NVIDIA (met zijn Tensor Cores), Google (met de TPU-lijn) en in mindere mate AMD en Intel de belangrijkste partijen die matrixvermenigvuldiging fysiek zo snel en efficiënt mogelijk in silicium proberen te gieten. Het bredere theoretische onderzoek wordt verder gevoed door de internationale gemeenschap van theoretisch informatici, die resultaten uitwisselt via vaktijdschriften en conferenties als STOC en FOCS.