EPISTHMONIKOS UPOLOGISMOS I 1. PÏte lËme Ïti Ëna

EPISTHMONIKOS UPOLOGISMOS
I
Exètash Proìdou (Dek. 2004): APANTHSEIS
I.
(25 b.)
1. Pìte lème ìti èna sÔsthma arijmhtik c kinht c upodiastol c ikanopoieÐ th sunj kh akriboÔc stroggÔleushc?
2. Na epiqeirhmatolog sete, me bˆsh tic timèc twn
Ω, Φmin
gia na deÐxete ìti h paragontopoÐhsh
LU
enìc
tetragwnikoÔ mhtr¸ou parèqei th dunatìthta kal c apìdoshc se sust mata me ierarqik mn mh (1-2 sunoptikèc protˆseic arkoÔn).
Apˆnthsh.
1. àna sÔsthma a.k.u. ikanopoieÐ th sunj kh akriboÔc stroggÔleushc ìtan to apotèlesma opoiasd pote apì
tic stoiqei¸deic prˆxeic thc arijmhtik c sto sÔsthma kai se dedomèna
x, y
pou eÐnai a.k.u. eÐnai o a.k.u.
pou ja proèkupte an ekteloÔsame thn prˆxh me arijmhtik ˆpeirhc akrÐbeiac kai metˆ strogguleÔame.
Eidikìtera,
˜
fl(x y) = xy
ìpou
˜
eÐnai h ulopoÐhsh thc prˆxhc
sto sÔsthma a.k.u.
A = LU aforˆ ston upologismì twn paragìntwn L, U apì to A. Epomènwc apaitoÔntai
Φmin = 2n2 load-store. EpÐshc, eÐnai gnwstì ìti h paragontopoÐhsh LU apaiteÐ perÐpou 2n3 /3
a.k.u. Epomènwc µmin = O(1/n) ìpwc kai sta BLAS-3, epomènwc faÐnetai ìti upˆrqei topikìthta
2. H paragontopoÐhsh
toulˆqiston
prˆxeic
(mènei na gÐnoun oi katˆllhlec ulopoi seic!).
II. (25 b.) Na epilèxete poia apì ta parakˆtw epistrèfoun logikì alhjèc (1) kai poia ìqi (0) kai na sqoliˆsete tic
apant seic sac. JewroÔme ìti qrhsimopoieÐtai arijmhtik kinht c upodiastol c IEEE dipl c akrÐbeiac (me bajmiaÐa upokanonikopoÐhsh). To realmax sumbolÐzei to mègisto peperasmèno jetikì arijmì kinht c upodiastol c,
realmin to mikrìtero kanonikopoihmèno jetikì a.k.u. kai == eÐnai to sÔmbolo logik c isìthtac:
a)
realmax + 1.0 == ∞.
b)
Inf/Inf == NaN.
g)
realmin/2 == 0.
d)
0/0 == Inf.
Apˆnthsh.
realmax eÐnai 1023. Gia na gÐnei h prìsjesh me to y = 1.0, ja prèpei na diairèsoume
y ètsi ¸ste o ekjèthc tou na gÐnei 1023. Kˆje diaÐresh me to 2 antistoiqeÐ se olÐsjhsh tou pio shmantikoÔ
bit thc ourˆc tou y katˆ mia jèsh proc ta dexiˆ. To m koc thc ourˆc sthn arijmhtik IEEE dipl c akrÐbeiac
eÐnai 52, epomènwc metˆ apì 53 olisj seic proc ta dexiˆ, h ourˆ ja mhdenisteÐ. Epomènwc realmax+1.0 ==
realmax.
a) Lˆjoc (0): O ekjèthc tou
to
b) Swstì (1): To apotèlesma thc diaÐreshc den orÐzetai.
g) Lˆjoc (0): To sÔsthma uposthrÐzei bajmiaÐa upokanonikopoÐhsh. To apotèlesma thc diaÐreshc ja eÐnai mh
kanonikopoihmènoc kai mh mhdenikìc arijmìc k.u.
d) Lˆjoc (0): To apotèlesma thc diaÐreshc
III.
0/0
den orÐzetai.
(25 b.) Qrhsimopoi¸ntac emprìc anˆlush sfˆlmatoc, na deÐxete ìti o parakˆtw algìrijmoc
n = 6; s=0; for j = 1:n, s = s+ x(j)*x(j); end;
upologÐzei to
s me mikrì sqetikì sfˆlma. Eidikìtera, na deÐxete ìla ta b mata thc anˆlushc kai na upologÐsete
u, tou sust matoc. Mpoupojèsete ìti kˆje stoiqeÐo x(j) eÐnai arijmìc kinht c upodiastol c kai ìti x(j) ∗ x(j) < Inf, ìpou
(mikrì) frˆgma gia to emprìc sqetikì sfˆlma sunart sei thc monˆdac stroggÔleushc,
reÐte na
Inf
eÐnai to {ˆpeiro} gia to qrhsimopoioÔmeno sÔsthma a.k.u.
Apˆnthsh. Qrhsimopoi¸ntac tic gnwstèc sqèseic diˆdoshc sfˆlmatoc, kai jètontac gia eukolÐa
σ=
σ̂
P6
2
j=1 xj
kai
σ̂
to
s
x(j) ≡ ξj
kai
pou upologÐzetai me a.k.u. apì ton parapˆnw k¸dika, èqoume:
= (((((ξ12 < 1 > +ξ22 < 1 >) < 1 > +ξ32 < 1 >) < 1 > +ξ42 < 1 >) < 1 > +ξ52 < 1 >) < 1 > +ξ52 < 1 >) < 1 >
= ξ12 < 6 > +ξ22 < 6 > +ξ32 < 5 > +ξ42 < 4 > +ξ52 < 3 > +ξ62 < 2 >
= ξ12 (1 + θ6 ) + ξ22 (1 + θ̂6 ) + ξ32 (1 + θ5 ) + ξ42 (1 + θ4 ) + ξ52 (1 + θ3 ) + ξ62 (1 + θ2 )
Epomènwc,
|σ̂ − σ| = |ξ12 θ6 + ξ22 θ̂6 + ξ32 θ5 + ξ42 θ4 + ξ52 θ3 + ξ62 θ2 |
≤ |ξ12 ||θ6 | + |ξ22 ||θ̂6 | + |ξ32 ||θ5 ||ξ42 ||θ4 | + |ξ52 ||θ3 | + |ξ62 ||θ2 |
≤ ξ12 γ6 + ξ22 γ6 + ξ32 γ5 + ξ42 γ4 + ξ52 γ3 + ξ62 γ2
ìpou
γj = ju/(1 − ju),
epomènwc, epeid γ6 > γ5 , ..., γ2 ,
|σ̂ − σ|
|σ|
V.
≤ γ6 = 6u/(1 − 6u).
(25 b.) (Sto er¸thma autì ja sac eÐnai qr simoc o tÔpoc (Sherman-Morrison):
(A + uv > )−1 = A−1 − A−1
uv >
A−1
1 + v > A−1 u
u, v ∈ Rn .) àstw ìti èqete diajèsimouc touc parˆgontec L kai U thc
n×n
paragontopoÐhshc LU enìc genikoÔ mhtr¸ou A ∈ R
, dhl. A = LU , kai ìti gÐnetai h ex c {ananèwsh}: AntikajÐstatai h teleutaÐa st lh tou A me èna ˆllo diˆnusma, èstw p. An gnwrÐzete ìti to nèo mhtr¸o
B = [A(:, 1), ..., A(:, n − 1), p] eÐnai epÐshc antistrèyimo, na perigrˆyete, me b mata pou antistoiqoÔn se entolèc
2
tÔpou BLAS ènan apodotikì trìpo epÐlushc tou sust matoc Bx = y pou na kostÐzei Ω = α2 n + α1 n + α0
prˆxeic, ìpou oi suntelestèc α1 kai α2 eÐnai stajerèc. EpÐshc na breÐte touc suntelestèc autoÔc. Gia pl rh
bajmì ja prèpei na qrhsimopoi sete kai entolèc tÔpou BLAS-3 qwrÐc na aux sete tautìqrona kai to sunolikì
kìstoc a.k.u. Ω gia to prìgramma.
me katˆllhla epilegmèna dianÔsmata
Prosoq :ArkeÐ na perigrˆyete me saf neia ti ekteleÐtai se kˆje b ma, se ti dedomèna, se poiˆ kathgorÐa
BLAS an kei. EpÐshc na analÔsete ta kìsth. Den qreiˆzetai na qrhsimopoi sete thn akrib onomatologÐa twn
BLAS. Gia parˆdeigma, an eÐqate na perigrˆyete ta b mata gia ton upologismì tou B = B + (Ax)y > , ìpou ta
x, y ∈ Rn kai A, B ∈ Rn×n , ja arkoÔse o parakˆtw pÐnakac (ta onìmata GEMV, GER den eÐnai aparaÐthta):
1.
2.
Upologismìc
Perigraf q = Ax
B = B + qy >
Pollaplasiasmìc mhtr¸o-diˆnusma ( KathgorÐa
Ananèwsh pr¸thc tˆxhc ( GEMV)
GER)
BLAS-2
BLAS-2
Sunolikì kìstoc
Apˆnthsh. ParathroÔme ìti
u = p − A(:, n)
kai
uv > = [0, ..., 0, p − A − (:, n)]
(mhtr¸o tˆxhc 1) epomènwc arkeÐ na epilèxoume
v = en .
Upologismìc
Perigraf u = p − A(:, n)
L[zu , zb ] = [u, b]
prˆxh tÔpou
2.
3.
U [zu , zb ] = [zu , zb ]
LÔsh ˆnw trigwnikoÔ
4.
x = zb + (zb (n)/(1 + zu (n)))zu
1.
n(2n − 1)
2n2
Ω = 4n2 − n
sAXPY
LÔsh kˆtw trigwnikoÔ sust matoc
me 1 sth diag. kai 2 dexiˆ mèlh ( Kìstoc (ìroi
BLAS-1
BLAS-3
O(n) kai O(n2 ))
n
2n(n − 1)
BLAS-3
2n2
BLAS-1
2n
α2 = 4, α1 = 1
TRSM)
me 2 dexiˆ mèlh ( Sunolikì kìstoc
ìpou
TRSM)
sAXPY
Ω = 4n2 + n + O(1)
KathgorÐa
epomènwc
zu (n), zb (n) eÐnai ta teleutaÐa stoiqeÐa twn dianusmˆtwn zu kai zb antÐstoiqa (dhl. bajmwtoÐ). Prosèxte ìti
v = en opìte h prˆxh v > [zu , zb ] (diˆnusma gramm epÐ mhtr¸o 2 eswterikˆ
sto parapˆnw axiopoi same to ìti
2
ginìmena) eÐnai tetrimmènh (den qreiˆzontai upologismoÐ). EpÐshc, an ektelèsoume to 1o b ma me apeujeÐac kl sh
sth
BLAS-1 sAXPY, to kìstoc ja eÐnai katˆ n megalÔtero,
±1 (mìno th mhdenik perÐptwsh).
kaj¸c h klasik sAXPY
den elègqei an o bajmwtìc
suntelest c eÐnai
ànac enallaktikìc (kai fjhnìteroc!) trìpoc epÐlushc, qwrÐc th qr sh tou tÔpou, eÐnai o akìloujoc: Parath-
LU = A epomènwc LU (:, j) = A(:, j) gia j = 1, ..., n. Epomènwc, an allˆxoume thn teleutaÐa st lh tou
A se p, h paragontopoÐhsh LU tou B ja èqei wc parˆgontec to Ðdio L kai wc U to Ũ = [U (:, 1), ..., U (:, n − 1), g],
ìpou oi pr¸tec n − 1 st lec eÐnai ìpwc prin kai h teleutaÐa ikanopoieÐ th sqèsh Lg = p. Epomènwc, mporoÔme na
upologÐsoume to g me mia lÔsh me to gnwstì kˆtw trigwnikì L. Epomènwc, mporoÔme na kˆnoume ta ex c b mata
gia na lÔsoume to Bx = y : 1) LÔnoume ta L[y, g] = [z, p] me BLAS-3 kai kìstoc 2n(n − 1) (lÔsh trigwnikoÔ me
2 dexiˆ mèlh kai monˆda sth diag¸nio). 2) Jètoume Ũ = [U (:, 1), ..., U (:, n − 1), g], opìte B = LŨ , kai lÔnoume
Ũ x = y wc proc x me BLAS-1 (lÔsh trigwnikoÔ sust matoc, kìstoc n2 .) Epomènwc to sunolikì kìstoc ja eÐnai
Ω = 3n2 − 2n.
roÔme ìti
3