Noua descoperire aduce multiplicarea matricelor mai aproape de ideal | Revista Quanta

Informaticienii sunt o grupă pretențioasă. Pentru ei, nu este suficient să obțineți răspunsul corect la o problemă – scopul, aproape întotdeauna, este să obțineți răspunsul cât mai eficient posibil.

Luați actul de a înmulți matrice sau matrice de numere. În 1812, matematicianul francez Jacques Philippe Marie Binet a venit cu setul de bază de reguli pe care încă îl predăm elevilor. Funcționează perfect, dar alți matematicieni au găsit modalități de a simplifica și accelera procesul. Acum sarcina de a grăbirea procesului de multiplicare a matricei se află la intersecția dintre matematică și informatică, unde cercetătorii continuă să îmbunătățească procesul până în prezent - deși în ultimele decenii câștigurile au fost destul de modeste. Din 1987, îmbunătățirile numerice în înmulțirea matricelor au fost „mici și … extrem de greu de obținut”, a spus François Le Gall, un informatician la Universitatea Nagoya.

Acum, trei cercetători - Ran Duan și Renfei Zhou de la Universitatea Tsinghua și Hongxun Wu de la Universitatea din California, Berkeley - au făcut un pas major înainte în atacarea acestei probleme perene. Al lor rezultate noi, prezentate în noiembrie anul trecut la conferința Foundations of Computer Science, provin dintr-o tehnică nouă neașteptată, a spus Le Gall. Deși îmbunătățirea în sine a fost relativ mică, Le Gall a numit-o „mai mare din punct de vedere conceptual decât celelalte anterioare”.

Tehnica dezvăluie o sursă necunoscută anterior și, prin urmare, neexploatată de potențiale îmbunătățiri, și a dat deja roade: O a doua lucrare, publicat în ianuarie, se bazează pe primul pentru a arăta cum înmulțirea matricei poate fi stimulată și mai mult.

„Acesta este o descoperire tehnică majoră”, a spus William Kuszmaul, un informatician teoretic la Universitatea Harvard. „Este cea mai mare îmbunătățire a înmulțirii matricelor pe care am văzut-o în mai mult de un deceniu.”

Intră în Matrice

Poate părea o problemă obscure, dar multiplicarea matricei este o operație de calcul fundamentală. Este încorporat într-o mare parte din algoritmii pe care oamenii îi folosesc în fiecare zi pentru o varietate de sarcini, de la afișarea unei grafice pe computer mai clare până la rezolvarea problemelor logistice în teoria rețelelor. Și ca și în alte domenii de calcul, viteza este primordială. Chiar și îmbunătățirile ușoare ar putea duce în cele din urmă la economii semnificative de timp, putere de calcul și bani. Dar pentru moment, teoreticienii sunt interesați în principal să descopere cât de rapid poate fi vreodată procesul.

Modul tradițional de înmulțire a doi n-de-n matrice — prin înmulțirea numerelor din fiecare rând din prima matrice cu numerele din coloanele din a doua — necesită n³ înmulțiri separate. Pentru matrice de 2 câte 2, înseamnă 2³ sau 8 înmulțiri.

În 1969, matematicianul Volker Strassen a dezvăluit o procedură mai complicată care putea înmulți matrice 2 cu 2 în doar șapte pași multiplicatori și 18 adunări. Doi ani mai târziu, informaticianul Shmuel Winograd a demonstrat că șapte este, într-adevăr, minimul absolut pentru matrice 2 pe 2.

Strassen a exploatat aceeași idee pentru a arăta că totul este mai mare n-de-n matricele pot fi, de asemenea, înmulțite în mai puțin de n³ trepte. Un element cheie în această strategie implică o procedură numită descompunere - descompunerea unei matrice mari în submatrici succesiv mai mici, care ar putea ajunge să fie la fel de mici ca 2-pe-2 sau chiar 1-pe-1 (acestea sunt doar numere simple).

Motivul pentru împărțirea unei matrice gigantice în bucăți mici este destul de simplu, potrivit Virginia Vassilevska Williams, un informatician la Institutul de Tehnologie din Massachusetts și coautor al uneia dintre noile lucrări. „Este greu pentru un om să se uite la o matrice mare (de exemplu, de ordinul 100 pe 100) și să se gândească la cel mai bun algoritm posibil”, a spus Vassilevska Williams. Nici măcar matricele 3 pe 3 nu au fost încă rezolvate complet. „Cu toate acestea, se poate folosi un algoritm rapid pe care l-am dezvoltat deja pentru matrice mici, pentru a obține și un algoritm rapid pentru matrice mai mari.”

Cheia vitezei, au stabilit cercetătorii, este reducerea numărului de pași de multiplicare, scăzând acel exponent de la n³ (pentru metoda standard) cât pot. Cea mai mică valoare posibilă, n², este practic atâta timp cât este nevoie doar pentru a scrie răspunsul. Informaticii se referă la acel exponent ca omega, ω, cu n^ω fiind cei mai puțini pași posibili necesari pentru a înmulți cu succes doi n-de-n matrice ca n crește foarte mare. „Scopul acestei lucrări”, a spus Zhou, care a fost și coautor al lucrării din ianuarie 2024, „este să vedem cât de aproape de 2 poți ajunge și dacă poate fi atins în teorie”.

O focalizare laser

În 1986, Strassen a avut un alt mare progres când el introdus ceea ce se numește metoda laser pentru multiplicarea matricei. Strassen l-a folosit pentru a stabili o valoare superioară pentru omega de 2.48. În timp ce metoda este doar un pas în înmulțirile mari de matrice, este una dintre cele mai importante, deoarece cercetătorii au continuat să o îmbunătățească.

Un an mai târziu, Winograd și Don Coppersmith au introdus un nou algoritm care a completat frumos metoda laser. Această combinație de instrumente a fost prezentă în aproape toate eforturile ulterioare de a accelera înmulțirea matricei.

Iată un mod simplificat de a gândi cum se potrivesc aceste elemente diferite. Să începem cu două matrici mari, A și B, pe care doriți să le înmulțiți împreună. Mai întâi, le descompuneți în multe submatrici mai mici sau blocuri, așa cum sunt uneori numite. Apoi, puteți folosi algoritmul lui Coppersmith și Winograd pentru a servi ca un fel de manual de instrucțiuni pentru manipularea și, în cele din urmă, asamblarea blocurilor. „Îmi spune ce să înmulțesc și ce să adaug și ce intrări merg unde” în matricea de produse C, a spus Vassilevska Williams. „Este doar o rețetă pentru a construi C din A și B.”

Există totuși o captură: uneori ajungi cu blocuri care au intrări în comun. Lăsarea acestora în produs ar fi asemănător cu numărarea acelor intrări de două ori, așa că la un moment dat trebuie să scăpați de acești termeni duplicați, numiți suprapuneri. Cercetătorii fac acest lucru „omorând” blocurile în care se află – setând componentele lor la zero pentru a le elimina din calcul.

Acolo intră în sfârșit în joc metoda laserului lui Strassen. „Metoda laser funcționează de obicei foarte bine și, în general, găsește o modalitate bună de a ucide un subset de blocuri pentru a elimina suprapunerea”, a spus Le Gall. După ce laserul a eliminat sau „ars” toate suprapunerile, puteți construi matricea produsului final, C.

Punerea laolaltă a acestor diferite tehnici are ca rezultat un algoritm pentru înmulțirea a două matrici cu un număr de înmulțiri în mod deliberat zgârcit - cel puțin în teorie. Metoda laser nu se dorește a fi practică; este doar o modalitate de a ne gândi la modul ideal de a multiplica matrice. „Nu rulăm niciodată metoda [pe un computer]”, a spus Zhou. „O analizăm.”

Și această analiză este cea care a condus la cea mai mare îmbunătățire a omega în mai mult de un deceniu.

S-a găsit o pierdere

Lucrarea din vara trecută, de Duan, Zhou și Wu, a arătat că procesul lui Strassen ar putea fi încă accelerat semnificativ. Totul s-a datorat unui concept pe care l-au numit o pierdere ascunsă, îngropat adânc în analizele anterioare – „rezultat al uciderii neintenționate a prea multor blocuri”, a spus Zhou.

Metoda laser funcționează prin etichetarea blocurilor cu suprapuneri ca gunoi, programate pentru eliminare; alte blocuri sunt considerate demne și vor fi salvate. Procesul de selecție este însă oarecum randomizat. Un bloc evaluat ca gunoi se poate dovedi, de fapt, a fi util până la urmă. Aceasta nu a fost o surpriză totală, dar examinând multe dintre aceste alegeri aleatorii, echipa lui Duan a stabilit că metoda laser subevaluează în mod sistematic blocurile: mai multe blocuri ar trebui salvate și mai puține aruncate. Și, așa cum este de obicei cazul, mai puține deșeuri se traduce printr-o eficiență mai mare.

„Potând păstra mai multe blocuri fără suprapunere duce astfel la... un algoritm de multiplicare a matricei mai rapid”, a spus Le Gall.

După ce a demonstrat existența acestei pierderi, echipa lui Duan a modificat modul în care metoda laser a etichetat blocurile, reducând substanțial deșeurile. Drept urmare, au stabilit o nouă limită superioară pentru omega la aproximativ 2.371866 - o îmbunătățire față de limita superioară anterioară de 2.3728596, stabilit în 2020 de Josh Alman și Vassilevska Williams. Aceasta poate părea o modificare modestă, scăzând limita cu aproximativ 0.001. Dar este cea mai mare îmbunătățire pe care oamenii de știință au văzut-o din 2010 din 2020. Rezultatul lui Vassilevska Williams și Alman din 0.00001, prin comparație, s-a îmbunătățit doar cu XNUMX față de predecesorul său.

Dar ceea ce este cel mai interesant pentru cercetători nu este doar noul record în sine – care nu a durat mult. Este și faptul că ziarul a scos la iveală o nouă cale de îmbunătățire care, până atunci, trecuse total neobservată. De aproape patru decenii, toată lumea s-a bazat pe aceeași metodă cu laser, a spus Le Gall. „Apoi au descoperit că, ei bine, putem face mai bine.”

Lucrarea din ianuarie 2024 a rafinat această nouă abordare, permițând lui Vassilevska Williams, Zhou și coautorilor lor să reducă și mai mult pierderea ascunsă. Acest lucru a condus la o îmbunătățire suplimentară a limitei superioare a omega, reducându-l la 2.371552. Autorii au generalizat, de asemenea, aceeași tehnică pentru a îmbunătăți procesul de înmulțire pentru dreptunghiulare (n-de-m) matrice — o procedură care are aplicații în teoria grafurilor, învățarea automată și în alte domenii.

Unele progrese suplimentare în această direcție sunt aproape sigure, dar există limite. În 2015, Le Gall și doi colaboratori s-au dovedit că abordarea actuală - metoda laser cuplată cu rețeta Coppersmith-Winograd - nu poate da un omega sub 2.3078. Pentru a face orice îmbunătățiri suplimentare, Le Gall a spus, „trebuie să îmbunătățiți [abordarea] originală a Coppersmith și Winograd, care nu s-a schimbat cu adevărat din 1987.. " Dar până acum, nimeni nu a venit cu o modalitate mai bună. Poate că nici măcar nu există.

„Îmbunătățirea omega este de fapt parte a înțelegerii acestei probleme”, a spus Zhou. „Dacă putem înțelege bine problema, atunci putem proiecta algoritmi mai buni pentru ea. [Și] oamenii sunt încă în stadiile incipiente ale înțelegerii acestei probleme veche.”