Forum » Znanost in tehnologija » Kvadriranje matrike
Kvadriranje matrike
Sergio ::
Po kmecko. Osem produktov, stiri sestevanja, 4 pomnilniske lokacije.
Nimas tuki kej praskat :)
a*a + b*c
a*b + b*d
a*c + c*d
b*c + d*d
Vrzes a, b, c in d v locene registre. Vecina procesorjev pre-emptivno zmnozi vrednosti med sabo, tako da mnozenje ne pobere dejansko nic.
Nato pa sestejes.
Rezultate zapises v 4 pomnilniske lokacije.
Nimas kej praskat.
Nimas tuki kej praskat :)
a*a + b*c
a*b + b*d
a*c + c*d
b*c + d*d
Vrzes a, b, c in d v locene registre. Vecina procesorjev pre-emptivno zmnozi vrednosti med sabo, tako da mnozenje ne pobere dejansko nic.
Nato pa sestejes.
Rezultate zapises v 4 pomnilniske lokacije.
Nimas kej praskat.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Sergio ::
Seveda pa ni sence dvoma v moji glavi, da si se hotel pohvalit z necim, ne pa samo sprasevat, kako se kvadrira poljubno 2x2 matriko. To zna vsak srednjesolec :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Jah ne. Že cel večer po netu praskam (ob mojem znanju Googla) en optimalen način za tole. Pa ne najdem. Zato me zanima.
Sergio ::
Najbrz zato, ker ni kej praskat pri tukaj za 'optimizacije'. Se vedno je to samo navadna 2x2 matrika.
Razen ce je matrika posebna in ne splosna. Za to imas pa mathworld.
Razen ce je matrika posebna in ne splosna. Za to imas pa mathworld.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Praviš, "dej v Critticall, če sta tko pametna s Critticallom oba, ne nas daviti tuki s tem ..."
Maš point. Sam ne morva midva lih vsega, ane?
Maš point. Sam ne morva midva lih vsega, ane?
Sergio ::
Pravim, da ima zato 'puney' matematicne naloge, ze procesor hardversko v sebi dosti optimizacij. Crittical pri mnozenju 2x2 matrik ne more dosti, pravzaprav zelo malo.
Don't get me wrong, ne trdim to za n*n matrike.
Ampak za 2x2 je pa to stvar stevila procesorjevih ciklov. In tipa procesorja. In stevila registrov. In zmogljivosti registrov. In njegovega cevovoda. In branch predictiona. In pomoznih registrov, kjer se izvajajo operacije samodejo. Etc etc etc. :)
Don't get me wrong, ne trdim to za n*n matrike.
Ampak za 2x2 je pa to stvar stevila procesorjevih ciklov. In tipa procesorja. In stevila registrov. In zmogljivosti registrov. In njegovega cevovoda. In branch predictiona. In pomoznih registrov, kjer se izvajajo operacije samodejo. Etc etc etc. :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Jah, mene zanima zaenkrat samo algoritem. Njegova implementacija v procesor pride potem, ko je algoritem optimalen. Ko ima recimo 7 množenj in 4 seštevanja. Kej tacga.
Sergio ::
Sej ze ima 7 mnozenj. :)
Pay attention. :)
Pay attention. :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Sergio ::
Heh, prakticno jih je 0. Ce imas dober procesor.
Ampak glejmo na to iz kmeckega vidika. In recimo takole:
Sestevanje pobere 5 sekund. Mnozenje 10 sekund. Pisanje matrike na list 3 sekunde.
To dela Janez.
Vse, kar lahko Janez naredi, da si skrajsa cas 8*10 + 4*5 + 3 sekunde je to:
Rezultat b*c si zapomni in ga uporabi.
Cas si skrajsa za 10 sekund.
To je pa tudi vse.
Ampak ves, procesorji ne delajo tako kot Janez :). Tako da trdim, da je se slabse, ce si ti shranjujes rezultat v pomnilnik, ker to terja vec casa, kot pa da nadaljujes z mnozenjem v registrih.
A prihajava pocasi na skupno vejo?
Ampak glejmo na to iz kmeckega vidika. In recimo takole:
Sestevanje pobere 5 sekund. Mnozenje 10 sekund. Pisanje matrike na list 3 sekunde.
To dela Janez.
Vse, kar lahko Janez naredi, da si skrajsa cas 8*10 + 4*5 + 3 sekunde je to:
Rezultat b*c si zapomni in ga uporabi.
Cas si skrajsa za 10 sekund.
To je pa tudi vse.
Ampak ves, procesorji ne delajo tako kot Janez :). Tako da trdim, da je se slabse, ce si ti shranjujes rezultat v pomnilnik, ker to terja vec casa, kot pa da nadaljujes z mnozenjem v registrih.
A prihajava pocasi na skupno vejo?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Jest (za spremembo) nič ne trdim. Potem ko sem prebrskal cel net, ne vem kako se v najmanj korakih kvadrira matriko 2X2.
Zdej se pa meni včasih zgodi, da mam kaj v spominu ali na kakšnem papirju, česar na netu ni. Me pa zanima, če se da kje zbrskat iz kakšnega kota (spomina) kakšen skrajšan način za kvadriranje matrik 2X2.
p.s.
2X3 se jih ne da kvadrirat in take modrosti so mi jasne.
Zdej se pa meni včasih zgodi, da mam kaj v spominu ali na kakšnem papirju, česar na netu ni. Me pa zanima, če se da kje zbrskat iz kakšnega kota (spomina) kakšen skrajšan način za kvadriranje matrik 2X2.
p.s.
2X3 se jih ne da kvadrirat in take modrosti so mi jasne.
Eschelon ::
Za 2x2 si ne moreš pomagat z ovinki. Za večje matrike se pa da malo pogoljufati, če so "redke". Za to se uporablja LAPACK (oz. SCALAPACK za paralelizacijo).
P.S.: Če najdeš kako ne-fortran scalapack zadevo za windowse (in po možnosti kako O.K. dokumentacijo), se priporočam - zadevo sem nekaj časa nazaj precej iskal po netu, pa nisem našel nič lepo serviranega.
P.S.: Če najdeš kako ne-fortran scalapack zadevo za windowse (in po možnosti kako O.K. dokumentacijo), se priporočam - zadevo sem nekaj časa nazaj precej iskal po netu, pa nisem našel nič lepo serviranega.
Vedeti, razumeti, znati.
Thomas ::
Ja. Tudi se nekoliko lahko "goljufa" za velike matrike s Strasserjevo formulo. Pri majhnih je pa ta Strasser sama izguba - pribitek. Potem maš še Winograda, kar je pa zelo ista. Šele pri (zelo) velikih matrikah se začenja poznati.
Thomas ::
Critticall prav tkole:
c12=a11+a22;
c12=c12*a12;
critticall3=a12*a21;
c11=a11*a11;
c11=c11+critticall3;
c22=a22*a22;
c22=c22+critticall3;
critticall3=a21*a11;
c21=a22*a21;
c21=c21+critticall3;
10 vrstic torej. Če pa lahko posvinja vhodno matriko, pa 8.
c21=a21*a12;
c11=a11*a11;
c11=c11+c21;
c22=a22*a22;
c22=c22+c21;
a11=a11+a22;
c12=a11*a12;
c21=a11*a21;
Ne vem, a je že optimum. Sicer je čist jasno tole, ja. Bomo dal kuhat še mau.
c12=a11+a22;
c12=c12*a12;
critticall3=a12*a21;
c11=a11*a11;
c11=c11+critticall3;
c22=a22*a22;
c22=c22+critticall3;
critticall3=a21*a11;
c21=a22*a21;
c21=c21+critticall3;
10 vrstic torej. Če pa lahko posvinja vhodno matriko, pa 8.
c21=a21*a12;
c11=a11*a11;
c11=c11+c21;
c22=a22*a22;
c22=c22+c21;
a11=a11+a22;
c12=a11*a12;
c21=a11*a21;
Ne vem, a je že optimum. Sicer je čist jasno tole, ja. Bomo dal kuhat še mau.
Thomas ::
Če je pa ne svinja (input matrike), pa tkole:
c21=a21*a12;
c11=a11*a11;
c11=c11+c21;
c22=a22*a22;
c22=c22+c21;
temp=a11+a22;
c12=temp*a12;
c21=temp*a21;
V bistvu čist jasno in nič posebnega. Ampak uporabte, kadar tako nanese.
c21=a21*a12;
c11=a11*a11;
c11=c11+c21;
c22=a22*a22;
c22=c22+c21;
temp=a11+a22;
c12=temp*a12;
c21=temp*a21;
V bistvu čist jasno in nič posebnega. Ampak uporabte, kadar tako nanese.
Zgodovina sprememb…
- spremenil: Thomas ()
Thomas ::
Ergo, tkole se kvadrira 2X2 matrika:
C21=A21*A12;
C11=A11*A11;
C11=C11+C21;
C22=A22*A22;
C22=C22+C21;
X=A11+A22;
C12=X*A12;
C21=X*A21;
Zanimivo je to, da če matriko skvadriramo samo vase, še vedno rabimo 8 vrstic. Vsega. 5 množenj in 3 seštevanja.
Če je pa recimo vedno 0 v zgornjem levem kotu, je dovolj 5 vrstic.
Vsaka matrika je svoja niša. Kako se množi, kako se potencira, transponira ... Kolikor niš, toliko algoritmov.
C21=A21*A12;
C11=A11*A11;
C11=C11+C21;
C22=A22*A22;
C22=C22+C21;
X=A11+A22;
C12=X*A12;
C21=X*A21;
Zanimivo je to, da če matriko skvadriramo samo vase, še vedno rabimo 8 vrstic. Vsega. 5 množenj in 3 seštevanja.
Če je pa recimo vedno 0 v zgornjem levem kotu, je dovolj 5 vrstic.
Vsaka matrika je svoja niša. Kako se množi, kako se potencira, transponira ... Kolikor niš, toliko algoritmov.
Sergio ::
Ja, ampak ugotavljanje niše pri 2x2 matrikah stane več, kot pa množenje poljubne 2x2 matrike z dummy algoritmom.
Pejt na 4x4, pa se bomo pogovarjal. :)
Pejt na 4x4, pa se bomo pogovarjal. :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Matrika 2X2 je sama niša!
Prav tako je možen primer, ko je vnaprej znano, da gre za podnišo, z zgornjim levim (ali katerimkoli) elementom obvezno enakim 0. Enakim 1.
Možne so matrike samo s potencami števila 2.
Takih primerov je dobesedno milijone - in seveda še več.
Prav tako je možen primer, ko je vnaprej znano, da gre za podnišo, z zgornjim levim (ali katerimkoli) elementom obvezno enakim 0. Enakim 1.
Možne so matrike samo s potencami števila 2.
Takih primerov je dobesedno milijone - in seveda še več.
Thomas ::
No, tisto modrost, da za sodobne vektorskoskalarne procesorje to itak ni noben problem in kako delajo za vse večne čase najbolje kar na običajnem, naivnem algoritmu ... sem pa že slišal. Samo ni modrost.
Sergio ::
Za 2x2 matriko je.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Sej mi je jasno. Zate je formula ki si jo dal zgoraj brezprizivna.
8 množenj (7, če en rezultat shranimo) in 4 seštevanja so najmanj kar se da in to je to.
Če se da recimo s 5 množenji in 3 seštevanji, to nima, ni imelo in ne bo nikoli imelo nobenega pomena whatsoever.
Ker itak si vedu, da se to tako da. Ali pa že nekdo je vedu.
Samo nima smisla tko računat. Stoletne izkušnje so nas naučile, da je tako najbolje.
8 množenj (7, če en rezultat shranimo) in 4 seštevanja so najmanj kar se da in to je to.
Če se da recimo s 5 množenji in 3 seštevanji, to nima, ni imelo in ne bo nikoli imelo nobenega pomena whatsoever.
Ker itak si vedu, da se to tako da. Ali pa že nekdo je vedu.
Samo nima smisla tko računat. Stoletne izkušnje so nas naučile, da je tako najbolje.
teoo ::
off topic
a je to splošno znana zadeva? kvadrat števila n je enak vsoti n zaporednih lihih števil.
n^2=sum(1-n)[2n-1]
nimam pojma a sm to že v osnovni šoli zvedu al ne? katera vrsta je to?
a je to splošno znana zadeva? kvadrat števila n je enak vsoti n zaporednih lihih števil.
n^2=sum(1-n)[2n-1]
nimam pojma a sm to že v osnovni šoli zvedu al ne? katera vrsta je to?
Sergio ::
Thomas: ne razumeš me. Očitno.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Sergio ::
In ker je nepoznavanje osnov računalniške arhitekture izgleda prevelik zalogaj, da bi se dalo vsaj konstruktivno razpravljati, se umikam iz debate.
Ker si spet pojebal celotno veselje do debate s tem, da si me hotel potlačit.
Očitno ne veš dovolj o rač. arhitekturi.
Ne. NIČ ne veš o tem, če boš trdil, da se SPLAČA optimizirati kvadriranje 2x2 matrike iz stališča porabljenega procesoskega časa.
Dokler ne pokapiraš tega ... boš pač druge tlačil v nič v debatah.
Mene zagotovo ne.
Priporočam v branje dve knjigi od prof. Dušana Kodeka. Arhitektura rač sistemov, 2001, in Mikroprocesorski sistemi, 1993.
Over & out.
Ker si spet pojebal celotno veselje do debate s tem, da si me hotel potlačit.
Očitno ne veš dovolj o rač. arhitekturi.
Ne. NIČ ne veš o tem, če boš trdil, da se SPLAČA optimizirati kvadriranje 2x2 matrike iz stališča porabljenega procesoskega časa.
Dokler ne pokapiraš tega ... boš pač druge tlačil v nič v debatah.
Mene zagotovo ne.
Priporočam v branje dve knjigi od prof. Dušana Kodeka. Arhitektura rač sistemov, 2001, in Mikroprocesorski sistemi, 1993.
Over & out.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Tremor, je znano in je off topic.
Kaj te ne razumem Sergio? Praviš, da tale optimizacija nima nobenega smisla, razen za peš računanje. V nobenem današnjem programu in na nobenem procesorju.
Kaj te ne razumem Sergio? Praviš, da tale optimizacija nima nobenega smisla, razen za peš računanje. V nobenem današnjem programu in na nobenem procesorju.
Thomas ::
|A|*|B|-|B|*|A|
C11=b21*a12;
b21=a21*b12;
a21=a12*b22;
b22=a11*b12;
b22=b22+a21;
temp=b11*a12;
C12=b12*a22;
C12=C12+temp;
C12=b22-C12;
C11=b21-C11;
???
C11=b21*a12;
b21=a21*b12;
a21=a12*b22;
b22=a11*b12;
b22=b22+a21;
temp=b11*a12;
C12=b12*a22;
C12=C12+temp;
C12=b22-C12;
C11=b21-C11;
???
Thomas ::
|B|=|A|*|A|-|A|
b11=a11+a22;
b12=b11*a12;
b12=b12-a12;
x=a22*a22;
b11=a21*a12;
b11=b11-a22;
b11=b11+x;
Bp?
b11=a11+a22;
b12=b11*a12;
b12=b12-a12;
x=a22*a22;
b11=a21*a12;
b11=b11-a22;
b11=b11+x;
Bp?
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | razstaviti izrazOddelek: Šola | 2862 (2482) | Math Freak |
| » | matematika-pomočOddelek: Šola | 2352 (2103) | Math Freak |
| » | Strassenovo množenje matrikOddelek: Programiranje | 2189 (1930) | eXoo |
| » | excel+visual basicOddelek: Pomoč in nasveti | 1569 (1456) | švrk |
| » | Intelektualna lastnina in copyleft (strani: 1 2 3 4 5 6 )Oddelek: Novice / Industrijska lastnina | 15496 (15496) | Exilian |