ΕΠΙΣΤΗΜΟΝΙΚΟΣ ΥΠΟΛΟΓΙΣΜΟΣ Ι

Ονοματεπώνυμο: Αραβανής Κων/νος Α .Μ.:3628

1^η Εργαστηριακή άσκηση

Μέρος 0

Αρχικά θα περιγράψουμε το σύστημα στο οποίο τρέξαμε τα πειράματα μας:

Το σύστημα μας είχε το λειτουργικό Microsoft Windows Vista Business και ο επεξεργαστής

του ήταν ένας Intel Core Duo T2300 στα 1,66GHz. Είχαμε μία ιεραρχεία μνήμης δύο

επιπέδων με το πρώτο επίπεδο να αποτελείτε από δύο κρυφές μνήμες, η μία για data (L1 DCache)

και η άλλη για inst. (L1 D-Cache) και οι δύο των 32ΚBytes και με τα ακόλουθα

χαρακτηριστικά: 8 way set-associative, 64-byte line size. Η κύρια μνήμη (L2 Cache) μας

είχε μέγεθος 2048ΚBytes και ακριβώς τα ίδια χαρακτηριστικά με τις κρυφές. Όσον αφορά το

λογισμικό στο οποίο εκτελέστηκαν τα προγράμματα μας ήταν η Matlab 7.4 Η βιβλιοθήκη τώρα που χρησιμοποιείται από την Matlab για τις πραξεις BLASS συφωνα με το link:

http://www.mathworks.com/support/solutions/data/1-JDIO3.html?solution=1-JDIO3

είναι η Math Kernel Library (MKL) BLAS για τους Intel επεξεργαστές.

Μέρος Α

Στο μέρος αυτό της άσκησης μας ζητήθηκε να υλοποιήσουμε τον αλγόριθμο Strassen (με δική μας υλοποίηση ή από το διαδύκτιο). Τον αλγόριθμο τον βρήκα στο internet στο παρακάτω link:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=2360

Ο αλγόριθμος αυτός φαίνεται παρακάτω:

function C = strassen_3628(A, B, nmin)

%strassen_3628 Strassen's fast matrix multiplication algorithm.

% C = strassen_3628(A, B, NMIN), where A and B are matrices of % dimension

% a power of 2, computes the product C = A*B.

% Strassen's algorithm is used recursively until dimension <= % % NMIN

% is reached, at which point standard multiplication is used.

% The default is NMIN = 8 (which minimizes the total number of

% operations).

% Reference:

% V. Strassen, Gaussian elimination is not optimal,

% Numer. Math., 13 (1969), pp. 354-356.

if nargin < 3, nmin = 8; end

n = length(A);

if n ~= 2^( log2(n) )

error('The matrix dimension must be a power of 2.')

end

if n <= nmin

C = A*B;

else

m = n/2; i = 1:m; j = m+1:n;

P1 = strassen_3628( A(i,i)+A(j,j), B(i,i)+B(j,j), nmin);

P2 = strassen_3628( A(j,i)+A(j,j), B(i,i), nmin);

P3 = strassen_3628( A(i,i), B(i,j)-B(j,j), nmin);

P4 = strassen_3628( A(j,j), B(j,i)-B(i,i), nmin);

P5 = strassen_3628( A(i,i)+A(i,j), B(j,j), nmin);

P6 = strassen_3628( A(j,i)-A(i,i), B(i,i)+B(i,j), nmin);

P7 = strassen_3628( A(i,j)-A(j,j), B(j,i)+B(j,j), nmin);

C = [ P1+P4-P5+P7 P3+P5; P2+P4 P1+P3-P2+P6 ];

end

strassen_3628.m

Ο αλγόριθμος αυτός περιέχει τις προϋποθέσεις που ζητούνται στην άσκηση. Συγκεκριμένα επιτρέπει τον πολλαπλασιασμό μητρώων οποιασδήποτε διάστασης παρέχοντας συγχρόνως την δυνατότητα ο χρήστης να ορίζει το ελάχιστο μέγεθος των μητρώων από το οποίο και κάτω ο πολλαπλασιασμός θα γίνεται με τον κλασσικό τρόπο δηλαδή απευθείας στην Matlab, με βάση την τιμή που θα τεθεί το κατώφλι. Επίσης σε περίπτωση που ο χρήστης δεν ορίσει την τιμή κατωφλιού αυτό τίθεται αυτόματα στην τιμή 8.

1.Στο ερώτημα αυτό συγκρίνουμε την mtimes με την strassen_3628. Συγκεκριμένα μετράμε το κόστος της strassen_3628 σε σχεση με το μέσο κόστος υπολογισμού για την mtimes σε μητρώα αντίστοιχων διαστάσεων. Τα μητρώα πάνω στα οποία γίναν τα πειπάματα είναι πυκνά διαστάσεων: 64x64, 128x128, 264x264, 512x512, 1024x1024 . Η κάθε μέτρηση έγινε για τιμές κατωφλιού 8, 16, 32, 64.

Ο κώδικας που χρησιμοποιήσαμε είναι ο ακόλουθος:

%arxikopoiisi tixaion mitroon C kai D diastaseon 1024x1024

C=rand(1024,1024);

D=rand(1024,1024);

for j=3:1:6

k=2^j;

for i=4:-1:0

%arxikopoiisi mitroon A kai B diastaseon sto 1o loop 64x64

% sto 2o loop 128x128

% sto 3o loop 264x264

% sto 4o loop 512x512

% sto 5o loop 1024x1024

A=C(1:2^i:1024,1:2^i:1024);

B=D(1:2^i:1024,1:2^i:1024);

%opos kai edo etsi kai sti klisi tis strassen ektelo mia fora prota tin

%praksi kathos panta i proti ektelesei epistrefei paraplanitika

%apotelesmata kai meta ksekino tin xronometrisi tis polles fores gia na

%paro ton meso oro

mtimes(A,B);

tic;

for l=1:1:25

mtimes(A,B);

end

Mtimes=toc/25

strassen_3628(A,B,k);

tic;

for l=1:1:25

strassen_3628(A,B,k);

end

%sto simeio afto ginetai i metrisi tou kostous tis strassen os

%pollaplasio tou mesou kostous ipologismou gia ti mtimesantistoixon

%diastaseon

Strassen_3628=(toc/25)/Mtimes

end

end

merosA_1.m

Συγκεντρωτικά τα αποτελέσματα των μετρήσεων μου φαίνονται στον παρακάτω πίνακα (πρόκειτει στην ουσία για τον μέσο χρόνο της strassen δια αυτόν της mtimes):

k/διαστάσεις μητρώων	64x64	128x128	256x256	512x512	1024x1024
8	34.9834	31.2563	27.8671	25.9118	23.3267
16	5.8894	5.9974	5.7941	5.4859	5.1268
32	2.1558	1.9200	2.0952	2.0999	2.0342
64	1.1402	1.2160	1.3560	1.4574	1.4327

merosA_1.txt

Απο τον παραπάνω πίνακα πίνακα φαίνεται οτι όσο μικροτερο το κατώφλι τόσο πιο πολύ χρόνο διαρκεί η strassen από την mtimes. Αυτό συμβαίνει γιατί όσο μικρότερο είναι το κατώφλι τόσο περισσότερες φορές εκτελείται η strassen αναδρομικά άρα τόσο περισσότερος χρόνος καταναλώνεται.

2.Στο σημείο αυτο της άσκησης θέλουμε να αποδελίξουμε οτι το εμπρός σφάλμα του θεωρητικά ταχέος strassen είναι χειρότερο από την κλασσική υλοποίηση, δηλαδη την mtimes.

Ο κώδικας που χρησιμοποιήσαμε για αυτό είναι ο ακόλουθος:

%meros A ipoerotima 2

%stoixeia ta opoia pollaplasiazoume me ta tuxaia mitroa pou arxikopoioume

%parakato oste na dimiourgisoume mitroa A, B me eksisou megala stoixeia,

%me eksisou mikra, me iso kai me "antidiametrika" antistoixa

a=[1e10;1e-10;1;1e10];

b=[1e10;1e-10;1;1e-10];

for i=1:1:4

%arxikopoiisi mitroon A kai B se arithmitiki diplis akriveias

A=a(i)*rand(256);

B=b(i)*rand(256);

%arikopoiisi mitroon C kai D se moni akriveia

C=single(A);

D=single(B);

%ektelesi pollaplasiasmou strassen me k=2 se arithmitiki monis

%akriveias

E_2=single(strassen_3628(C,D,2));

%ektelesi pollaplasiasmou strassen me k=16 se arithmitiki monis

%akriveias

E_16=single(strassen_3628(C,D,16));

%ektelesi pollaplasiasmou mtimes se arithmitiki monis akriveias

F=single(mtimes(C,D));

%ektelesi pollaplasiasmou se arithmitiki dilis akriveias

G=double(mtimes(double(A),double(B)));

%ipologismos eN kai eC gia strassen monia akriveias me k=2 kai mtimes

%diplis akriveias

eN_strassen_2=norm(E_2-G,2)/((eps('single')/2)*norm(G,2))

eC_strassen_2=max(max(abs(E_2-G)./((eps('single')/2)*abs(G))))

%ipologismos eN kai eC gia strassen monia akriveias me k=16 kai mtimes

%diplis akriveias

eN_strassen_16=norm(E_16-G,2)/((eps('single')/2)*norm(G,2))

eC_strassen_16=max(max(abs(E_16-G)./((eps('single')/2)*abs(G))))

%ipologismos eN kai eC gia mtimes monia akriveias kai mtimes diplis

%akriveias

eN_mtimes=norm(F-G,2)/((eps('single')/2)*norm(G,2))

eC_mtimes=max(max(abs(F-G)./((eps('single')/2)*abs(G))))

end

merosA_2.m

Συγκεντωτικά τα αποτελέσματα που λάβαμε ήταν τα παρακάτω:

Για strassen μονης ακρίβειας με k=2

ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΠΡΩΤΟΥ ΠΙΝΑΚΑ	ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΔΕΥΤΕΡΟΥ ΠΙΝΑΚΑ	eN	eC
Πολύ μεγάλες	Πολύ μεγάλες	9.7409	980.5700
Πολύ μικρές	Πολύ μικρές	7.5891	664.2161
Κανονικές	Κανονικές	8.6833	865.8161
Πολύ μεγάλες	Πολύ μικρες	9.5754	851.3267

merosA_2.txt

Για strassen μονης ακρίβειας με k=16

ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΠΡΩΤΟΥ ΠΙΝΑΚΑ	ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΔΕΥΤΕΡΟΥ ΠΙΝΑΚΑ	eN	eC
Πολύ μεγάλες	Πολύ μεγάλες	1.8249	122.3961
Πολύ μικρές	Πολύ μικρές	1.6814	114.4679
Κανονικές	Κανονικές	1.7180	110.5917
Πολύ μεγάλες	Πολύ μικρες	1.6396	113.8317

merosA_2.txt

Για mtimes μονης ακρίβειας

ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΠΡΩΤΟΥ ΠΙΝΑΚΑ	ΤΙΜΕΣ ΣΤΟΙΧΕΙΩΝ ΔΕΥΤΕΡΟΥ ΠΙΝΑΚΑ	eN	eC
Πολύ μεγάλες	Πολύ μεγάλες	0.0973	2.8324
Πολύ μικρές	Πολύ μικρές	0.0934	3.0715
Κανονικές	Κανονικές	0.0965	2.9746
Πολύ μεγάλες	Πολύ μικρες	0.0977	3.1041

merosA_2.txt

Από τους παραπάνω πίνακες και από τις τιμές των eN και eC επαληθεύεται ότι το εμπρός σφάλμα του θεωρητικά ταχέος strassen είναι χειρότερο από την κλασσική υλοποίηση και πιο συγκεκριμένα το σφάλμα είναι μεγαλύτερο όταν το κατώφλι είναι ίσο με 2 από ότι όταν είναι 16. Επίσης παρατηρούμε ότι ότι μητρώα και να επιλέξουμε, τα σφάλματα που προκύπτουν απο την εφαρμεγή της κάθε μεθόδου και λέγοντας μεθόδου εννοούμε strassen με κατώφλι 2, strassen με κατώφλι 16 και mtimes, είναι της ίδιας τάξης μεγέθους.

Όσον αφορά την επιλογή ενός μητρώου με πολύ μεγάλες τιμές στοιχείων και ενός με πολύ μικρές αυτή έγινε γιατί εκτελώντας πράξεις ανάμεσα σε τέτοια μητρώα η Matlab στην ουσία απαλοίφει το μητρώο με τις μικρές τιμες και επειδή όταν καλείτε η strassen με πολύ μικρό κατώφλι εκτελείτε αναδρομικά ακόμα περισσότερες φορες παρουσιαζονται πολυ μεγαλα σφάλματα eN και eC για την strassen με k=2. Εδώ αξίζει να σημειώσουμε τον οτι έναχαρακτηριστικό της strassen είναι ότι συνδιάζει σε προσθαφερέσεις τμήματα του κάθε πολλαπλασιστή.

Μέρος Β
Στο σημείο αυτό της άσκησης κάνουμε τον σχετικό έλεγχο για το αν ο δείκτης κατάστασης είναι ίσος με το c δηλαδή με το s1/sn σύμφωνα με τις οδηγίες που μας δόθηκαν απο την άσκηση για την κατασκευή μητρώου M(n,c).

Ο κώδικας που χρησιμοποιήθηκε ήταν ο ακόλουθος:

%elegxos an to cond(A) einai iso me to c me vasi tis proipotheseis pou

%etethisan apo tin ekfonisi tis askisis

%o elegxos ginetai gia ta codition pou xrisimopoioume paakato stin ipoloipi

%askisi kathos kai gia to analogo n

n=10;

c=[10;1e2;1e5;1e8];

%arxikopoiisi tou s1 me vasi tin protropi tis askisis

s1=1;

for i=1:1:4

sn=s1/c(i);

%arxikopoiisi pinaka diastasewn (n-2)x1 me ta stoixeia tou na

%kimenontai apo to sn os to s1

d=sn+(s1-sn).*rand(n-2,1);

D=diag([s1,d',sn]);

[U,R]=qr(rand(n));

[V,R]=qr(rand(n));

A=U*D*V';

ConditionOfM=cond(A)

End

merosB_elegxos_condition.m

Και πράγματι τα αποτελέσματα που λάβαμε για το condition ήταν οι τιμές που είχαμε δώσει στο c όπως φαίνεται και στο παρακάτω screenshot:

merosB_elegxos_condition.jpg

Για το επόμενο ζητούμενο της άσκησης, δηλαδή την εύρεση του εμπρός σχετικού σφάλματος καθώς επίσης και του άνω φράγματος για την επίλυση του συστήματος Αx=b για Α τα οποία καθορίζονται από την εκφώνηση, ο κώδικας μας φαίνεται παρακάτω:

%meros B--to 2 stin ousia ipoerotima

%arxikopoiisi pinakon stous opoious filassontai ta apotelesmata gia to piso

%kai to empros sfalma kathos kai to ano fragma gia ta mitroa M kai G

%antistoixa

piso_sfalma_M=zeros(4,1);

ano_fragma_M=zeros(4,1);

empros_sfalma_M=zeros(4,1);

piso_sfalma_G=zeros(2,1);

ano_fragma_G=zeros(2,1);

empros_sfalma_G=zeros(2,1);

%dimiourgia pinaka e nx1 pou periexei monades os stoixeia

e=ones(n,1);

%arxikopoiisi n me vasi tin ekfonisi kathos kai dimiourgia pinaka c pou

%periexei ola ta c pou ha xrisimopoiithoun stin ektelesi

n=10;

c=[10;1e2;1e5;1e8];

%arxikopoiisi s1 me vasi tin protropi tis askisis

s1=1;

%arxikopoiisi metriti j

j=1;

for i=1:1:4

%arxikopoiisi sn oste na isxiei oti c=s1/sn

sn=s1/c(i);

%arxikopoiisi pinaka diastasewn (n-2)x1 me ta stoixeia tou na

%kimenontai apo to sn os to s1

d=sn+(s1-sn).*rand(n-2,1);

D=diag([s1,d',sn]);

[U,R]=qr(rand(n));

[V,R]=qr(rand(n));

A=U*D*V';

b=A*e;

%euresi tou eponomazomenou stin ekfonisi x^

x=A\b;

%ipologismos piso kai empros sfalmato kathos kai no fragmatos gia ton

%pinaka M(n,c) tis ekfonisis

piso_sfalma_M(i)=norm(b-A*x,2)/(norm(A,2)*norm(x,2)+norm(b,2));

empros_sfalma_M(i)=norm(e-x)/norm(e);

ano_fragma_M(i)=2*cond(A)*piso_sfalma_M(i);

if((c(i)==10)|(c(i)==1e5))

%dimiourgia tou pinaka G

G=gfpp(triu(A(1:n-1,1:n-1)));

b=G*e;

A=G;

%euresi tou eponomazomenou stin ekfonisi x^

x=A\b;

%ipologismos piso kai empros sfalmato kathos kai no fragmatos gia ton

%pinaka G tis ekfonisis

piso_sfalma_G(j)=norm(b-A*x,2)/(norm(A,2)*norm(x,2)+norm(b,2));

empros_sfalma_G(j)=norm(e-x)/norm(e);

ano_fragma_G(j)=2*cond(A)*piso_sfalma_G(j);

j=j+1;

end

end

%ektiposi empros sfalmatos kai ano_fragmatos gia ton kathe M(n,c) kai ton kathe G

empros_sfalma_M

ano_fragma_M

empros_sfalma_G

ano_fragma_G

merosB.m

Τα αποτελέσματα που λάβαμε φείνονται στον παρακάτω πίνακα:

	Εμπρός σφάλμα (x 1.0e-010)	Άνω φράγμα (x 1.0e-009)
M(10,10)	0.000	0.00
M(10,1e2)	0.000	0.00
M(10,1e5)	0.027	0.01
M(10,1e8)	8.380	11.14
G για c=10	0.0003	0.0004
G για c=1e5	0.2086	0.1421

merosB.txt

Μέρος Γ

Στο σημείο αυτό της άσκησης έχουμε σαν σκοπό την εύρεση των Mflop/s για την επίλυση του συστήματος Αx=b με μονη και διπλή ακρίβεια, χρησιμοποιώτας τυχαία πυκνά μητρώα μεγεθών 1000:200:2000 και ακολούθως να τα συγκρίνουμε.

Ο κώδικας που χρησιμοποιήθηκε για τον υπολογισμό των Mflop/s είναι αυτός:

%merosC euresi Mflop/s

%arxikopoiisi sto 0 pinaka ston opoio tha apothikeutoun ta ipologismena

%Mflop/s

mflops=zeros(6,2);

%arxikopoiisi metriti j

j=1;

for i=1000:200:2000

%dimiourgia tixaion mitroon diastaseon ixi kai ix1 antistoixa

A=rand(i);

b=rand(i,1);

%ektelesi arxika mias foras tis prakseis x=A\b prin ksekinisoume tin

%xronmetrisi kathos i proti ektelesi mporei na dosi paraplanitika

%apotelesmata gia ton xrono kai etsi den tin simperilamvanoume sto meso

%oro

x=A\b;

%euresi mesou xronou ektelesis tis prakseis x=A\b se arithmitiki

%diplis akriveias

tic;

for k=1:1:20

x=A\b;

end

dipli_akriveia=toc/20;

%arxikopoiisi mitroon C kai d monis akriveias

C=single(A);

d=single(b);

%ektelesi mias foras tis prakseis x=C\d gia ton idio opos kai

%proigoumenos logo

x=C\d;

%euresi mesou xronou ektelesis tis prakseis x=C\d se arithmitiki

%monis akriveias

tic;

for k=1:1:20

x=single(C\d);

end

moni_akriveia=toc/20;

%ipologismos ton Mflop/s

mflops(j,1)=((2/3)*i^3+2*i^2)/dipli_akriveia;

mflops(j,2)=((2/3)*i^3+2*i^2)/moni_akriveia;

j=j+1;

end

x=[1000;1200;1400;1600;1800;2000];

%ektiposi grafikis parastasis me stoixeia tin ekseliksi ton Mflop/s

%gia prakseis diplis kai monis akriveias apo mitroa diastasis

%1000 x 1000 se mitroa 2000 x 2000

plot(x, mflops(:,1), '.-');

% kanoume hold gia na emfanistoun se koini grafiki parastasi

hold on;

plot(x, mflops(:,2), 'g.-');

legend('dipli akriveia', 'moni akriveia')

hold;

MerosC_1.m

Η γραφική παράσταση που λάβαμε σαν αποτέλεσμα ήταν η εξής:

merosC_1.fig

Όπως ήταν αναμενόμενο άλλωστε η αναπαράσταση μονής ακρίβειας εκτελεί πολύ περρισότερες πράξεις το δευτερόλεπτο σε σχέση με την αναπαράσταση διπλής ακρίβειας και αυτό λόγο της μικρότερης πολυπλοκότητας των πράξεων αφου επεξεργάζονται μικρότερης ακρίβειας δεδομένα. Εύκολα διαπυστώνουμε από την γραφική παράσταση ότι όταν μεγαλώνει και το μέγεθος των μητρώων με τα οποία ασχολούμαστε τοσο μεγαλώνουν, ελαφρώς βέβαια και οι αντίστοιχες τιμές των Mflop/s.

Τώρα σαν στόχο έχουμε να υλοποιήσουμε κώδικα στον οποίο να παρατηρούμε τις διαφορές στους χρόνους επίλυσης του συστήματος Ax=b, με αλγόριθμο επαναλυπτικής εκλέπτυνσης σε μονή ακρίβεια και με την κλασσική υλοποίηση, δηλαδή x=A^(-1)*b, καθώς επίσης και τις μεταξύ διαφορές των αποτελεσμάτων (των x δηλαδή) με είσοδο διάφορων διαστάσεων τυχαία μητρώα.

Ο κώδικας που υλοποιήσαμε φαίνεται παρκάτω:

%meros C -- ipoerotima 2

%arxikopoiisi pinakon pou apothikeuoun ta apotelesmata gia to poses fores

%einai taxiteri i epanalitiki ekleptinsi apo to mtimes, tis diastaseis ton

%pinakon pou xrisimopoioume, tin maximum diafora gia ton x pou

%ipologizontai me tis dio diaforetikes methodoud, tin minimum, ton meso

%xrono tis epanaliptikis ekleptinsisgia kathe diastasi kai ton meso xrono

%tis mtimes antistoixa

poses_fores_taxtiteros=zeros(10,1);

diastaseis=zeros(10,1);

maximum=zeros(10,1);

minimum=zeros(10,1);

epanaliptiki_ekleptinsi=zeros(10,1);

mtimes=zeros(10,1);

%arxikopoiisi metriti j

j=0;

for n=100:100:1000

j=j+1;

%dimiourgia tixaion mitroon A,b

A=rand(n);

b=rand(n,1);

tic;

for i=1:1:20

%Algorithmos epanaliptikis ekleptinsis

%diaspasi tou A se mitroa L, U kai P

[L,U,P]=lu(A);

%euresi ton L, U kai P se moni akriveia

U_single=single(U);

L_single=single(L);

P_single=single(P);

%ipologismos tou x se moni akriveia

x=single(U_single\(L_single\(P_single*single(b))));

k=1;

while(k==1||norm(z)<=eps('single')*norm(x))

r=b-A*x;

z=single(U_single\(L_single\(P_single*single(r))));

x=x+z;

k=k+1;

end

end

%apothikeusi mesou xronou ipologismou tou x me tin methodo tis

%epanaliptikis ekleptinsis

epanaliptiki_ekleptinsi(j)=toc/20;

%ipologismos tou x me ton klassiko pollaplasiasmo tis Matlab, edo to x

%to onomazo y

tic;

for i=1:1:20

y=inv(A)*b;

end

%apothikeusi mesou xronou ipologismou tou x me tin methodo tis mtimes

mtimes(j)=toc/20;

%ipologismos diaforas metaksi ton apotelesmaton ton dio methodon

diafora_metaksi_ton_2_x=y-x;

%ipologismos tis apolitis timis ton diaforon

l=abs(diafora_metaksi_ton_2_x);

%ipologismos maximum fiaforas

maximum(j)=max(l);

%ipologismos minimum diaforas

minimum(j)=min(l);

%topothetisi ton diastaseon ston pinaka me tis diastaseis

diastaseis(j)=n;

%ipologismos tou pilikou mtimes/epanaliptiki_ekleptinsi, oste na

%diapistosoume poses fores einai taxiteros o algorithmos epanaliptikis

%ekleptinsis apo tin euresi tou x me tin mtimes

poses_fores_taxtiteros(j)=mtimes(j)/epanaliptiki_ekleptinsi(j);

end

plot(diastaseis,poses_fores_taxtiteros,'.-')

legend('poses fores taxiteros o Algorithmos Epanaliptikis Ekleptinsis apo afto tis Mtimes')

epanaliptiki_ekleptinsi

mtimes

maximum

minimum

poses_fores_taxtiteros

merosC_2.m

Στο παρακάτω σχήμα φαίνεται η γραφική παράσταση του πηλικου του μέσου χρόνου εκτέλεσης της επίλυσης του συστήματος με την κλασσική υλοποιηση προς αυτόν με τον αλγόριθμο επαναληπτικής εκλέπτυνσης:

merosC_2.fig

Όπως εύκολα μπορούμε να διαπυστώσουμε με μονή ακρίβεια η λύση επέρχεται πολύ πιο γρήγορα, αναμενόμενο άλλωστε λόγο της πολυπλοκότητας των υπολογισμών σε σχέση με την διπλή ακρίβεια. Επίσης όσο μεγαλύτερα τα μητρώα με τα οποία εχουμε να κάνουμε τόσο μεγαλύτερος είναι και ο λόγος των δύο χρόνων, αν και όσο τίνουμε προς πολυ μεγάλα μητρώα ο λόγος αυτός υποθέτουμε ότι συγκλίνει.

Συγκεκριμένα οι αντίστιχοι χρόνοι για την μέθοδο της επαναληπτικής εκλέπτυνσης και της mtimes,από τους οποίους προκύπτει ο παραπάνω λόγος, φαίνονται στον παρακάτω πίνακα:

ΔΙΑΣΤΑΣΕΙΣ Α	ΧΡΟΝΟΣ ΓΙΑ ΕΠΑΝΑΛΗΠΤΙΚΗΣ ΕΚΛΕΠΤΥΝΣΗΣ	ΧΡΟΝΟΣ ΓΙΑ MTIMES
100x100	0.0022	0.0028
200x200	0.0071	0.0148
300x300	0.0219	0.0490
400x400	0.0492	0.1119
500x500	0.0902	0.2141
600x600	0.1497	0.3687
700x700	0.2308	0.5779
800x800	0.3394	0.8613
900x900	0.4704	1.2119
1000x1000	0.6347	1.6544

merosC_2.txt

Τώρα βέβαια γεννάται η απορία για την απώλια ακριβειας της λύσης x, όταν οι υπολογισμοί γίνονται σε αριθμητική μονής ακρίβειας σε σχεση με αυτή της διπλής. Παρ’ όλα αυτα από τον παρακάτω πίνακα είναι ολοφάνερο οτι η μέγιστη διαφορά στα μεταξύ διπλής και μονής ακρίβειας αποτελέσματα, δηλαδή τα x, είναι αμελιτέα σε σχέση με τον χρόνο που γλιτώνουμε. Τώρα για την ελάχιστη διαφορά δεν αξίζει να γίνει λόγος αφου είναι υπερβολικά μικρή.

ΔΙΑΣΤΑΣΕΙΣ Α	MAXIMUM ΔΙΑΦΟΡΑ	MINIMUM ΔΙΑΦΟΡΑ (x1.0e-005)
100x100	0.0000	0.0059
200x200	0.0000	0.0039
300x300	0.0018	0.0166
400x400	0.0000	0.0008
500x500	0.0000	0.0002
600x600	0.0001	0.0011
700x700	0.0008	0.1037
800x800	0.0001	0.0050
900x900	0.0000	0.0010
1000x1000	0.0004	0.0011

merosC_2.txt

Η διαφορές αυτές είναι ανεξάρτητες από το μέγεθος του πίνακα που χρησιμοποιούμε σαν δεδομένο για την επίλυση των συστημάτων. Έπίσης είναι πολύ μικρές λόγω του ότι δεν λύθηκε απλά το σύστημα σε αριθμητική μονής ακρίβειας αλλά υλοποιήθηε ένας αλγοριθμος επαναληπτικής εκλέπτυνσης.