Википедија

Algoritam množenja matrica — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Ред 31:
Tri petlje u iterativnom množenju matrica mogu se proizvoljno zameniti bez uticaja na tačnost ili asimptotsko vreme izvršenja algoritma. Međutim, red može imati značajan uticaj na praktičnu performansu zbog obrazaca pristupa memoriji i keš korišćenja algoritma. Koji redosled je najbolji takođe zavisi od toga da li se matrice čuvaju u redosledu prvo red, redosledu prvo kolona, ili mešavina oba.
 
KoknretnoKonkretno, u idealnom slučaju potpuno asocijativog keša koji se sastoji od ''M'' keš linija po ''b'' bajtova svaki, gorepomenuti algoritam je podoptimalan za ''A'' i ''B'' koji se čuvaju u redosledu prvo red. Kada je {{math|''n'' > {{sfrac|''M''''b''}}}}, svaka iteracija unutrašnje petlje vodi do promašaja keša kada se pristupa redu ''B''. To znači da algoritam snosi {{math|Θ(''n''<sup>3</sup>)}} keš promašaja u najgorem slučaju. Od 2010. godine, memorijske brzine upoređene sa brzinama procesora su takve da keš promašaji, a ne stvarni proračuni, dominiraju vremenom izvršenja za prilično velike matrice.
 
Optimalna varijanta iterativnog algoritma za ''A'' i ''B'' u rasporedu prvo red je verzija sa pločicama, gde je matrica implicitno podeljena na kvadratne pločice veličine {{math|√''M''}} {{math|√''M''}}
Преузето из „https://sr.wikipedia.org/wiki/Algoritam_množenja_matrica”