Test konvergence na kruhu
Obsah

Nasledujicich testy byly provedeny za ucelem overeni, ze metoda konverguje k presnemu reseni pri zjemnovani kroku (jak prostoroveho, tak casoveho). Podminky pokusu zustaly temer stejne jako v testu paralelizace:

Stred kruznice = [ 2.0, 2.0 ]
Polomer = 1.35

Velikost oblasti pri mrizce procesu  = [ 0.0 - 4.0, 0.0 - 4.0 ]
Pocatecni cas = 0.0
Koncovy cas = 0.9
Epsilon^2 = 1e-10

Nasledujici tabulky zachycuje zakladni vysledky pokusu, kdy chyba je merena jako prumerna | X^2-Y^2-R^2 |, kde souradnice jsou samozrejme posunuty do stredu kruznice a R udava analyticky spocitany polomer. Merena je v case 0.9. Doba vypoctu vzdalenosti udava cas straveny pri inicializaci vzdalenosti, synchronizace ukazuje cas straveny synchronizaci pri kazde iteraci (nutno podotknout, ze vsechny porcesy bezely na jednom pocitaci a tudiz se data neposilala pres zadny pomaly kanal jako sit a protokol TCP/IP). Bohuzel jsem vybral casovy krok az prilis velky, coz melo za nasledek nestabilitu vypoctu pro krok 0.02. A proto jsem provedl druhou sadu testu na jemnejsim casovem kroku.

Sada 1
<konverg1>
Prostorovy krok (bodu mrizky)
 0.03 (133^2)
 		0.02 (200^2)
 		0.015 (267^2)
 		0.01 (400^2)
 		0.0075 (533^2)
Casovy krok
 4e-4
 1.9e-4
 1e-4
 4.4e-5
 2.5e-5
Chyba
 2.9e-4
 <nestab>
 6.4e-5
 5.3e-5
 2.3e-5*
Chyba haus
 1.7e-3
 <nestab>
 4.8e-4
 2.6e-4
 2.9e-5**
Doba vypoctu vzdalenosti (s)
 1
 3
 17
 64
 130
Doba synchronizace (s)
 0.01
 0.02
 0.04
 0.09
 0.15
Doba vypoctu (s)
 38
 183
 648
 2934
 8885
* Aproximovano z hladiny 0.72 pomerem chyb na hladinach z nasledujici tabulky
** Na hladine 0.72

Sada 2
<konverg2>
Prostorovy krok
0.03
0.025
0.02
0.015
 		0.01
0.0075*
0.005
Casovy krok
 1e-4
 6.9e-5
 4.4e-5
 2.5e-5
 1.1e-5
 6.3e-6
 		2.7e-6
Chyba
 1.4e-4
 1.0e-4
 5.0e-5
 3.4e-5
 3.4e-5
 1.9e-5
 		1.1e-5
Chyba haus
 1.6e-3
 9.2e-4
 4.9e-4
 3.5e-4
 2.3e-4
 1.3e-4
 		6.7e-5
Doba vzdalenosti (s)
 1
 2
 3
 14
 66
 132
 		226
Doba synchronizace (s)
 0.01 (58%)
 0.02 (55%)
 0.02 (53%)
 0.04 (56%)
 0.1 (59%)
 0.15 (55%)
 		0.3
Doba vypoctu (s)
 154
 332
 763
 2226
 13706
 35972
 		1.7dne**
* Neni krok 0.005*k
** Vykonejsi stroj

A ten samy vypocet provedeny na sekvencnim algoritmu... Vypocet proveden na stroji zhruba polovicniho vykonu. Cekal jsem zhruba stejnou dobu vypoctu, protoze 50% se provadi synchronizace, ale doba je naopak spise dvojnasbna. Cim to, netusim.

Sada 3
<konverg3>
Prostorovy krok (bodu mrizky)
 0.03 (133^2)
 		0.02 (200^2)
 		0.01 (400^2)
 		0.0075 (533^2)
Casovy krok
 1e-4
 4.4e-5
 1.1e-5
 6.3e-6
Chyba
 1.8e-4
 5.5e-5
 2.5e-5
 7.9e-6
Chyba haus



Doba vypoctu - priblizne (s)
 320
 1260
 19800
 61980

Odchylka od vypoctu na paralelnim programu tam sice je, ale: Skutecna odchylka je zhruba odmocnina z uvadenych hodnot, coz jsou ale stale hodnoty hluboce pod velikosti kroku (jak je vizualne ukazano na nasledujicim obrazku).

Znovu porovnani sekvencniho a paralelniho algoritmu (cas 0.9, krok 0.0075 x 6.3e-6). Cervena sekvencni, Zelena paralelni verze. Vlevo plny obrazek, vpravo vyrez. Shoda je opravdu obdivuhodna. :-) Co si nepochvalim sam, to nemam. Vykresleni exaktniho reseni jen zneprehlednuje obrazek, protoze se opravdu temer kryje (prakticky az na interpolace mezi body).
Zakladni porovnani
 Maly vyrez




Jednim z parametru simulaci je reinicializace, takze dalsi test se zameril na vliv poctu reinicializaci na vysledek. Simulace jsem provedl na kroku 0.02 a odpovidajicim casovem kroku.

Sada 4
<reinit1>
Pocet reinicializaci
 1
 2
 3
 4
Chyba
 3.2e-5
 3.3e-5
 3.3e-5
 3.3e-5
Chyba haus
 4.9e-4
 4.9e-4
 4.9e-4
 4.9e-4
Doba vypoctu (s)
 753
 834
 744
 750

A muzeme konstatovat, ze reinicializace nema v tomto jednoduchem pripade na chybu temer zadny vliv. Casovy vypadek pro 2 reinicializace je zpusoben vytizenim kompu behem simulace. Malym prekvapenim je to, ze chyba je jeste lepsi nez bez reinicializace. Je vsak nepatrna.

Dalsi studovanou vlastnosti je pochopitelne narrow band. Nastavit vhodne vsechny mozne parametry se ukazalo jako docela netrivialni zalezitost - napr. se take ukazalo nutne prepracovat trochu duvody k reinicializaci. Nasledujici tabulka ukazuje vysledky na pokusu s krokem 0.02, kdyz budeme postupne zvetsovat narrow band z 20 bodu na 50. Chyba byla merena na casove hladine 0.72. Doba synchronizace radove e-3 ve vsech pripadech. Doba vypoctu mereny do hladiny 0.9, pokud se tam algoritmus dostal.

Sada 5
<narrow1>
Velikost pasu
 20
 30
 40
 50
Chyba
 <chyba>*
 1.8e-3
 1.0e-3
 5.6e-5
Chyba haus
4.7e-3
 1.3e-3
 1.4e-4
Doba vypoctu
5min
 7min
 9min
* Pri vypoctu se krivka dostala prilis blizko ke kraji a reinicializace to neustala.
 
Vidime, ze chyba je mnohem horsi nez pri pouziti plne mrizky pokud pouzijeme mene nez sirku 50. Myslim si, ze dramaticky skok v presnosti je zpusobeny tim, ze na uzsim pasu se krivka az prilis priblizuje hranam.  Take casove zrychleni jsem subjektivne cekal vetsi. Na sirce 50 uz je jen a neco rychlejsi (z puvodnich 13min). A nakonec taky nejaka poradne spatna zprava: Chyba pri reinicializaci znamenek tam furt je i pres muj opravny patch... Sice mnohem mensi (radove par bodu), ale je tam.

Dalsi sada testu s ponekud vice pesimistickou (castejsi a casnejsi) reinicializaci (upravena stara verze). Jinak uplne stejne podminky jako minula sada.

Sada 6
<narrow2>
Velikost pasu
 20
 30
 40
 50
Chyba
 1.6e-3
 1.4e-3
 2.4e-4
 2.6e-4
Chyba haus
2.0e-3
 1.8e-3
 3.5e-4
 3.4e-4
Doba vypoctu
 5min
 6min
 7min
 9min

Co dodat. I uzky pas nam dava aspon nejake vysledky, zrychleni kvuli caste reinicializaci je pomerne male. Sirsi pas vykazuje jiste zlepseni presnosti, ale napr. pouziti sirky 50 je horsi nez 40. Asi mu lepe sedlo pokryti ctverci. Verze 50 je dokonce horsi nez pri mene caste reinicializaci v predchozim pripade.

Protoze jsem musel opet upravit generovani min a vyhodnocovani reinicializaci, tak jsem provedl predchozi simulace znovu porovnal vysledky - nastesti sedi. <narrow3>

Na kroku 0.02 se nemohla vyhoda narrowbandu projevit naplno, takze jsme presli na jemnejsi krok 0.01 a znovu zopakovali ten samy pokus.

Sada 7
<narrow4>
Velikost pasu
 20 30
 40
 50
Chyba
 2.2e-3
 1.2e-3
 1.4e-3
 3.2e-4
Chyba haus
 4.8e-3
 2.5e-3
 1.8e-3
 3.9e-4
Doba vypoctu (s)
 1396
 1937
 2760
 3445
* Doba vypoctu plne mrizky je 13706 s

Prestoze jsme zlepsili prostorovy krok z 0.02 na 0.01, tak jsme chybu nezmensili - urcite take proto, ze jsme ponechali bodovou (!) velikost pasu z predchoziho experimentu. Na tomto pokusu uz lze zretelne videt casova uspora pasu.

Pomerne velka chyba je dle me zpusobena tim, ze se krivka nekde az prilis priblizi hranici. Na potvrzeni ci vyvraceni teto domenky jsem provedl nasledujici 2 pokusy. Prvni zvysuje prekryv pokryvajicich bloku, cimz se zlepsi pokryti. Druhy zprisnuje reinicializaci (jen podminku) - velikost pokryti zustava stejna.

Sada 8
<covery1>
Prekryti (%)
 20
 30
 40
 50
 60
 70
Chyba
 1.1e-3
 9.5e-4
 9.7e-4
 1.1e-3
 1.1e-3
 1.1e-3
Chyba haus
 1.2e-3
 1.1e-3
 1.9e-3
 1.8e-3
 1.8e-3
 1.8e-3
Doba vypoctu (s)
 1659
 1772
 1773
 1776
 1737
 1714

Takze ma prvni domenka, ze by se to melo malinko zlepsovat se nepotvrdila - chyba zustava temer nemenna. Potesujici je, ze se nemeni take doba potrebna k vypoctu. Uvazime-li, ze prochazi mnohem vic bodu dvakrat a vickrat, tak je to pomerne prekvapujici.

Sada 9
<narrow5>
Reinicializacni vzdalenost od kraje (body)
 6
 9
 12
Chyba
 1.2e-3
 1.0e-3
 7.8e-4
Chyba haus
 2.5e-3
 1.9e-3
 7.7e-4
Doba vypoctu (s)
 1900
 2125
 1975
Pocet reinicializaci
 20
 23
 43
* Chyba pri plne mrizce 3.6e-5 (haus 2.3e-4)

Druha sada pokusu uz nastesti potvrzuje moji domnenku a vidime, ze se chyba podstatne zlepsi, nenechame-li krivku priblizit se prilis okrajum narrow bandu. A opet se nestacim divit, ze zvetseni poctu reinicializaci na dvojnasobek nezpomali podstatne vypocet - tyka se asi jen uzkeho pasu, na sirsim by to melo jit poznat. Vykyvy jsou asi zpusobeny vytizenim kompu behem vypoctu.

Dalsi veci potrebnou pro uspesne nasazeni metody je aspon orientacni znalost stability schematu/metody, ktere se venuje nasledujici tabulka. Vratili jsme se pro zmenu zase na vypocet na cele ctvercove oblasti. V nasledujici tabulce mame zobrazenou chybu/haus pri ruznych nastavenich prostoroveho a casoveho kroku.

Sada 10
<stabil1, stabil2, stabil3>
Cas. krok  \ Prostor. krok
0.03
 		0.02
 		0.01
5e-6
 1.1e-4 / 1.5e-3
 3.3e-5 / 4.1e-4
 3.3e-5 / 2.0e-4
1e-5
 1.1e-4 / 1.5e-3
 3.4e-5 / 4.2e-4
 3.5e-5 / 2.1e-4
5e-5
 1.2e-4 / 1.5e-3
 4.8e-5 / 4.8e-4
 <nestab>
1e-4
 1.5e-4 / 1.6e-3
 6.9e-5 / 5.7e-4
5e-4
 <nestab>
 <nestab>

Podstatne je pro nas zatim to, ze chyba se uz podstatne nezlepsuje, zjemnujeme-li casovy krok. Na hrubem kroku site uz chybu nezlepsime, i kdyz se par bodu bude presne kryt s resenim.