Umetna inteligenca izboljšala 50 let star algoritem za množenje matrik

V računalništvu so med najpomembnejšimi odkritji novi algoritmi, ki pohitrijo pogosta opravila. Tak primer je množenje matrik, ki ga današnji procesorji za izris grafike in druga opravila izvajajo milijonkrat, in še vedno poteka po algoritmu iz leta 1969. Sedaj pa je umetna inteligenca DeepMind AI odkrila nov, hitrejši algoritem.

Naivno množenje matrik terja množenje vrstic s stolpci, kar ima zahtevnost O(n³). Že leta 1969 je nemški matematik Volker Strassen odkril algoritem, ki za množenje dveh matrik dimenzij 2 x 2 namesto osmih množenj potrebuje sedem (in še nekaj operacij seštevanja, ki pa so bistveno hitrejše). Tak algoritem ima zahtevnost O(n^2.81), zato je hitrejši. Kasneje so odkrili algoritme, ki imajo še nižjo zahtevnost (nižji eksponent), a v praksi niso uporabni, ker imajo tako velike predfaktorje, da bi se pospešitev poznala šele pri tako ogromnih matrikah, ki jih v praksi nikoli ne srečamo. Take algoritme sicer imenujemo galaktični algoritmi.

Vrnimo se k DeepMindu. Njegova umetna inteligenca je odkrila algoritem, ki je hitrejši od Strassnovega že pri matrikah obvladljivih velikosti, kar je prvi oprijemljiv napredek v zadnjih 50 letih. Algoritem, ki ga je odkril, je matematično preverjen in pravilen, a neintuitiven in bi ga ljudje težko iznašli. Kako ga je iznašel DeepMind, ni jasno niti njegovim tvorcem. V resnici je našel cel kup algoritmov, odvisno od dimenzij matrike. Za matrike 4x4 je odkril 14.000 algoritmov, med katerimi je eden hitrejši od Strassnovega. To zadostuje.

Praktični testi so pokazali, da je algoritem na Nvidii V100 približno 10-20 odstotkov hitrejši od obstoječih algoritmov. To je sicer veliko, a vprašanje je, ali bodo pohitritve tudi na običajnih računalnikih tako opazne. A četudi bodo novosti uporabne le za superračunalnike, bo to imelo za znanost in svet velikanski pomen. Veliko računalniških simulacij, od kvantnokemijskih izračunov do napovedovanja vremena, je v svoji srži množenje matrik.

Nature

Delovanje algoritma Strassen.