On 19 Sty, 07:15, Mariusz Marszałkowski <m...@g...com> wrote:
> On 19 Sty, 02:52, bartekltg <b...@g...com> wrote:
>
> > On 18 Sty, 20:26, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > > Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
>
> > Porownales wektor * macierz. Ja zastanawialem sie nad porownaniem
> > mnozenia 2 macierzy kwadratowych (i nieco wiekszych niz 1000).
>
> Nie wiem czy się skuszę (mam masę innych rzeczy do testowana) na
> taki test, ale może... Nie znam tego algorytmu który ma mniejszą
> złożoność niż N^3. Obecnie jakie jest dokładne teoretyczne
> ograniczenie?

Coppersmitha-Winograda daje n^2.376, ale stala jest tak duza,
za na razie komputery nie bawia sie takimi macierzami pelnymi.

Niby mozna uzywac algorytmu Strassena (n^log_2 7 = log^2.807),
ale ma on klopoty z numeryczna stabilnoscia. Blas uzywa n^3
(jeszcze do tego wroce).

> Może jakbym miał przystępnie opisany ten algorytm to bym napisał w
> gołym C.
> Zapodajcie linka do dobrego algorytmu, może spróbuję.

http://en.wikipedia.org/wiki/Strassen_algorithm
ale IHMO nie ma sensu n^3 starczy.

> > > Napisałem wydajniej to co opisałem: mnożenie macierzy o
> > > rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
> > > mieć specjalną implementację do takich macierzy.
>
> > A nie jest to wydajne? Masz czas tego samego rzedu co w jezyku
> > kompilowalnym (i to skompilowanem pod swoj system i procek!).
>
> Zależy jak oceniać. Słyszałem opinie z których wynikało że
> matlab to wszystko robi z 50 razy szybciej. W świetle tamtych

http://ubuntuforums.org/archive/index.php/t-1295370.
html
:)

> opinii wypadł śmiesznie, i głównie to chciałem sprawdzić. A
> czy jest 2 razy szybszy czy 2 razy wolniejszy to osobiście
> zgadzam się że nie powód do oceniania pakietu. Chciałem się
> tylko upewnić czy nie jest 50 razy lepszy :)

50 na dzien dobry brzmi smiesznie.
Ale nadal bede mowic, ze sprawdziles to dla
danych nieso spoza zakresu w ktorym matlab jest dobry.

> Przy jednym z moich projektów miesięczny rachunek za energię
> na komputery liczące to około 1000zł. Dużo nie brakuje aby
> starczyło na wypłatę dla nastepnego programisty...

Teraz polowe zaoszczedzisz.. Student na pol etatu na to pojdzie?

> Właśnie od różnych ludzi i z różnych środowisk, w
> końcu mnie sprowokowali.

Skoro sprowokowali, to zrob uczciwy test na duzych
maciezach a nie pitu-pitu wektorkami po 1000 elementow:)

> > Moze rzeczywiscie pisali mnozenie macierzy w javie;)
>
> Sadze ze w ogole nie pisali i w ogole nie porownywali czasow,
> tylko ulegli marketingowi matlaba.

:)


> Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
> ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
> procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
> M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
> wymnozylaby duzo szybciej niz ogolna.

Dla bardzo malych K mozna by sie bawic w rozwijanie petli.
Dla wiekszych - nie ma znaczenia przy algorytmie n^3.


> > Ja nadal uwazam, ze jesli pakiet numeryczny daje ten sam rzad
> > wielkosci, to jest przyzwoity wynik.
>
> Ja tez tak podejrzewam, ale teraz tez wiem ze nie ma
> implementacji 50 razy wydajniejszych.

Za to sa 50razy mniej wydajne;)

> > W miare mozliwosci (trzeba napisac) zrob to porownanie przy mnozeniu
> > dwuch macierzy 1000x1000. Roznica powinna sie znacznie zmniejszyc.
>
> Nie obiecuje, ale sprobuje, tylko zapodajcie dobry opis algorytmu,
> nigdy
> nie implementowalem lepszego algorytmu mnozenia macierzy.


> Może mieć algorytm o lepszej zlozonosci niż N^3 i
> jego moc się nie ujawnia gdy mnozymy macierze
> podobne do wierszowych.


Nie. Matlab, (mimo mojego natkniecia sie na informacje,
ze jednak) nie korzysta z szybszych algorytmow
(przynajmniej dla macierzy rzedu 1000-2000).

Dowod literaturowy. Matlab korzysta z BLASa jako
silnika do operacji na macierzach:
http://www.mathworks.com/access/helpdesk/help/techdo
c/ref/mtimes.html
[*]
Wiki gdzies wsponilala, ze BLAS uzywa dla duzych macierzy jakios
modyfikacji
Strassena, jadnak w kodzie tego nie widac:
http://www.netlib.org/blas/dgemm.f (macierz macierz).

Dowod statystyczny (12 macierzy o wielkosciach ciut ponizej 1000 do
ok2000):
wyn=[];for j=95:110; n=floor(2^(j/10)); a=rand(n); b=rand(n);
tic;a*b;wyn=[wyn;n,toc], end;
plot(log(wyn(:,1)),log(wyn(:,2)),'*' ) %poogladajmy sobie
[s,serr]=lscov([x,ones(size(x))],y)

Czas algorytmu to n^k hdzie k= 2.99 +- 0.06

Wiec n^3. Przynajmniej nie bede sie bac o stabilnosc numeryczna.

Jednak polecam napisanie tego n^3 i porownaine z matlabem.
Moze ci 'z roznych srodowisk' nie mylili sie tak bardzo
i kombajn bedize szybszy od napredce zmajstrowanego
programiku (pomijajac wspolczynnik 50 wziety z sufitu;)

pozdrawiam
bartekltg

[*] z tego linku wynika tez, ze jednak uzywa dgemv, czyli
specjalizowanej procedury macierz-wektor.

Czyzby 1000 bylo nadl tam mala liczba.
Moze porwnajmy monzenie M_kxn * wektor_n
gdzie n rzedu 10^6 a k rzedu kilkadziesiat.