Objavljeno: 11.10.2022 05:00 | Teme: umetna inteligenca

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(n3). Ž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(n2.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.

Več novic

Naroči se na redna tedenska ali mesečna obvestila o novih prispevkih na naši spletni strani!

Komentirajo lahko le prijavljeni uporabniki

Najbolj brano

  • Android vam bo povedal, ali vam policija prisluškuje

    Čedalje popularnejši način prisluškovanja in prestrezanja podatkov z mobilnih telefonov je uporaba lažnih baznih postaj (IMSI catcher), ki jih imajo organi pregona v nekaterih državah, lahko pa tudi drugi akterji. Na takšno napravo se povežejo vsi telefoni v okolici, saj njen signal preglasi legitimne bazne postaje, upravljavec pa potem zlahka prestreza komunikacijo. Uporabnik tega početja praktično ne more zaznati.

    Objavljeno: 1.7.2025 07:00
  • Tisoče severnokorejskih uslužbencev prikrito na daljavo delalo v ameriških podjetjih

    Ameriško pravosodno ministrstvo je vložilo obtožnice zoper devet ljudi, ki so skrbeli za prikrito zaposlovanje računalnikarjev iz Severne Koreje za delo na daljavo v ameriških podjetjih. En Američan, šest Kitajcev in dva Tajvanca so obtoženi prevare, pranja denarja, kraje identitete, nepooblaščenega dostopa v računalniški sistem in kršenja mednarodnih sankcij.

    Objavljeno: 2.7.2025 07:00
  • Podjetja nočejo Copilota, ker zaposleni raje uporabljajo ChatGPT

    Microsoft kljub velikim naporom (beri: finančnemu vložku) podjetjem težko proda storitve umetne inteligence Copilot.

    Objavljeno: 27.6.2025 09:00
  • Naprava, ki z laserji uničuje komarje

    Čeprav še nimamo letečih avtomobilov ali robotov strežnikov, lahko zdaj naročimo nekaj, o čemer smo od nekdaj sanjali - lasersko napravo, ki zazna in ubije komarja v nekaj milisekundah.

    Objavljeno: 3.7.2025 11:00
  • Kitajski prenosniki so dve leti za zahodnimi

    Čeprav se Kitajci močno trudijo in izdatno investirajo v domači razvoj in proizvodnjo čipov, so še vedno vsaj dve generaciji za zahodnimi izdelki. To izkazuje tudi najnovejši Huaweijev prenosnik MateBook Fold Ultimate, ki poganja lastni HarmonyOS in ima same kitajske komponente. A te v primerjavi z zahodnimi zaostajajo.

    Objavljeno: 25.6.2025 07:00
  • Pametna očala s samodejnim ostrenjem bi lahko nadomestila bifokalna stekla

    Finsko podjetje IXI razvija inovativna očala z lečami, ki se samodejno ostrijo glede na pogled uporabnika. 

    Objavljeno: 23.6.2025 10:00 | Teme: pametna očala
 
  • Polja označena z * je potrebno obvezno izpolniti
  • Pošlji