Date post: | 29-Nov-2014 |
Category: |
Education |
Upload: | cristian-maureira |
View: | 580 times |
Download: | 0 times |
Algoritmo Tree CodeAproximando el calculo de la fuerza, en el problema de n-cuerpos.
Cristian D. Maureira [email protected]
Universidad TecnicaFederico Santa Marıa
19 de septiembre de 2011
Algoritmo Tree Code
IntroduccionProblema de n-cuerpos
DefinicionPredecir el movimiento de un grupo de objetos celestes, que vaninteractuando unos con otros gravitacionalmente.
2 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
IntroduccionSecciones crıticas
� Posiciones iniciales.� Random.� Plummer Model.
� Metodo de integracion.� Euler.� Leapfrog.� Runge Kutta.� Two step Adams-Bashworth.� etc.
� Calculo de las fuerzas.� Particle-Particle. O(n2)� Particle-Mesh. O(n + ng log ng)� Treecode. O(n log n)� Multipole. O(n)� etc.
3 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
IntroduccionAlgoritmo General
� Calculo de la fuerza.� Posiciones iniciales xi .� Velocidades iniciales vi .� 1 ≤ i ≤ N
fij = G ·mi ·mj
||rij ||2·
rij||ri j ||
� mi y mj masas de los cuerpos i y j .� rij = (xj − xi ) vector de distancia entre los cuerpos i y j .� G , constante gravitacional. (6, 67428× 10−11m3kg−1s−2)
4 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
IntroduccionTree-code
“A Hierarchical O(N log N) Force Calculation Algorithm”, JoshBarnes & Piet Hut, 1986. Nature 324, 446.
� Joshua Edward Barnes� Faculty member at the Institute for Astronomy (IfA), University of
Hawaii.
� Piet Hut� Professor of Interdisciplinary Studies, Institute for Advanced Study.
5 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeIdea
“Agrupar cuerpos cercanos y aproximarlos en un solo cuerpo”
� Si el grupo esta muy lejos, se aproximan los efectos gravitacionalesutilizando el centro de masa.
� Centro de masa, promedio de las posiciones de un cuerpo en ungrupo, ponderado por la masa.
6 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeIdea
“Agrupar cuerpos cercanos y aproximarlos en un solo cuerpo”
� Si el grupo esta muy lejos, se aproximan los efectos gravitacionalesutilizando el centro de masa.
� Centro de masa, promedio de las posiciones de un cuerpo en ungrupo, ponderado por la masa.
6 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeIdea
“Agrupar cuerpos cercanos y aproximarlos en un solo cuerpo”
� Si el grupo esta muy lejos, se aproximan los efectos gravitacionalesutilizando el centro de masa.
� Centro de masa, promedio de las posiciones de un cuerpo en ungrupo, ponderado por la masa.
6 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeIdea
Centro de Masa
Formalmente si dos cuerpos con posiciones (x1, y1), (x2, y2) y masasm1, m2, la masa total del centro de masa (x , y) esta dada por:
m = m1 + m2
x =(x1 ·m1 + x2 ·m2)
m
y =(y1 ·m1 + y2 ·m2)
m
7 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAlgoritmo
� Esquema inteligente para agrupar cuerpos suficientemente lejos.
� Recursivamente divide el conjunto de cuerpos en gruposguardandolos en un “quad-tree”.
� Cada nodo representa una region en un espacio de dos dimensiones.
� El nodo mas alto representa todo el espacio, y sus cuatro hijosrepresentan cuatro cuadrantes en el espacio,
8 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAlgoritmo
� Esquema inteligente para agrupar cuerpos suficientemente lejos.
� Recursivamente divide el conjunto de cuerpos en gruposguardandolos en un “quad-tree”.
� Cada nodo representa una region en un espacio de dos dimensiones.
� El nodo mas alto representa todo el espacio, y sus cuatro hijosrepresentan cuatro cuadrantes en el espacio,
8 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAlgoritmo
� Esquema inteligente para agrupar cuerpos suficientemente lejos.
� Recursivamente divide el conjunto de cuerpos en gruposguardandolos en un “quad-tree”.
� Cada nodo representa una region en un espacio de dos dimensiones.
� El nodo mas alto representa todo el espacio, y sus cuatro hijosrepresentan cuatro cuadrantes en el espacio,
8 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAlgoritmo
� Esquema inteligente para agrupar cuerpos suficientemente lejos.
� Recursivamente divide el conjunto de cuerpos en gruposguardandolos en un “quad-tree”.
� Cada nodo representa una region en un espacio de dos dimensiones.
� El nodo mas alto representa todo el espacio, y sus cuatro hijosrepresentan cuatro cuadrantes en el espacio,
8 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAproximacion
A
B
C
D
E
FG
H
9 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAproximacion
� Cada nodo externo, representa un unico cuerpo.
� Cada nodo interno, representa el grupo de cuerpos debajo de ella,(guarda “centro de masa” y “masa total”).
10 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAproximacion
� Cada nodo externo, representa un unico cuerpo.
� Cada nodo interno, representa el grupo de cuerpos debajo de ella,(guarda “centro de masa” y “masa total”).
10 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeAproximacion
*
ANO NE
NO
B
NE
C
SO SE
D
SO
NO
E
NE
F
SO
G
SE
HSE
Cuerpo Region con > 1 cuerpo Cuadrante vacıo
11 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza
� En un cuerpo particular.� Recorrer los nodos del arbol, partiendo de la raız.
� Centro de masa de un nodo interno:� Si lo suficientemente lejos del cuerpo.
� Se aproximan los cuerpos contenidos. (con centro de masa y masa total)
� No lo suficientemente lejos del cuerpo.� Recorrer los sub-arboles recursivamente.
12 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza
� ¿Como determinarlo?
� Cociente = ancho region nodo (s)distancia Cuerpo-CM (d)
� Despues, comparar con un valor umbral θ.� Si s
d < θ, entonces el nodo interno esta lo suficiente lejos.� Ajustando θ, podemos cambiar la velocidad y la precision de la
simulacion.� Se suele utilizar θ = 0,5. Si θ = 0, degenera (fuerza bruta).
13 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.
� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.
� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.
� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.� Subdivide la region creando cuatro hijos.
� Entonces, recursivamente inserta ambos cuerpos, b y c, en elcuadrante apropiado.
� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.
� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.� Recursividad!
� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
Si queremos ingresar el cuerpo b en el arbol con raız en el nodo x.
1. Si el nodo x no contiene un cuerpo, poner el nuevo cuerpo b ahı.
2. Si el nodo x es un nodo interno, actualizar el CM y M.(Recursivamente inserta el cuerpo b en el cuadrante apropiado).
3. Si el nodo x es un nodo externo, digamos que contiene un cuerpoc, entonces hay dos cuerpos, b y c en la misma region.� Subdivide la region creando cuatro hijos.� Entonces, recursivamente inserta ambos cuerpos, b y c, en el
cuadrante apropiado.� Recursividad!� Finalmente, actualizar el CM y M de x.
14 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Ejemplo, 5 cuerpos.� Convencion ramas, de izquierda a derecha (NO, NE, SO y SE).
A
B
C D
ENO NE SO SE
15 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Agregar cuerpo A.� Encaja en el cuadrante NO de la raız.
masa: 1
NOSO
NESE
1
A
NO NE SO SE
16 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Agregar cuerpo B.� Encaja en el cuadrante NE de la raız.
masa: 2
NOSO
NESE
2
A
NO
B
NE SO SE
17 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Agregar cuerpo C.� Cuadrante NE ocupado por B, se crea rama y se insertan los dos.
masa: 2
masa: 3
NOSO
NESE
3
A
NO
2
B
NO NE
C
SO SE
SO SE
18 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Agregar cuerpo D.� Encaja en el cuadrante SE de la rama.
masa: 3
masa: 4
NOSO
NESE
4
A
NO
3
B
NO NE
C
SO
D
SE
SO SE
19 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeConstruyendo un arbol
� Agregar cuerpo E.� Encaja en el cuadrante SE de la raız.
masa: 5
NOSO
NESE
5
A
NO
3
B
NO NE
C
SO
D
SE
SO
E
SE
20 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
Calcular la fuerza que ejerce la red sobre un cuerpo b, comenzandocon la raiz:
1. Si el nodo actual es un nodo externo (y no b).Calcular y agregar fuerza.
2. Si no, calcular sd . Si s
d < θ, nodo interno como un unico cuerpo.Calcular y agregar fuerza.
3. Si no, recursividad del procedimiento en cada hijo del nodo actual.
21 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
Calcular la fuerza que ejerce la red sobre un cuerpo b, comenzandocon la raiz:
1. Si el nodo actual es un nodo externo (y no b).Calcular y agregar fuerza.
2. Si no, calcular sd . Si s
d < θ, nodo interno como un unico cuerpo.Calcular y agregar fuerza.
3. Si no, recursividad del procedimiento en cada hijo del nodo actual.
21 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
Calcular la fuerza que ejerce la red sobre un cuerpo b, comenzandocon la raiz:
1. Si el nodo actual es un nodo externo (y no b).Calcular y agregar fuerza.
2. Si no, calcular sd . Si s
d < θ, nodo interno como un unico cuerpo.Calcular y agregar fuerza.
3. Si no, recursividad del procedimiento en cada hijo del nodo actual.
21 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
� Ejemplo, calcular la fuerza de la red sobre el cuerpo a.� Comenzaremos en la raız (nodo interno).
� Representa CM de los 6 cuerpos.� a, b, c, d, e y f, con masas 1, 2, 3, 4, 5 y 6 Kg.
El calculo de fuerza procede de la siguiente forma.
22 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
1. El primer nodo examinado es la raız.
� Cociente entre A y CM. sd = 100
43,1 > θ = 0,5
� → Proceso recursivo dentro.
A
B CD
E
F
A
B C D
E
F
23 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
2. El primer hijo es el cuerpo A
� No ejerce fuerza sobre si mismo.
� → No hacemos nada.
A
B C D
E
F
24 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
3. Hijo representante NE (contiene b, c, d y e).
� sd = 50
62,7 > θ.
� → Proceso recursivo dentro.
A
B C D
E
F
25 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
4. Hijo representante NE del padre (contiene b, c y d).
� sd = 25/66,9 < θ.
� → Se calcula la fuerza como un solo nodo.
A
B C D
E
F
26 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
5. El siguiente hijo es el que contiene el cuerpo e.
� Este es un nodo externo.
� → Calculamos fuerza entre a y e.
A
B C D
E
F
27 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
6. Volvemos al nivel anterior, para ver otro hijo.
� Este es un nodo externo.
� → Calculamos fuerza entre a y f.
A
B C D
E
F
28 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Barnes-Hut Tree CodeCalculo de la fuerza sobre un cuerpo
7. Finalmente, en cada paso vamos sumando las fuerzas calculadas,para obtener la fuerza total de la red sobre el cuerpo a.
29 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).
� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.
� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree Code
Conclusiones
� Muestra nuevo enfoque para abordar el problema.
� Es mas rapido, pues no recorre todos los cuerpos.
� Disminuye el orden del algoritmo de O(n2) a O(n log n).� Generamos errores, lo que nos lleva a tener una menor precision.
� Podemos controlar la precision, modificando θ.� Desarrollo multipolar (Multipole expansions) lo corrige!.
30 of 31Cristian D. Maureira Fredes
Algoritmo Tree CodeAproximando el calculo de la fuerza, en el problema de n-cuerpos.
Cristian D. Maureira [email protected]
Universidad TecnicaFederico Santa Marıa
19 de septiembre de 2011