Drugie życie metody Jacobiego?
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.
Komentarze (7)
Jarek Duda, 1 lipca 2014, 08:02
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, 1 lipca 2014, 20:16
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:
Najszybsze rozwiązanie nie jest tym które ludzie wybierają.
radar, 2 lipca 2014, 09:56
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, 2 lipca 2014, 10:20
Mam rozwiązanie na 17 minut
I sam widzisz, że pewnie Twoje jest tym najczęściej wybieranym, a moje (prawdopodobnie) najszybszym.
radar, 2 lipca 2014, 11:55
Tak się skupiłeeeem i... nic nie wymyśliłem Jakie jest rozwiązanie na 17?
Afordancja, 2 lipca 2014, 12:26
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, 2 lipca 2014, 13:36
HAHAHA, co za matoł, zapomniałem, że wraca 2:) Zagadka stara jak świat tyle, że z owcami i psem chyba.