Nov preboj približuje matrično množenje idealu | Revija Quanta

Računalničarji so zahtevna druščina. Za njih ni dovolj, da dobijo pravi odgovor na težavo – skoraj vedno je cilj dobiti odgovor čim bolj učinkovito.

Recimo dejanje množenja matrik ali nizov števil. Leta 1812 je francoski matematik Jacques Philippe Marie Binet pripravil osnovni niz pravil, ki jih še vedno učimo učence. Deluje popolnoma dobro, vendar so drugi matematiki našli načine za poenostavitev in pospešitev postopka. Zdaj pa naloga pospešitev postopka matričnega množenja leži na stičišču matematike in računalništva, kjer raziskovalci nadaljujejo z izboljševanjem procesa do danes - čeprav so bili v zadnjih desetletjih dobički dokaj skromni. Od leta 1987 so bile numerične izboljšave v množenju matrik "majhne in … izjemno težko dosegljive", je dejal François Le Gall, računalničar na univerzi Nagoya.

Zdaj so trije raziskovalci – Ran Duan in Renfei Zhou z univerze Tsinghua ter Hongxun Wu s kalifornijske univerze v Berkeleyju – naredili velik korak naprej pri napadu na to večno težavo. Njihovo novi rezultati, ki je bil predstavljen novembra lani na konferenci Foundations of Computer Science, izvira iz nepričakovane nove tehnike, je dejal Le Gall. Čeprav je bila izboljšava sama relativno majhna, jo je Le Gall imenoval "konceptualno večja od drugih prejšnjih."

Tehnika razkriva prej neznan in zato neizkoriščen vir potencialnih izboljšav in je že obrodila sadove: Drugi papir, objavljeno januarja, temelji na prvem, da pokaže, kako je mogoče matrično množenje še povečati.

"To je velik tehnični preboj," je dejal William Kuszmaul, teoretični računalniški znanstvenik na univerzi Harvard. "To je največji napredek pri množenju matrik, ki smo ga videli v več kot desetletju."

Vnesite Matrix

Morda se zdi nejasen problem, vendar je množenje matrike temeljna računska operacija. Vključen je v velik del algoritmov, ki jih ljudje uporabljajo vsak dan za različne naloge, od prikaza ostrejše računalniške grafike do reševanja logističnih problemov v teoriji omrežij. In kot na drugih področjih računalništva je hitrost najpomembnejša. Celo majhne izboljšave lahko sčasoma povzročijo znatne prihranke časa, računalniške moči in denarja. Toda za zdaj teoretike zanima predvsem ugotovitev, kako hiter je lahko proces.

Tradicionalni način množenja dveh n-z-n matrike — z množenjem števil iz vsake vrstice v prvi matriki s števili v stolpcih v drugi — zahteva n³ ločena množenja. Za matrike 2 krat 2 to pomeni 2³ ali 8 množenja.

Leta 1969 je matematik Volker Strassen razkril bolj zapleten postopek, s katerim je bilo mogoče pomnožiti matrike 2 krat 2 v samo sedmih množilnih korakih in 18 seštevanjih. Dve leti pozneje je računalniški znanstvenik Shmuel Winograd dokazal, da je sedem dejansko absolutni minimum za matrike 2 krat 2.

Strassen je izkoristil isto idejo, da bi pokazal, da je vse večje n-z-n matrike je mogoče pomnožiti tudi v manj kot n³ koraki. Ključni element v tej strategiji vključuje postopek, imenovan dekompozicija – razčlenitev velike matrike na zaporedoma manjše podmatrike, ki so lahko na koncu tako majhne kot 2 krat 2 ali celo 1 krat 1 (to so samo posamezne številke).

Utemeljitev za razdelitev ogromnega niza na majhne koščke je precej preprosta Virginia Vassilevska Williams, računalničar na tehnološkem inštitutu v Massachusettsu in soavtor enega od novih člankov. "Človeku je težko pogledati veliko matriko (recimo, velikosti 100 krat 100) in pomisliti na najboljši možni algoritem," je dejala Vassilevska Williams. Tudi matrike 3 krat 3 še niso v celoti razrešene. "Kljub temu lahko uporabimo hiter algoritem, ki smo ga že razvili za majhne matrike, da dobimo tudi hiter algoritem za večje matrike."

Raziskovalci so ugotovili, da je ključ do hitrosti zmanjšanje števila korakov množenja in znižanje tega eksponenta n³ (za standardno metodo), kolikor lahko. Najnižja možna vrednost, n², je v bistvu toliko časa, kolikor traja samo pisanje odgovora. Računalniški znanstveniki ta eksponent imenujejo omega, ω, z n^ω je najmanj možnih korakov, potrebnih za uspešno množenje dveh n-z-n matrice kot n zelo zraste. "Bistvo tega dela," je dejal Zhou, ki je bil tudi soavtor prispevka iz januarja 2024, "je videti, kako blizu 2 se lahko približate in ali je to mogoče doseči v teoriji."

Lasersko ostrenje

Leta 1986 je Strassen doživel še en velik preboj, ko je Uvedeno tako imenovana laserska metoda za matrično množenje. Strassen ga je uporabil za določitev zgornje vrednosti za omega 2.48. Medtem ko je metoda le en korak pri velikih množenjih matrik, je ena najpomembnejših, ker so jo raziskovalci še naprej izboljševali.

Leto pozneje sta Winograd in Don Coppersmith predstavila nov algoritem, ki je lepo dopolnjeval lasersko metodo. Ta kombinacija orodij se je pojavila v skoraj vseh poznejših prizadevanjih za pospešitev množenja matrik.

Tukaj je poenostavljen način razmišljanja o tem, kako se ti različni elementi ujemajo. Začnimo z dvema velikima matricama, A in B, ki ju želite pomnožiti. Najprej jih razstavite na številne manjše podmatrice ali bloke, kot jih včasih imenujemo. Nato lahko uporabite Coppersmithov in Winogradov algoritem, ki služi kot nekakšen priročnik z navodili za rokovanje in končno sestavljanje blokov. "Pove mi, kaj naj pomnožim in kaj dodam ter kateri vnosi kam gredo" v produktni matriki C, je dejala Vassilevska Williams. "To je samo recept za izgradnjo C iz A in B."

Vendar obstaja ulov: včasih na koncu dobite bloke, ki imajo skupne vnose. Če bi jih pustili v izdelku, bi bilo podobno dvakratnemu štetju teh vnosov, zato se morate na neki točki znebiti teh podvojenih izrazov, imenovanih prekrivanja. Raziskovalci to naredijo tako, da "ubijejo" bloke, v katerih so - nastavijo njihove komponente na nič, da jih odstranijo iz izračuna.

Tu končno nastopi Strassenova laserska metoda. "Laserska metoda običajno deluje zelo dobro in na splošno najde dober način za ubijanje podskupine blokov, da se odstrani prekrivanje," je dejal Le Gall. Ko je laser odstranil ali "požgal" vsa prekrivanja, lahko sestavite končno matriko izdelka, C.

Če združimo te različne tehnike, dobimo algoritem za množenje dveh matrik z namenoma skromnim skupnim številom množenj - vsaj v teoriji. Laserska metoda ni mišljena kot praktična; to je le način za razmišljanje o idealnem načinu za množenje matrik. "Metode nikoli ne izvajamo [na računalniku]," je dejal Zhou. "Analiziramo ga."

In ta analiza je vodila do največjega izboljšanja omega v več kot desetletju.

Najdena je izguba

Članek Duana, Zhouja in Wuja iz prejšnjega poletja je pokazal, da bi lahko Strassenov postopek še vedno znatno pospešili. Vse je bilo zaradi koncepta, ki so ga poimenovali skrita izguba, zakopanega globoko v prejšnjih analizah - "posledica nenamernega ubijanja preveč blokov," je dejal Zhou.

Laserska metoda deluje tako, da bloke s prekrivanjem označi kot smeti, namenjene za odlaganje; drugi bloki se štejejo za vredne in bodo shranjeni. Izbirni postopek pa je nekoliko naključen. Blok, ocenjen kot smeti, se lahko kljub vsemu izkaže za uporabnega. To ni bilo popolno presenečenje, a s preučevanjem številnih teh naključnih izbir je Duanova ekipa ugotovila, da laserska metoda sistematično podcenjuje bloke: več blokov je treba shraniti in manj zavreči. In kot je običajno, manj odpadkov pomeni večjo učinkovitost.

"Zmožnost ohranjanja več blokov brez prekrivanja tako vodi do ... hitrejšega algoritma množenja matrike," je dejal Le Gall.

Potem ko je dokazala obstoj te izgube, je Duanova ekipa spremenila način, kako je laserska metoda označevala bloke, s čimer se je količina odpadkov znatno zmanjšala. Posledično so postavili novo zgornjo mejo za omega na približno 2.371866 - izboljšanje prejšnje zgornje meje 2.3728596, postavljeno leta 2020 avtorja Josh Alman in Vassilevska Williams. To se morda zdi skromna sprememba, saj se meja zniža le za približno 0.001. Vendar je to največji napredek, ki so ga znanstveniki opazili od leta 2010. Rezultat Vassilevske Williams in Almana iz leta 2020 je za primerjavo izboljšal svojega predhodnika le za 0.00001.

Toda tisto, kar je najbolj vznemirljivo za raziskovalce, ni le nov rekord sam - ki ni trajal dolgo. Dejstvo je tudi, da je časopis razkril novo pot za izboljšave, ki je bila do takrat popolnoma neopažena. Skoraj štiri desetletja se vsi zanašajo na isto lasersko metodo, je dejal Le Gall. "Potem so ugotovili, da lahko storimo bolje."

Članek iz januarja 2024 je izboljšal ta novi pristop in omogočil Vassilevski Williams, Zhouju in njunima soavtorjema dodatno zmanjšanje skrite izgube. To je pripeljalo do dodatnega izboljšanja zgornje meje omega in jo zmanjšalo na 2.371552. Avtorji so to isto tehniko posplošili tudi za izboljšanje postopka množenja za pravokotne (n-z-m) matrike — postopek, ki se uporablja v teoriji grafov, strojnem učenju in drugih področjih.

Nekaj ​​nadaljnjega napredka v tej smeri je vse prej kot gotovo, vendar obstajajo omejitve. Leta 2015 Le Gall in dva sodelavca dokazano da trenutni pristop – laserska metoda skupaj z receptom Coppersmith-Winograd – ne more dati omege pod 2.3078. Za nadaljnje izboljšave, je dejal Le Gall, "morate izboljšati prvotni [pristop] Coppersmitha in Winograda, ki se od leta 1987 ni zares spremenil.«. Toda doslej še nihče ni našel boljšega načina. Morda ga niti ni.

"Izboljšanje omega je pravzaprav del razumevanja tega problema," je dejal Zhou. »Če lahko dobro razumemo problem, potem lahko oblikujemo boljše algoritme zanj. [In] ljudje so še vedno v zelo zgodnjih fazah razumevanja tega prastarega problema.”