Multiplikation af to 2x2 matricer kræver to multiplikationer for hvert element i den endelige matrix udført på den sædvanlige måde. Men det kan udføres smartere med kun syv multiplikationer. Illustration: arkiv.
Der findes mere effektive metoder til matrixmultiplikation end dem, man lærer i skolen. AI-program har fundet endnu bedre metoder end de, som i dag benyttes i computere.
Multiplikation af matricer er ikke kun noget, man plager elever og studerende med i matematikundervisningen. Matrixmultiplikation anvendes i stor stil i forbindelse med billedbehandling, talegenkendelse, computergrafik, vejrsimulationer og meget mere. At kunne multiplicere matricer effektivt og hurtigt er helt afgørende for mange tekniske og videnskabelige applikationer.
En ny artikel i Nature præsenter en række nye algoritmer til matrixmultiplikation, der typisk kan speede beregningerne op med 10-20 pct.
Det opsigtsvækkende er, at de alle er fundet med brug af kunstig intelligens!
I skolen lærer vi at multiplicere matricer som vist i illustrationen i toppen af denne artikel, hvor det kræver otte multiplikationer og fire additioner at udføre multiplikationen af to 2x2 matricer.
Artiklen fortsætter efter annoncen
I 1969 chokerede den tyske matematiker Volker Strassen den matematiske verden ved at vise, at operationen kunne udføres med kun syv multiplikationer mod, at man til gengæld accepterede at bruge flere additioner.
Konventionel multiplikation af to 2x2 matricer kræver otte multiplikationer. Med Volker Strassens metode kan man nøjes med kun syv mod at have flere additioner. For en computer er multiplikationer langt mere krævende end additioner, så Strassens metode er mere effektiv. (Forstør billedet ved at klikke på det) Illustration: DeepMind.
Strassen sat gang i eftersøgning af nye algoritmer
Siden da har matematikere og dataloger søgt at finde metoder til multiplikation af også større matricer med færrest muligt antal multiplikationer.
I 1976 beskrev Julian D. Laderman eksempelvis en metode til multiplikation af to 3x3 matricer, der kun kræver 23 multiplikationer frem for de 27, som skal bruges med den sædvandlige skolemetode.
I Nature præsenterer forskere fra DeepMind nu en lang række metoder til effektiv multiplikation af større matricer, der er bedre end de allerede kendte i den forstand, at de bruger færre antal multiplikationer.
Det interessante er, at alle de disse metoder er fundet af et system kaldet AlphaTensor, der er en videreudvikling af AlphaZero, som lærte sig selv at spille en lang række brætspil herunder skak på en overnaturlig måde.
Som eksempel kan nævnes, at multiplikation af en 4x5 matrix med en 5x5 matrix kan udføres med kun 76 multiplikationer. Med den konventionelle metode kræver det 100 multiplikationer, og den hidtil bedste alternative metode kræver 80 multiplikationer.
Et avanceret tensor-spil
AlphaTensor finder nye former for matrixmultiplikation ved en form for spil, som det spiller på lidt samme måde, som AlphaZero lærte sig skak ved at spille mod sig selv.
Metoden er ganske kompliceret, og spillet er langt mere krævende end at lære at spille skak. I matrixmultiplikationsspillet er antallet af mulige træk eksempelvis ved hvert skridt omkring 10^30 gange større end i brætspil.
Under sin oplæring finder matrixmultiplikationsspillet selv frem til Strassens algoritme for 2x2 matricer og Ladermans algoritme for 3x3 matricer (ligesom AlphaZero også fandt frem til de mest benyttede åbninger i skak), men altså også nye og mere effektive algoritmer for multiplikation af større matricer.
Ofte vil de mest effektive former for matrixmultiplikation i praksis afhænge af hvilken form for hardware, man benytter i sin computer. Så udover at finde de former for matrixmultiplikation, der har færrest antal multiplikationer, har DeepMind også fundet de algoritmer, der fungerer bedst på specifik hardware som f.eks. Nvidia V100 GPU og Google TPU v2.
Generelt er de nye algoritmer 10-20 pct. hurtigere end de algoritmer, som bruges i dag.
Matrixmultiplikationsspillet opererer med tensorer.
Artiklen fortsætter efter annoncen
Multiplikation af 2x2 matricer kan repræsenteres med en 3D tensor, hvor blå angiver tallet 1, mens de øvrige elementer har værdien 0. Tensoren indikerer f.eks., at c1=a1b1 + a2b3, som er vist ved, at tensorelementerne (a1,b1,c1) og (a2,b3,c1) er 1 Illustration: Nature.
For en given matrixmultiplikation, f.eks multiplikation af en 4x5 matrix med en 5x5 matrix, tager AlphaTensor en given tensor som input. Spillet går så ud på at opdatere denne tensor, som man kommer frem til en simpel tensor, der fører til samme resultat for matrixmultiplikationen. Mere teknisk skal man finde en ny tensor med en lavere rang.
DeepMind forskerne bemærker, at deres nuværende metode rent faktisk er baseret på, at AlphaTensor skal hjælpes lidt på vej, og metoden derfor i princippet kan overse endnu mere effektive algoritmer end dem, som nu er fundet. Forskerne skriver derfor også, at yderligere forskning og forbedringer kan føre frem til endnu bedre algoritmer for matrixmultiplikation.
De bemærker endvidere, at man kan forestille sig, at principperne bag AlphaTensor bruges til andre optimeringsopgaver f.eks. inden for energiforbrug.
God dag alle på kontoret
Jeg hedder Thomas Richter, 61 år gamle og invalide siden 2012. De 4 grundregne tekniker har min interesse. jeg er per tilfælde stødt på noget, som ved nærmer undersøgelse viste sig som en ny vej til multiplikation. Dermed kommer jeg ved langt de fleste regnestykker på halvdelen og mmindre enkelte ekstra skrit en her beskrevet. Og med kendskab til sekvensperiode beregning, er det muligt at gange 1000vis af cifre med hinanden i hoved! men hvem har interesse at lægge grækernes hypoteser til side og bytte dem ud med tyske fakta? de må gerne kontaktee mig på "jtrichter@123dk.dk!
Venligst Thomas Richter
Ved hardware, hvad betyder det så om der er 7 eller 8 multiplikatorer på chippen? Routingen betyder mere for arealet, og spikes betyder mer for strømforbrug.
Idet Log_2 (7) = 2.8 kan ved hjælp af del og hersk (fordi matrix multiplikation kan gøres blokvis) eksponenten 3 i antallet af multiplikationer O(N^3) nøjes med O(N^2.8)
Dette skulle spille en rolle ved dimensioner N > 100 så ja fordi man kan halvere matricerne gentagne gange og på denne måde gennemføre matrix multiplikation som 2x2 blokmatricer så betyder det noget om der er 8 eller kun 7 multiplikations trin i hvert fald hvis matricerne er store
Strassen er ikke hvem som helst (antager jeg) hvis han er den som sammen med Solovay har opfundet Solovay-Strassen's stokastiske sammensatheds-test der hurtigt kan si sammensatte tal bort fra kandidater til primtal selv om den omtalte test ikke er en sikker primtalstest
Jeg er enig med dig i din software vurdering. Mange hardware implementeringer har samme problem som software implementeringer, men de har mulighed for større parallelisme. Ved hardware betyder 20% ikke meget - og man ofre gerne 20% ekstra transistorer på at reducere strømforbruget, eller opnå større hastighed. Kan opnås dobbelt hastighed med 20% ekstra transistorer, er det fuldt investeringen værd. Har vi eksempel et niveau af multiplikationer inden resultatet ved en normal udregning, men to ved vores "sparede" version, så bliver den mere end 20% sløvere.
Altså, en 20% optimering er vildt meget!!!
Jeg sidder pt med et kæmpe projekt med FEM implementering i C++, hvor netop matrix multiplikation udgør langt størstedelen af beregningerne. Så jeg skal da læse artiklen i Nature omhyggeligt igennem.
I det software system vi byggede til styringen af spejlene i ESO's ELT teleskop ganges en vector med en 6000x10000 matrix 500 gange per sekund per maskine.
En forbedring på 20% ville gøre det muligt at styre spejlene med 600Hz i stedet og det ville iflg forskerne hos ESO give konkrete og målbare forbedringer i billedkvalitet.
Jeg tror primært at disse nye algoritmer er interessante i hardware-implementeringer, hvor en multiplikator kræver kvadratisk flere transistorer end adder.
I software baserede systemer tror jeg ikke umiddelbart at disse nye "moderne" algoritmer vil være hurtigere, både fordi der skal bruges meget mere memory-båndbredde til informationen om hvad der skal ske i hvilken rækkefølge, enten i form af instruktioner eller tabeller, men også fordi de resulterende memory-operationer, iflg. mit øjemål, ikke kan tilrettelægges nær så optimalt for i forhold til den begrænsende båndbredde mellem CPU, Cache og Memory.
Desuden vil det være mere vanskeligt at validere korrektheden af resultatet uden den simple ortogonalitet i en normal MVM. Man være nødt til, at eftervise at alle celler i matricerne dukker op præcis hvor de skal og ingen andre steder. En simpel brute-force kørsel over alle cellepar er ikke garanteret vandtæt, når der også indgår subtraktioner.
Jeg syntes ikke en reduktion af antallet af multiplikationer med 20% lyder af meget. Der kan være andre faktorer, der har større betydning, end antallet af multiplikationer. Har vi f.eks. en chip, og sparer nogle multiplikationer, så kan vi måske få et mindre areal - men det er ikke sikkert, for en regulær og simpel struktur, giver måske reelt det laveste areal. Ofte, så er det forsinkelsen - altså vejen fra input til output som er afgørende, og så betyder det ikke noget, at bruge flere multiplikationer, hvis forsinkelse kan reduceres. Det er helt normalt, at man på en chip ødsler med antallet af transistorer og multiplikatorer, for at bringe delayet ned, da delayet er det kritiske. Nogle gange bruges endda flere multiplikatorer til at regne flere værdier ud, for at kunne bruge den korrekte senere. Det interessante er oftest, at kunne parallelisere opgaven, og få svaret så hurtigt som muligt igennem en parallel struktur.
Vi kan sammenligne det med at optimere logiske udtryk: Vi kan få færre gates, og færre transistorer, men ofte bliver forsinkelsen større, end hvis vi anvender en ikke optimeret struktur. Og en ikke optimeret struktur, har måske endda færre skifts, og lavere strømforbrug, fordi at signalerne ikke går igennem komponenter der får signalerne til at skifte flere gange. Det er ikke ualmindeligt, at vi anvender ekstra komponenter, alene for at få en lavere delay, og en hurtigere chip.
