Nyt gennembrud bringer matrixmultiplikation tættere på ideelt | Quanta Magasinet

Dataloger er en krævende flok. For dem er det ikke nok at få det rigtige svar på et problem - målet er næsten altid at få svaret så effektivt som muligt.

Gør det med at gange matricer eller rækker af tal. I 1812 kom den franske matematiker Jacques Philippe Marie Binet med det grundlæggende regelsæt, vi stadig lærer eleverne. Det fungerer udmærket, men andre matematikere har fundet måder at forenkle og fremskynde processen. Nu opgaven fremskynde processen af matrixmultiplikation ligger i skæringspunktet mellem matematik og datalogi, hvor forskere fortsætter med at forbedre processen den dag i dag - selvom gevinsterne i de seneste årtier har været ret beskedne. Siden 1987 har numeriske forbedringer i matrixmultiplikation været "små og ... ekstremt vanskelige at opnå," sagde François Le Gall, en datalog ved Nagoya University.

Nu har tre forskere - Ran Duan og Renfei Zhou fra Tsinghua University og Hongxun Wu fra University of California, Berkeley - taget et stort skridt fremad i at angribe dette flerårige problem. Deres nye resultater, præsenteret i november sidste år på Foundations of Computer Science-konferencen, stammer fra en uventet ny teknik, sagde Le Gall. Selvom forbedringen i sig selv var relativt lille, kaldte Le Gall den "konceptuelt større end andre tidligere."

Teknikken afslører en hidtil ukendt og dermed uudnyttet kilde til potentielle forbedringer, og den har allerede båret frugt: Et andet papir, udgivet i januar, bygger på den første til at vise, hvordan matrixmultiplikation kan øges yderligere.

"Dette er et stort teknisk gennembrud," sagde William Kuszmaul, en teoretisk datamatiker ved Harvard University. "Det er den største forbedring i matrixmultiplikation, vi har set i mere end et årti."

Indtast matrixen

Det kan virke som et obskurt problem, men matrixmultiplikation er en grundlæggende beregningsoperation. Det er indarbejdet i en stor del af de algoritmer, folk bruger hver dag til en række forskellige opgaver, lige fra at vise skarpere computergrafik til at løse logistiske problemer i netværksteori. Og som på andre områder inden for beregning, er hastighed altafgørende. Selv små forbedringer kan i sidste ende føre til betydelige besparelser af tid, regnekraft og penge. Men indtil videre er teoretikere primært interesserede i at finde ud af, hvor hurtig processen nogensinde kan være.

Den traditionelle måde at gange to på n-ved-n matricer — ved at gange tal fra hver række i den første matrix med tal i kolonnerne i den anden — kræver n³ separate multiplikationer. For 2-til-2-matricer betyder det 2³ eller 8 gange.

I 1969 afslørede matematikeren Volker Strassen en mere kompliceret procedure, der kunne multiplicere 2-til-2 matricer i blot syv multiplikative trin og 18 additioner. To år senere demonstrerede datalogen Shmuel Winograd, at syv faktisk er det absolutte minimum for 2 x 2 matricer.

Strassen udnyttede den samme idé til at vise, at alle større n-ved-n matricer kan også ganges med færre end n³ trin. Et nøgleelement i denne strategi involverer en procedure kaldet nedbrydning - nedbrydning af en stor matrix i successivt mindre submatricer, som kan ende med at blive så små som 2 x 2 eller endda 1 x 1 (dette er kun enkelte tal).

Rationalet for at opdele et kæmpe array i bittesmå stykker er ret simpelt ifølge Virginia Vassilevska Williams, en datalog ved Massachusetts Institute of Technology og medforfatter til en af ​​de nye artikler. "Det er svært for et menneske at se på en stor matrix (f.eks. i størrelsesordenen 100 x 100) og tænke på den bedst mulige algoritme," sagde Vassilevska Williams. Selv 3-til-3-matricer er ikke fuldt løst endnu. "Alligevel kan man bruge en hurtig algoritme, som man allerede har udviklet til små matricer til også at opnå en hurtig algoritme til større matricer."

Nøglen til hastighed, har forskere fastslået, er at reducere antallet af multiplikationstrin og sænke denne eksponent fra n³ (for standardmetoden) så meget de kan. Den lavest mulige værdi, n², er dybest set så lang tid, som det tager bare at skrive svaret. Dataloger omtaler den eksponent som omega, ω, med n^ω være de færrest mulige trin, der er nødvendige for at kunne gange to n-ved-n matricer som n vokser sig meget stor. "Pointen med dette arbejde," sagde Zhou, som også var medforfatter til avisen fra januar 2024, "er at se, hvor tæt på 2 du kan komme, og om det kan opnås i teorien."

Et laserfokus

I 1986 fik Strassen endnu et stort gennembrud, da han introduceret det, der kaldes lasermetoden til matrixmultiplikation. Strassen brugte det til at etablere en øvre værdi for omega på 2.48. Mens metoden kun er et trin i store matrixmultiplikationer, er den en af ​​de vigtigste, fordi forskerne er blevet ved med at forbedre den.

Et år senere introducerede Winograd og Don Coppersmith en ny algoritme, der smukt komplementerede lasermetoden. Denne kombination af værktøjer har været med i stort set alle efterfølgende bestræbelser på at fremskynde matrixmultiplikation.

Her er en forenklet måde at tænke på, hvordan disse forskellige elementer passer sammen. Lad os starte med to store matricer, A og B, som du vil gange sammen. Først nedbryder du dem i mange mindre submatricer eller blokke, som de nogle gange kaldes. Dernæst kan du bruge Coppersmith og Winograds algoritme til at fungere som en slags instruktionsmanual til håndtering og i sidste ende samling af blokkene. "Det fortæller mig, hvad jeg skal gange og hvad jeg skal tilføje, og hvilke poster der går hvorhen" i produktmatrix C, sagde Vassilevska Williams. "Det er bare en opskrift på at bygge C op fra A og B."

Der er dog en hage: Du ender nogle gange med blokke, der har indgange til fælles. At efterlade disse i produktet ville svare til at tælle disse poster to gange, så på et tidspunkt skal du slippe af med de duplikerede termer, kaldet overlapninger. Forskere gør dette ved at "dræbe" de blokke, de er i - at sætte deres komponenter lig med nul for at fjerne dem fra beregningen.

Det er her Strassens lasermetode endelig kommer i spil. "Lasermetoden fungerer typisk meget godt og finder generelt en god måde at dræbe en delmængde af blokke for at fjerne overlapningen," sagde Le Gall. Når laseren har elimineret eller "brændt væk" alle overlapninger, kan du konstruere den endelige produktmatrix, C.

At sætte disse forskellige teknikker sammen resulterer i en algoritme til at multiplicere to matricer med et bevidst nærigt antal multiplikationer samlet set - i det mindste i teorien. Lasermetoden er ikke beregnet til at være praktisk; det er bare en måde at tænke på den ideelle måde at multiplicere matricer på. "Vi kører aldrig metoden [på en computer]," sagde Zhou. "Vi analyserer det."

Og den analyse er det, der førte til den største forbedring af omega i mere end et årti.

Et tab er fundet

Sidste sommers papir, af Duan, Zhou og Wu, viste, at Strassens proces stadig kunne fremskyndes betydeligt. Det var alt sammen på grund af et koncept, de kaldte et skjult tab, begravet dybt i tidligere analyser - "et resultat af utilsigtet at dræbe for mange blokke," sagde Zhou.

Lasermetoden fungerer ved at mærke blokke med overlapninger som affald, beregnet til bortskaffelse; andre blokke anses for værdige og vil blive gemt. Udvælgelsesprocessen er dog noget randomiseret. En blok, der er klassificeret som skrald, kan faktisk vise sig at være nyttig trods alt. Dette var ikke en total overraskelse, men ved at undersøge mange af disse tilfældige valg, fastslog Duans team, at lasermetoden systematisk undervurderede blokke: Flere blokke skulle gemmes og færre smidt ud. Og, som det normalt er tilfældet, giver mindre spild sig større effektivitet.

"At være i stand til at beholde flere blokke uden overlapning fører således til ... en hurtigere matrixmultiplikationsalgoritme," sagde Le Gall.

Efter at have bevist eksistensen af ​​dette tab ændrede Duans team den måde, lasermetoden mærkede blokke på, hvilket reducerede affaldet væsentligt. Som et resultat satte de en ny øvre grænse for omega til omkring 2.371866 - en forbedring i forhold til den tidligere øvre grænse på 2.3728596, sat i 2020 af Josh Alman og Vassilevska Williams. Det kan virke som en beskeden ændring, der sænker grænsen med kun omkring 0.001. Men det er den største enkeltstående forbedring, videnskabsmænd har set siden 2010. Vassilevska Williams og Almans 2020-resultat blev til sammenligning kun forbedret med 0.00001 i forhold til sin forgænger.

Men det, der er mest spændende for forskere, er ikke kun selve den nye rekord - som ikke varede længe. Det er også det faktum, at avisen afslørede en ny mulighed for forbedring, som indtil da var gået helt ubemærket hen. I næsten fire årtier har alle været afhængige af den samme lasermetode, sagde Le Gall. "Så fandt de ud af, at vi kan gøre det bedre."

Papiret fra januar 2024 forfinede denne nye tilgang, hvilket gjorde det muligt for Vassilevska Williams, Zhou og deres medforfattere at reducere det skjulte tab yderligere. Dette førte til en yderligere forbedring af omega's øvre grænse, hvilket reducerede den til 2.371552. Forfatterne generaliserede også den samme teknik til at forbedre multiplikationsprocessen for rektangulære (n-ved-m) matricer — en procedure, der har anvendelser inden for grafteori, maskinlæring og andre områder.

Nogle yderligere fremskridt langs disse linjer er næsten sikkert, men der er grænser. I 2015, Le Gall og to samarbejdspartnere bevist at den nuværende tilgang - lasermetoden kombineret med Coppersmith-Winograd-opskriften - ikke kan give en omega under 2.3078. For at foretage yderligere forbedringer, sagde Le Gall, "du er nødt til at forbedre den oprindelige [tilgang] fra Coppersmith og Winograd, som ikke rigtig har ændret sig siden 1987". Men indtil videre er der ingen, der har fundet på en bedre måde. Der er måske ikke engang en.

"At forbedre omega er faktisk en del af forståelsen af ​​dette problem," sagde Zhou. "Hvis vi kan forstå problemet godt, så kan vi designe bedre algoritmer til det. [Og] folk er stadig i de meget tidlige stadier af at forstå dette ældgamle problem."