Agnieszka Borkowska
--------------------------------------------------------
Octave, version 2.0.16

Test zostal przeprowadzony na Pentium II, 350 MHz,
64 MB RAM.

Czas dzialania byl mierzony za pomoca funkcji clock
i etime.
--------------------------------------------------------
Algorytm:

Macierz A:
 -----------------------------------------
| A1,1 | A1,2 |   . . .   | A1,K | A1,K+1 |
|      |      |           |      |        |
 ------ ------ ----------- ------ --------
|  .      .                  .       .    |
|  .      .                  .       .    |
|  .      .                  .       .    |
 ------ ------ ----------- ------ --------
| AK,1 | AK,2 |   . . .   | AK,K | AK,K+1 |
|      |      |           |      |        |
 ------ ------ ----------- ------ --------
|AK+1,1|AK+1,2|   . . .   |AK+1,K|AK+1,K+1|
|      |      |           |      |        |
 -----------------------------------------

gdzie Ai,j - MxM
gdy R>0: Ai,K+1 - MxR
         AK+1,j - RxM
         AK+1,K+1 - RxR (i,j=1,...,K)
gdzie R:=N mod K
      M:=N div K

Podobnie przedstawiam macierz B i stosuje wzor:

gdy R=0
Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j

gdy R>0
Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j+Ai,K+1*BK+1,j

Listing funkcji:
--------------------------------------------------------

function D = Mnozenie(A,B,C,K)
N = size(A,1);
M = floor(N/K);
R = rem(N,K);
L = K*M;

% Di,j=Ci,j+Ai,1*B1,j+...+Ai,K*BK,j
i = 0;
while (i < L)
j = 0;
while (j < L)
TEMP = C(i+1:i+M,j+1:j+M);
k = 0;
while (k < L)
TEMP = TEMP + A(i+1:i+M,k+1:k+M)*B(k+1:k+M,j+1:j+M);
k = k + M;
endwhile
D(i+1:i+M,j+1:j+M) = TEMP;
j = j + M;
endwhile
i = i + M;
endwhile

% Przemnozenie prostokatow powstalych gdy K nie dzieli N
if (R>0)

% Di,j=Di,j+Ai,K+1*BK+1,j
i = 0;
while (i < L)
j = 0;
while (j < L)
D(i+1:i+M,j+1:j+M) = D(i+1:i+M,j+1:j+M) + A(i+1:i+M,L+1:N)*B(L+1:N,j+1:j+M);
j = j + M;
endwhile
i = i + M;
endwhile

% Di,K+1=Ci,K+1+Ai,1*B1,K+1+...+Ai,K+1*BK+1,K+1
i = 0;
while (i < L)
TEMP = C(i+1:i+M,L+1:N);
k = 0;
while (k < L)
TEMP = TEMP + A(i+1:i+M,k+1:k+M)*B(k+1:k+M,L+1:N);
k = k + M;
endwhile
TEMP = TEMP + A(i+1:i+M,L+1:N)*B(L+1:N,L+1:N);
D(i+1:i+M,L+1:N) = TEMP;
i = i + M;
endwhile

% DK+1,j=CK+1,j+AK+1,1*B1,j+...+AK+1,K+1*BK+1,j
j = 0;
while (j < L)
TEMP = C(L+1:N,j+1:j+M);
k = 0;
while (k < L)
TEMP = TEMP + A(L+1:N,k+1:k+M)*B(k+1:k+M,j+1:j+M);
k = k + M;
endwhile
TEMP = TEMP + A(L+1:N,L+1:N)*B(L+1:N,j+1:j+M);
D(L+1:N,j+1:j+M) = TEMP;
j = j + M;
endwhile
k = 0;
TEMP = C(L+1:N,L+1:N);
while (k < L)
TEMP = TEMP + A(L+1:N,k+1:k+M)*B(k+1:k+M,L+1:N);
k = k + M;
endwhile
TEMP = TEMP + A(L+1:N,L+1:N)*B(L+1:N,L+1:N);
D(L+1:N,L+1:N) = TEMP;

endif

endfunction

--------------------------------------------------------
Tabelka wynikow:

 N   |   T1    |   T2    | K opt | P
----------------------------------------
100  |  0.0306 |  0.0345 | 1     | 0.89
200  |  0.2260 |  0.2369 | 1     | 0.95
400  |  3.9356 |  2.0761 | 2     | 1.89
800  | 31.3730 | 16.4130 | 5     | 1.91
1000 | 61.4290 | 32.1360 | 8     | 1.91

Opis tabelki:
T1 - czas (sek.) dzialania operacji C = C + A * B
T2 - czas (sek.) dzialania funkcji Mnozenie przy optymalnym K
P - przyspieszenie, P = T1/T2

Wnioski:
Macierze, dla ktorych N jest duze (N > 500), lepiej jest podzielic
na mniejsze podmacierze i je mnozyc, oczywiscie kosztem wiekszej
liczby dzialan na macierzach.
Dlatego, jezeli K jest za duze, moze to znacznie wydluzyc dzialanie
algorytmu (np. dla N=1000 i K=100 czas mnozenia wynosi ok. 9 min.).