KopalniaWiedzy.pl 292 Posted June 30, 2014 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 Share this post Link to post Share on other sites
Jarek Duda 124 Posted July 1, 2014 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 Share this post Link to post Share on other sites
thikim 117 Posted July 1, 2014 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ą. Share this post Link to post Share on other sites
radar 95 Posted July 2, 2014 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? Share this post Link to post Share on other sites
pogo 102 Posted July 2, 2014 Mam rozwiązanie na 17 minut I sam widzisz, że pewnie Twoje jest tym najczęściej wybieranym, a moje (prawdopodobnie) najszybszym. Share this post Link to post Share on other sites
radar 95 Posted July 2, 2014 Tak się skupiłeeeem i... nic nie wymyśliłem Jakie jest rozwiązanie na 17? Share this post Link to post Share on other sites
Afordancja 57 Posted July 2, 2014 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) Share this post Link to post Share on other sites
radar 95 Posted July 2, 2014 HAHAHA, co za matoł, zapomniałem, że wraca 2:) Zagadka stara jak świat tyle, że z owcami i psem chyba. Share this post Link to post Share on other sites
