¿Podría usar el algoritmo de Barnes-Hut de forma iterativa, con múltiples cuadrantes centrales?

Question

¿Podría usar el algoritmo de Barnes-Hut de forma iterativa, con múltiples cuadrantes centrales?

Física
muchos cuerpos
algoritmos
simulaciones
gravedad newtoniana
física computacional

Urna de pulpo mágico

Me preguntaba si podría usar la simulación de Barnes-Hut más allá de lo que originalmente se pretendía. Para muchos algoritmos de Barnes-Hut, las fuerzas solo se consideran para un solo cuadrante, el centroide o el cuerpo estelar. Luego, el algoritmo se ramifica a partir de ahí, afectando áreas de influencia y cuadrantes recursivamente. Por ejemplo:

Parece que el algoritmo de Barnes-Hut anterior se basó en el cuerpo central de la animación.

Mi pregunta:

¿La ejecución de Barnes-Hut iterativamente en todos los cuerpos, tratando cada cuerpo a su vez como el centroide, daría como resultado una representación precisa de un problema de n cuerpos donde se considera la fuerza de gravedad suma de todos los cuerpos? ¿O estoy malinterpretando exactamente qué es el algoritmo de Barnes-Hut?

Si no entiendo bien el algoritmo, ¿alguien puede volver a explicar exactamente cómo funciona este algoritmo? Para cualquiera que entienda de programación hasta cierto punto, ¿alguien podría mirar este proyecto y decirme si me estoy perdiendo algo importante aquí? Es una implementación de Java GitHub del algoritmo Barnes-Hut , pero lo he iterado en todos los cuerpos (lo que puede ser increíblemente estúpido). Además... sí, sé que no es así como funciona el tiempo. Nota: Crédito debido al profesor original, como se indica en GitHub.

Además, para aquellos que no son expertos en tecnología, ¿pueden mirar este GIF y ver algo intrínsecamente incorrecto? El rojo es menos masa, el blanco es más masa; amarillo son dos o más masas colisionadas. Una vez que aparece el tercer punto amarillo (masa combinada), las cosas se ponen interesantes. No puedo decir si interesante bueno, o interesante... malo.

Urna de pulpo mágico

Aquí hay 1000 partículas en 1000 pasos: i.imgur.com/SwPbG4j.mp4

kyle kanos

Si está iterando sobre todos los cuerpos, ¿no está simplemente haciendo la ley del cuadrado inverso estándar en todos los cuerpos? En cuyo caso, ¿acaba de deshacer el propósito del método BH?

Urna de pulpo mágico

@KyleKanos, ¿no estaría haciendo la ley del cuadrado inverso desde un punto de referencia de partida diferente? Podría estar absolutamente equivocado en todos los aspectos.

kyle kanos

El objetivo de BH es reducir la carga de trabajo necesaria para resolver

a_{i} \sim \sum_{j} 1 / | r_{i} - r_{j} |^{2}

$a_i\sim\sum_j 1/\vert r_i-r_j\vert^2$ al tratar un grupo de partículas como un grupo para que otros objetos del grupo solo sientan los efectos del centro de masa. Si comienza a querer iterar sobre más partículas, entonces está deshaciendo todo el punto de la aproximación BH.

kyle kanos

Es decir, el BH hace resolver la aceleración

O (n \log n)

$\mathcal{O}(n\log n)$ , por lo que aumenta

n

$n$ (que es lo que quieres hacer) lo hará más lento . Si haces BH en todas las partículas, entonces vuelves a

O (n^{2})

$\mathcal{O}(n^2)$ algoritmo que es lo que BH fue diseñado para evitar.

Urna de pulpo mágico

@KyleKanos Entiendo que la complejidad del tiempo se deshace literalmente, mi pregunta principal es si la física resultante sería precisa o no para un problema de n cuerpos. No demasiado preocupado por la complejidad del tiempo. Una gran parte del algoritmo, además de la complejidad del tiempo tal como lo entendí, era la capacidad de generalizar interacciones de larga y corta distancia en un modelo grande. Además, creo que sería O(n^2log(n))así-- ¿verdad? O(n)x O(nlog(n))?

Urna de pulpo mágico

@KyleKanos Lo pregunto principalmente porque para los algoritmos de reducción de mapas agrupados o las aplicaciones de subprocesos múltiples, una n superior puede actuar porque O(nlog(n))las tareas para cada cuerpo pueden ejecutarse en paralelo. Por supuesto, esto tiene un límite superior de cuán alto npuede llegar a depender de la arquitectura. Simplemente se consideró si la física y la lógica de la interacción de partículas seguían siendo sólidas dado el método iterativo.

kyle kanos

Sí, la física resultante sería precisa porque todavía estás haciendo la suma de las fuerzas. Simplemente sería increíblemente más lento y no valdría la pena el esfuerzo de hacerlo de esa manera, incluso cuando está paralelizado.

Urna de pulpo mágico

@KyleKanos no cambia ninguna de las interacciones ni siquiera un poco? Parece tener resultados que son, con el tiempo, mucho menos estables debido a cómo se calcula la aceleración sobre cada cuerpo, en función de sus posiciones. ¿Está diciendo que probablemente sería mejor usar un solucionador ODE para valores grandes Ny resolver los problemas reales de n cuerpos, en términos de complejidad de tiempo y precisión? Sería negligente si no te pidiera algoritmos alternativos que conozcas, pareces estar bastante bien informado, y este es el primer algoritmo de física con el que honestamente me metí en cualquier capacidad. Gracias por tomarte tu tiempo :).

Respuestas (1)

¿Podría usar el algoritmo de Barnes-Hut de forma iterativa, con múltiples cuadrantes centrales?

Aquí hay 1000 partículas en 1000 pasos: i.imgur.com/SwPbG4j.mp4
Si está iterando sobre todos los cuerpos, ¿no está simplemente haciendo la ley del cuadrado inverso estándar en todos los cuerpos? En cuyo caso, ¿acaba de deshacer el propósito del método BH?
@KyleKanos, ¿no estaría haciendo la ley del cuadrado inverso desde un punto de referencia de partida diferente? Podría estar absolutamente equivocado en todos los aspectos.
El objetivo de BH es reducir la carga de trabajo necesaria para resolver $a_i\sim\sum_j 1/\vert r_i-r_j\vert^2$ al tratar un grupo de partículas como un grupo para que otros objetos del grupo solo sientan los efectos del centro de masa. Si comienza a querer iterar sobre más partículas, entonces está deshaciendo todo el punto de la aproximación BH.
Es decir, el BH hace resolver la aceleración $\mathcal{O}(n\log n)$ , por lo que aumenta $n$ (que es lo que quieres hacer) lo hará más lento . Si haces BH en todas las partículas, entonces vuelves a $\mathcal{O}(n^2)$ algoritmo que es lo que BH fue diseñado para evitar.
@KyleKanos Entiendo que la complejidad del tiempo se deshace literalmente, mi pregunta principal es si la física resultante sería precisa o no para un problema de n cuerpos. No demasiado preocupado por la complejidad del tiempo. Una gran parte del algoritmo, además de la complejidad del tiempo tal como lo entendí, era la capacidad de generalizar interacciones de larga y corta distancia en un modelo grande. Además, creo que sería O(n^2log(n))así-- ¿verdad? O(n)x O(nlog(n))?
@KyleKanos Lo pregunto principalmente porque para los algoritmos de reducción de mapas agrupados o las aplicaciones de subprocesos múltiples, una n superior puede actuar porque O(nlog(n))las tareas para cada cuerpo pueden ejecutarse en paralelo. Por supuesto, esto tiene un límite superior de cuán alto npuede llegar a depender de la arquitectura. Simplemente se consideró si la física y la lógica de la interacción de partículas seguían siendo sólidas dado el método iterativo.
Sí, la física resultante sería precisa porque todavía estás haciendo la suma de las fuerzas. Simplemente sería increíblemente más lento y no valdría la pena el esfuerzo de hacerlo de esa manera, incluso cuando está paralelizado.
@KyleKanos no cambia ninguna de las interacciones ni siquiera un poco? Parece tener resultados que son, con el tiempo, mucho menos estables debido a cómo se calcula la aceleración sobre cada cuerpo, en función de sus posiciones. ¿Está diciendo que probablemente sería mejor usar un solucionador ODE para valores grandes Ny resolver los problemas reales de n cuerpos, en términos de complejidad de tiempo y precisión? Sería negligente si no te pidiera algoritmos alternativos que conozcas, pareces estar bastante bien informado, y este es el primer algoritmo de física con el que honestamente me metí en cualquier capacidad. Gracias por tomarte tu tiempo :).

kyle kanos · Answer 1

Se sabe razonablemente que a distancias lo suficientemente grandes, la fuerza entre un grupo de objetos y otro objeto es esencialmente equivalente a la fuerza entre el centro de masa del grupo y el otro objeto:

F_{i} \sim \sum_{j} \frac{{metro}_{i} {metro}_{j}}{| r_{i} - r_{j} |^{2}} ≃ \frac{{metro}_{i} {metro}_{nene}}{| r_{i} - r_{com} |^{2}}

$F_i\sim\sum_j\frac{m_im_j}{\vert r_i-r_j\vert^2}\simeq \frac{m_im_\text{tot}}{\vert r_i-r_\text{com}\vert^2}$ dónde

m_{tot} = \sum_{j} m_{j}

$m_\text{tot}=\sum_jm_j$ y

r_{com}

$r_\text{com}$ es el centro de masa del

j

$j$ partículas

El algoritmo de Barnes-Hut aplica esto a $n$ -simulaciones de cuerpo al dividir el dominio en grupos de tamaño razonable y, por lo tanto, reducir la cantidad de cuerpos efectivos para iterar, en lugar de sumar $n$ partículas $n-1$ veces. Por lo que puedo ver/decir, el $n$ -Las simulaciones corporales que utilizan el algoritmo BH son bastante precisas, aunque hay mejores algoritmos en términos de velocidad (p. ej., método multipolar rápido u otros esquemas híbridos).

¿La ejecución de Barnes-Hut iterativamente en todos los cuerpos, tratando cada cuerpo a su vez como el centroide, daría como resultado una representación precisa de un problema de n cuerpos donde se considera la fuerza de gravedad suma de todos los cuerpos? ¿O estoy malinterpretando exactamente qué es el algoritmo de Barnes-Hut?

Su propuesta esencialmente quiere volver a la suma de $n$ partículas $n-1$ veces, lo que equivaldría a no usar BH en absoluto. Será preciso, aunque probablemente no mucho más preciso que BH, y ciertamente sería muy lento.

Entonces, al cuestionar si uno puede aplicar BH iterativamente a todos los cuerpos, sospecho que está malinterpretando el algoritmo BH. El objetivo es reducir la carga de trabajo requerida para encontrar las fuerzas sobre las partículas en cada paso de tiempo. Realmente no quiere aumentar el número de clústeres, quiere que se minimice porque haciendo un $\mathcal{O}\left(n^2\right)$ actualizar cada paso de tiempo es muy, muy lento.

¿Podría usar el algoritmo de Barnes-Hut de forma iterativa, con múltiples cuadrantes centrales?

Urna de pulpo mágico

Urna de pulpo mágico

kyle kanos

Urna de pulpo mágico

kyle kanos

kyle kanos

Urna de pulpo mágico

Urna de pulpo mágico

kyle kanos

Urna de pulpo mágico

Respuestas (1)

kyle kanos

Interacción mutua de partículas NNN en un plano cartesiano

¿Puedo rebobinar la gravedad?

Cálculo de una trayectoria orbital bidimensional con granularidad infinita (integración no Euler)

¿Por qué los objetos en una simulación de gravedad experimentan grandes aceleraciones repentinas?

Simulación del módulo de aterrizaje Philae desactivada por un factor de ~3

¿Cómo encontrar posiciones de nnn masas en la mecánica de Newton?

¿Cómo identificar estrellas binarias en la simulación de cuerpo NNN?

Datos de posición y velocidad del sistema solar

Métodos para manejar aproximaciones cercanas en simulaciones de cuerpo NNN

Disco estable para simulación de cuerpo NNN