Išče se hiter algoritem za izračun ene čudne matrične operacije.

Definirano imamo operacijo na kvadratnih matrikah velikosti n*n:


C = A * B

c(i,j) = min{ a(i,k) + b(k,j) }, kjer k teče od 1 do n.


Časnovna zahtevnost algoritma za izračun tega je O(n^3).

Zahtevnost običajnega matričnega množenja takisto O(n^3), vendar se ga da s Strassenovo metodo izboljšati na O(n^2.8).

A ma mogoče kdo kakšno idejo če bi se dalo kako izboljšati tudi zahtevnost zgoraj napisane operacije??

A je možna še kakšna dodatna izboljšava, če sta matriki A in B enaki (C = A * A)?

A daj no, malo se sam potrudi, ne pa da ti drugi rešujejo seminarsko.

Za začetek vzamemo naivni algoritem. O(n^4).

Za vsak par elementov iz A in B matrike preveri, če imata eden isto x, kot drugi y koordinato. Če ja, potem ju seštejemo. Če je vsota manjša od elementa na koordinatah x,y - ga nadomestimo s to vsoto.

Uporabimo pa Cjevsko notacijo, kjer je matrika interpretirana iz enodimenzionalnega niza.

int TAB[1000];int i=0;int j=0;int k=0;int l=0;int m=0;int n=0;int o=0;int p=0;int q=0;int r=0;int s=0;int x=0;
q=3;
p=9;
//C
//F TAB[26]
//R TAB
i=0;
while (i < q) {

j=0;
while (j < q) {

x=i*q;
x=x+j;
x=x+p;
x=x+p;
o=255;
TAB[x]=o;
k=0;
while (k < q) {

l=0;
while (l < q) {

if (k==l) {

o=i*q;
o=o+l;
x=k*q;
x=x+p;
x=x+j;
m=TAB[o];
n=TAB[x];
m=m+n;
o=i*q;
o=o+j;
o=o+p;
o=o+p;
r=TAB[o];
if (m < r) {

TAB[o]=m;

}

}
l++;

}
k++;

}
j++;

}
i++;

}

Potem dame zadevo v Critical ver. 1.0 beta in čakamo kaj bo ...

Kakršna koda bo že prišla ven - postana bo sem.

Ampak strassen prispara pri mnozenjih in jih nadoknadi z precej vec sestevanji... pa je zato hitrejs... mislim da iz 8 mnozenj pride na 7, ampak dobi 16 sestevanj.

V tem primeru pa sploh ni nobenega mnozenja...

Naj napisem do konca od tele seminarske... izracunati je treba A^(n-1) teh operacij torej n matrik A zracunat po tej operaciji.

Kako vam gre kej hitrost? jest sm spravu 1000x1000 matriko na 48.5s na P4, na isto po oznakah hitrem athlonu pa tocno 1x pocasneje.. zanimivo :)

lp
PEter.

Meni je zaenkrat uspelo 1000x1000 matriko spraviti na 20 do 30 sekund (odvisno kakšni so elementi matrike) na Duronu 1300.
Treba je še upoštevati da linux laufam na windowsih pod vmwarom in je zato malo počasneje.

Običajen algoritem pa mi stvar naredi v približno 600 sekundah . Ne glede na matriko.

Ciki: a 20-30 sekund ti traja ta operacija al N takih operacij pri matriki 1000x1000?

Thomas: am, ti mas samo eno tabelo... in si prepises vrednosti, ki jih mors uporablat... lej:
|1 2|
A =|3 4|

C=A*A

|1 2| |1 2| |2 3|
|3 4| * |3 4| = |4 5|

drugo matriko dobis takole:
C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((1+2),(2+4)) = 3;
C[1,0] = min((3+1),(4+3)) = 4;
C[1,1] = min((3+2),(4+4)) = 5;

Ti pa pises v ISTO matriko, in ti ze na drugem koraku zajebes, ker:

C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((2+2),(2+4)) = 4;

Sicer mozn da ti indexi ne tecejo glih tko, ker si mal drugac naredu zanke, sam prej al slej se prepises... v vsakem primeru moras rezultat pisat v drugo matriko...

lp
PEter.

20-30 sekund cela seminarska (A*A....*A - n-krat)

2500x2500 pa 180 sekund.

Fora je, da ugotavljamo minimalen element, zato ni treba pregledati vse elemente kot pri običanjem matričnem množenju. Če si malce pomagamo s sortiranjem vrstic, lahko z iskanjem najmanjšega nehamo še predem pridemo do konca, samo pravilne pogoje je treba postaviti...

Tistemu izrazu A*A*A*A..*A pa se da zaradi asociativnosti opracije časovno zahtevnost z O(n) zmanjšati na O(logn)

Smo dal zdejle algoritem mau optimizirat (šele).

Bom ga zjutrej tle sem napisal, če bo sreča z elektriko in ostalim.