Grid felhasználás: alkalmazott matematika Konvex testek egyensúlyi osztályozása a Saleve keretrendszerrel
Kápolnai Richárd1 Domokos Gábor2 Szabó Tímea2 1 BME
Irányítástechnika és Informatika Tanszék
[email protected] 2 BME Szilárdságtani és Tartószerkezeti Tanszék
e-Science Cafè, 2011. november 14.
Verzió: $Id: scicafe.tex 273 2011-11-14 10:45:12Z richard $
Egyensúlyi pontok Konvex, homogén test felszínén távolság a tkp-tól: R(θ, ϕ) Egyensúlyi pontok az R szélsőértékei (minimum, maximum és nyereg) S R
U R
H
π π/2 0
0 π/4
θ
ϕ
-π/2
π/2 3π/4 π -π
Elforgatott ellipszoid magasságfüggvénye Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
2 / 17
Ellipszoid magasságfüggvénye és gradiensmezője 3
π
2.8 2.6 π/2 2.4
ϕ
2.2 0
2 1.8 1.6
-π/2 1.4 1.2 -π
1 0
Kápolnai Richárd (BME)
π/4
π/2
3π/4
Grid felhasználás: θalkalmazott matematika
π e-Science Cafè, 2011.11.14.
3 / 17
Egyensúlyi osztályok (S, U): a test egyensúlyi osztálya, pl. a kocka: (6,8) S
(1,1)
U
1
2
3
4
5
6
7
8
…
1 2 3 4
(1,2)
5 6 7 8 …
Domokos Gábor – Várkonyi Péter, 2006. Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
4 / 17
Minden osztályban van valamilyen test S
U
1
2
3
4
5
6
7
8
…
1 2 3 4 5 6 7 8 Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
5 / 17
Az egyensúlyi gráf Finomabb felosztás: izolált pályák (U −→ H és H −→ S) egy négyszögelt gráfot határoznak meg 4
3 2.8
3
2.6 2 2.4 1
2.2
0
2 1.8
-1
1.6 -2 1.4 -3
-4 -0.5
1.2
0
0.5
1
1.5
2
2.5
3
3.5
1
Az R függvény Morse–Smalekomplexének gráfja Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
6 / 17
Futási eredmények – alosztályok felsorolása S + U ≤ 10-ig Hányféle topológia lehetséges egy (S, U) egyensúlyi osztályon belül? n = S + U a csúcsok száma: 3
4
5
6
7
8
9
10
U\S 1 2 3 4 5 6 7 8 9
1 1 1 1 2 3 6 12 27 65
2 1 2 5 13 35 104 315 1021
3 1 5 20 83 340 1401 5809
Kápolnai Richárd (BME)
4 2 13 83 504 2843 15578
5 3 35 340 2843 21420
6 6 104 1401 15578
Grid felhasználás: alkalmazott matematika
7 12 315 5809
8 27 1021
9 65
e-Science Cafè, 2011.11.14.
7 / 17
Felsorolás hatékonysága
Jelölje S az összes egyensúlyi gráf halmazát n 3 4 5 6 7 8 9 10
feldolgozási idő 0 0 0 0 6 sec 10 perc 20 óra 81 nap
Kápolnai Richárd (BME)
vizsgált lehetőségek 2 14 291 14 468 1,1 · 106 1,1 · 108 1,2 · 1010 1,4 · 1012
|S| 2 4 14 52 248 1 416 9 172 66 366
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
8 / 17
Gráfok párhuzamos generálása ismétlés nélkül G0
G1
G4
G2
G5
G6
G3
G7
G8
G9
Csak a fekete élek mentén generálunk (legjobb redukció)
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
9 / 17
Gráfok párhuzamos generálása ismétlés nélkül G0
G1
G4
G2
G5
G6
G3
G7
G8
G9
Csak a fekete élek mentén generálunk (legjobb redukció) Itt 6 független job indítható Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
9 / 17
Gráfok párhuzamos generálása ismétlés nélkül G0
G1
G4
G2
G5
G6
G3
G7
G8
G9
Csak a fekete élek mentén generálunk (legjobb redukció) Itt 6 független job indítható Függetlenül generálják a megoldásokat (Brinkmann – McKay, 2007) Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
9 / 17
Egyenletes feldarabolás a Saleve alkalmazáshoz G0
G1
G4
G2
G5
G6
G
G3
G7
G8
G9
G
Nem tudjuk előre az egyes darabok számításigényét Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
10 / 17
Egyenletes feldarabolás a Saleve alkalmazáshoz G0
G1
G4
G2
G5
G6
G
G3
G7
G8
G9
G
Nem tudjuk előre az egyes darabok számításigényét Iteratív darabolás: bizonyos részeket manuálisan továbbdarabolunk Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
10 / 17
Egyenletes feldarabolás a Saleve alkalmazáshoz G0
G1
G4
G2
G5
G6
G
G3
G7
G8
G9
G
Nem tudjuk előre az egyes darabok számításigényét Iteratív darabolás: bizonyos részeket manuálisan továbbdarabolunk Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
10 / 17
Gridalkalmazás fejlesztése a Saleve keretrendszerben Példa: függvény integrálása [0, 1]-en: kis módosítás a forráskódon
Eredeti forráskód
Saleve kliens: majdnem ugyanaz,
int main(int ac, char *av[]) { double result = integrate("0.0", "1.0"); printf("%lf\n", result); }
int saleve_main(int argc, char *argv[]) { double subresult = integrate(argv[1], argv[2]); printf("%lf", subresult); }
Az alkalmazás lényegi részén (integrate) nem kell változtatni
kiegészítve a paramétertér felosztásával, összegzésével: void saleve_span() { saleve_addInstance("0.0 saleve_addInstance("0.1 ...
0.1"); 0.2");
Automatikus: (többdimenziós) paramétertartomány feldarabolása, grides job futtatása minden darabhoz C/C++ támogatás, „becsomagolható” bármilyen konzolos alkalmazás (Java, Matlab, Python, Fortran, . . . ) Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
11 / 17
Saleve: transzparens működés A kliens elküldi önmagát és a feladatot: 1
2
A szerver jobokat küld a gridbe
tux@linux#
A kliens összegzi a részeredményeket 4
A visszatérő részeredményeket a szerver továbbítja a kliensnek 3
P
5 7
9
tux@linux#
4
Kápolnai Richárd (BME)
=
tux@linux#
25 Grid felhasználás: alkalmazott matematika
7
5 9 4
e-Science Cafè, 2011.11.14.
12 / 17
Saleve gridalkalmazás hatékonysága Feldolgozási idők:
Sorbanállás + feldolgozás:
n = 10 pontszámra 1076 job, összesen 1923 cpu óra (80 nap) A kezdeti paramétertartomány az n = 8 méretű T -gráfok 1. iteráció: 1000 job, 2. iteráció: 4 job továbbdarabolva Ideális párhuzamosításban minden job kb. 2 órás lenne Volt 11 órás job is, így kb. 6-szoros futási idő (vö. 80 nappal) Hosszú várakozási sorok automatikus kezelése Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
13 / 17
Vannak-e a Gömböc mellett más ősök? n < 8-ig minden gráf előállítható a Gömböcből, ahol n = S + U. A programmal generált gráfokra ellenőrizhető: n 4 5 6 7 8 9 10
mindkettő 2 6 32 172
Kápolnai Richárd (BME)
csak C1 1 2 4 10
csak C2 1 6 16 66
egyik sem -
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
14 / 17
Vannak-e a Gömböc mellett más ősök? n < 8-ig minden gráf előállítható a Gömböcből, ahol n = S + U. A programmal generált gráfokra ellenőrizhető: n 4 5 6 7 8 9 10
mindkettő 2 6 32 172
csak C1 1 2 4 10
csak C2 1 6 16 66
egyik sem -
Léteznek-e egyéb ősök? Létezik-e hozzájuk fizikai test? Hogyan képzeljük el őket?
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
14 / 17
Vannak-e a Gömböc mellett más ősök? n < 8-ig minden gráf előállítható a Gömböcből, ahol n = S + U. A programmal generált gráfokra ellenőrizhető: n 4 5 6 7 8 9 10
mindkettő 2 6 32 172 1071 7370 55766
csak C1 1 2 4 10 33 114 474
csak C2 1 6 16 66 311 1688 10125
egyik sem 1 1
Léteznek-e egyéb ősök? Létezik-e hozzájuk fizikai test? Hogyan képzeljük el őket? n ≥ 8 esetén vannak más ősök!
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
14 / 17
Minimálpoliéderek
Ős: semmiből sem származtatható
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
15 / 17
Minimálpoliéderek
Ős: semmiből sem származtatható Példa: szabályos poliéderek, gúla, . . .
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
15 / 17
Minimálpoliéderek
Ős: semmiből sem származtatható Példa: szabályos poliéderek, gúla, . . . Meghatároztunk egy olyan test-kategóriát, mely nem származtatható a Gömböcből.
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
15 / 17
Ős megállapítása Egy gráfot általában többféleképpen lehet generálni egy ősből, az ős egyértelműen megállapítható Kb. 100 bescannelt kavicsnak megállapítottuk az ősét
Scannelt kavics pályái, ábra: GTT és SZT (Sípos András–Szabó Tímea)
Kápolnai Richárd (BME)
Grid felhasználás: alkalmazott matematika
e-Science Cafè, 2011.11.14.
16 / 17
Köszönöm szépen a figyelmet! Saleve keretrendszer http://cern.ch/saleve/ Hungrid Virtuális Szervezet http://grid.kfki.hu/hungrid/ G. Brinkmann – B. D. McKay, Fast generation of planar graphs, MATCH Comm., (2007) 58 G. Domokos – P. Várkonyi, Static equilibria of rigid bodies: dice, pebbles and the Poincaré–Hopf theorem, J Nonlinear Sci, (2006) 16 P. Dóbé – R. Kápolnai – A. Sipos – I. Szeberényi, Applying the improved Saleve framework for modeling abrasion of pebbles, in LSSC, vol. 5910 of LNCS, 2010 R. Kápolnai – G. Domokos, Inductive generation of convex bodies, in The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 170–178, 2011