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?
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ę.

> > 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
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 :)

> Chcesz z maksymalna moca swojego komputera robic ceizkie
> obliczenia gdzie te 30% jest istotne.. chyba bedzie trzeba
> zatrudnic programiste. Albo doktoranta:)

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...

> A skad te glosy ze jest super wydajne? Moze od ludzi,
> ktorzy robili to w Ja.. jakims podejrzanym jezyku skryptowym
> bez uzycia bilioteki. Albo od ludzi, ktorym mnozenie macierzy
> pisal ow doktorant:)
Właśnie od różnych ludzi i z różnych środowisk, w
końcu mnie sprowokowali.

> BTW, rozumeim, ze pusciels oba parokrotnie i porownales
> najlepszy z najlepszym.
Tak. Właściwie mój brat jeszcze zaczął kompilować projekt w
gcc z różnymi opcjami aby jeszcze przyspieszyć, ale już
nic nie pomagało.

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

> A jestes pewien, ze niewielkim nakladem pracy zbudujesz dobry
> algorytm numeryczny. Wydajne PCG dla macierzy rzadkich,
> roznego rodzaju rozklady, czy uniwersalna szukaczke minimow.
Niewielkim to niemozliwe, no chyba ze znam algorytm i juz
kiedys go implementowalem.

> Podejrzewam, ze trzeba mu kazac (byc moze sa to osobne funkcje).
> I miec wersje (toolboxa?) pozwalajaca na to.
Nie wiem, mozliwe.

> > > Skontaktuj sie z nimi i zapytaj o podiane bibliotek na superprocek.
>
> > Nie chce mi sie, pokazalem ze na najprostszym przykladzie radzi
> > sobie gorzej, wiec dlaczego mam dawac waire ze na zaawansowanych
> > procedurach radzi sobie lepiej?
>
> Szczerze mowiac, wybrales zagadneinie nad ktorym srednio sie
> pochylali. Patrz koniec postu.
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.

> A bardziej zaawansowane algorytmy to cos wiecej niz dwie/trzy petle.
> Jak chesz naprawde porownac matlaba i swoj kod, zrob to
> na czyms powazniejszym, LUP (wbudowana), znajdowanie
> wektortow wlasnych (wbudowana, cholski i QZ) albo PCG (skrypt).
> Pewnie da sie napisac w c szybiej (trzecia na pewno;))
> zwlaszcza na konkretny procek, ale wymagac bedzie juz odrobiny
> wysilku.
Zgadza sie, nigdy temu nie zaprzeczalem.

> 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.

> 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.

>
> Przy okazji:
>
> Zrobilem tez prosty test. Macierz 1000x1000 mnoze przez
> 256 wektorow, ale na rozne sposoby. Mnoze 2^j razy paczki
> po 256/2^j wektorow.
>
> a=rand(1000);
> t=[];
> for j=8:-1:2,
>     v=rand(2^(8-j),1000);
>     tic;
>     for k=1:2^j,
>                         v*a;
>     end;
>     t=[t;toc];
> end;
>
> Wyniki:
>
> petli   wektorow w pakiecie     czas
> 256         1       3.6121
> 128         2       2.2496
> 64           4       1.3139
> 32           8       0.80334
> 16          16      0.65687
> 8            32      0.53299
> 4            64      0.5166
>
> Za kazdym razem mnozylismy tyle samo wektorow.
> Sredni czas na wektor dosc mocno spadal, jesli robilismy
> to na raz. Przyszpieszylismy szesciokrotnie!
> Teraz zaczynam sie dziwic, dlaczego Twoj program
> byl tylko niecale dwa raza szybszy (jemu wszytko jedno
> czy mnozymy po koleji, czy hurtem).

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

Pozdrawiam serdecznie