On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
> 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/techdoc/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;)

Zgoda, jesli zapewniles mnie ze matlab uzywa tego algorytmu
n^3 to sprawdze na macierzach o roznych rozmiarach. Wkrotce
podam czasy wykonania.

A co do 50 razy to wrecz zaczynalem czuc presje, ze
powinienem uzyc matlaba. To chyba znak ze matlab
naprawde niezle jest rozreklamowany.

Pozdrawiam