Drugie życie metody Jacobiego?

[KopalniaWiedzy.pl 357]

Opracowana w XIX wieku metoda Jacobiego może powrócić do łask. Wszytko, dzięki uporowi jednego studenta i wierze jego profesora.

W 1845 roku niemiecki matematyk Carl Gustav Jacob Jacobi opracował metodę iteracyjnego rozwiązywania układu n równań z n niewiadomymi. Rozwiązywanie takich równań tradycyjną metodą pochłania bardzo dużo czasu, dlatego też tam, gdzie nie potrzebujemy dokładnego wyniku, a jedynie dobrego przybliżenia, możemy posłużyć się metodami iteracyjnymi. Metoda Jacobiego była często wykorzystywana w epoce przed rozwojem superkomputerów. Jednak obecnie istnieją lepsze i szybsze sposoby obliczeń, dlatego metodę Jacobiego zarzucono.

Jednak pewien student z Uniwersytetu Johnsa Hopkinsa tchnął w nią nowe życie i przyspieszył jej działanie aż 200-krotnie.

Jesienią 2012 roku profesor Rajat Mittal prowadził zajęcia z metod numerycznych. Omówił na nich metodę Jacobiego, którą opisał jako elegancką, ale obecnie bezużyteczną i skupił się w dalszej części zajęć na nowocześniejszych, szybszych metodach. Wśród słuchaczy Mittala był student pierwszego roku Xiang Yang. Zainteresował się metodą Jacobiego, przyjrzał się jej bliżej, a po jakimś czasie spotkał się z Mittalem i zarysował swój pomysł na jej przyspieszenie. Zamiast powiedzieć mi, że metoda liczy sobie 169 lat i każdy bez powodzenia próbował ją udoskonalić, profesor Mittal odrzekł, iż mój pomysł brzmi obiecująco i zachęcał mnie do dalszej pracy nad nim - mówi Yang.

Student przez kilka tygodni pracował pod kierunkiem Mittala nad metodą. Później wspólnie napisali artykuł, który mógłby zostać opublikowany w recenzowanym czasopiśmie. Właśnie ukazał się on w online'owej wersji Journal of Computational Physics. Profesor Mittal wierzy, że dzięki temu ulepszona przez Yanga metoda Jacobiego spotka się z zainteresowaniem i zostanie zastosowana w praktyce. Myślę, że bardzo szybko ją zaadaptują. Każdemu zależy na czasie, a nowa metoda Jacobiego pozwala zaoszczędzić czas. Jej piękno polega na tym, że jest świetnie dostosowana do współczesnego przetwarzania równoległego, które jest wykorzystywane podczas większości symulacji. Zdaniem uczonego na pracy Yanga skorzystają szczególnie ci eksperci, którzy zajmują się mechaniką płynów.

Co ciekawe, praca nad metodą Jacobiego jest dla Yanga zajęciem pobocznym. Młody naukowiec pisze pracę doktorską, w której bada, w jaki sposób skorupiaki przyczepione do kadłuba statku wpływają na jego poruszanie się w wodzie.

« powrót do artykułu

[Jarek Duda 139]

Link do pracy: http://engineering.jhu.edu/fsag/wp-content/uploads/sites/23/2013/10/JCP_revised_WebPost.pdf

Ciekawe, twierdzą ponad 100 krotne przyśpieszenie ...

 

Dobra nauczka żeby automatycznie nie uznawać nawet podstawowych domyślnie używanych algorytmów jako już tych najlepszych. Np. postawą kompresji danych jest koder entropii: szybkie ale dające gorszą kompresję kodowanie Huffmana, albo dobre ale strasznie wolne kodowanie arytmetyczne ... a tu kilka miesięcy temu pojawiły się dobre i nawet szybsze od Huffmana kodery oparte na nowym podejściu (np. FSE, rANS), dając to co kodowanie arytmetyczne tylko np. 8x szybciej: http://encode.ru/threads/1920-In-memory-open-source-benchmark-of-entropy-coders

[thikim 119]

Nie zawsze coś na pierwszy rzut oka najszybsze jest najszybsze.

Dawniej nawet była taka reguła (dziś już chyba nie obowiązuje): dłuższy kod = szybsze wykonanie.

Ale mniejsza o to. Jest taka zagadka:

Czterech podróżnych chce przejść przez dziurawy most nocą, mając tylko jedną latarką. Boją się przechodzić bez latarki, a most jest na tyle słaby, że równocześnie mogą się na nim znajdować tylko dwie osoby. Na przejście mostu pierwszy podróżnik potrzebuje 1 minuty, drugi 2 minuty, trzeciemu zajmuje to 5 minut, a czwartemu aż 10. Kiedy idą w parze szybszy dostosowuje prędkość do wolniejszego.

Najszybsze rozwiązanie nie jest tym które ludzie wybierają.

[radar 104]

Z tym, że nie napisałeś, że chodzi o to, żeby przejść jak najszybciej, o to co ludzie najczęściej wybierają, ani jaki jest prawidłowy wynik

Mi, licząc na oko wyszło 19 minut, ale dlaczego ktoś miałby wybierać inaczej?

[pogo 102]

Mam rozwiązanie na 17 minut

I sam widzisz, że pewnie Twoje jest tym najczęściej wybieranym, a moje (prawdopodobnie) najszybszym.

[radar 104]

Tak się skupiłeeeem i... nic nie wymyśliłem Jakie jest rozwiązanie na 17?

[Afordancja 57]

Mam rozwiązanie na 17 minut I sam widzisz, że pewnie Twoje jest tym najczęściej wybieranym, a moje (prawdopodobnie) najszybszym.

 

Zanim zacznę myśleć nad tym, to się upewnię, oczywiście doliczyłeś powroty(2 powroty) ? bo 19 minut przychodzi każdemu od strzału.

 

[edit]

Faktycznie 17minut

 

 

 

1 z 2 (2)

wraca 1 (1)

5 z 10 (10)

wraca 2 (2)

1 z 2 (2)

razem (17)

 

 

[radar 104]

HAHAHA, co za matoł, zapomniałem, że wraca 2:) Zagadka stara jak świat tyle, że z owcami i psem chyba.