direita|miniaturadaimagem|300x300px| Uma simulação com 100 corpos, onde a árvore de Barnes-Hut é visualizada como caixas azuis. A simulação de Barnes-Hut (nomeada em homenagem a Joshua Barnes e Piet Hut) é um algoritmo de aproximação para realizar uma simulação de N corpos. Ela se destaca por ter ordem O(n log n) em comparação com um algoritmo de soma direta que seria O(n2).
O volume de simulação é geralmente dividido em células cúbicas por meio de uma octree (em um espaço tridimensional), de modo que apenas as partículas de células próximas precisam ser tratadas individualmente, e as partículas em células distantes podem ser tratadas como uma única partícula grande centrada no centro de massa da célula (ou como uma expansão multipolar de baixa ordem). miniaturadaimagem| Visualização dinâmica da estrutura em quadtree do algoritmo de Barnes-Hut para o problema de N corpos em 2D Alguns dos projetos de computação de alto desempenho mais exigentes realizam astrofísica computacional usando o algoritmo de código de árvore Barnes-Hut, como o DEGIMA .
Algoritmo
A árvore Barnes–Hut Em uma simulação tridimensional de N-corpos, o algoritmo de Barnes–Hut divide recursivamente os n corpos em grupos, armazenando-os em uma octree (ou uma quadtree em uma simulação 2D). Cada nó nesta árvore representa uma região do espaço tridimensional. O nó superior representa todo o espaço, e seus oito filhos representam os oito octantes do espaço. O espaço é subdividido recursivamente em octantes até que cada subdivisão contenha 0 ou 1 corpo (algumas regiões não possuem corpos em todos os seus octantes). Existem dois tipos de nós na octree: nós internos e nós externos. Um nó externo não possui filhos e está vazio ou representa um único corpo. Cada nó interno representa o grupo de corpos abaixo dele e armazena o centro de massa e a massa total de todos os seus corpos filhos.
Calculando a força que atua sobre um corpo Para calcular a força resultante sobre um determinado corpo, percorrem-se os nós da árvore, começando pela raiz. Se o centro de massa de um nó interno estiver suficientemente distante do corpo, os corpos contidos nessa parte da árvore são tratados como uma única partícula cuja posição e massa são, respectivamente, o centro de massa e a massa total do nó interno. Se o nó interno estiver suficientemente próximo do corpo, o processo se repete para cada um de seus filhos.
O fato de um nó estar ou não suficientemente distante de um corpo depende do quociente. , onde s é a largura da região representada pelo nó interno e d é a distância entre o corpo e o centro de massa do nó. O nó está suficientemente distante quando essa proporção é menor que um valor limite θ . O parâmetro θ determina a precisão da simulação; valores maiores de θ aumentam a velocidade da simulação, mas diminuem sua precisão. Se θ = 0, nenhum nó interno é tratado como um único corpo e o algoritmo degenera em um algoritmo de soma direta.
Ligações externas Códigos de árvore, J. Barnes Parallel TreeCode Exemplo de simulação gráfica de Barnes-Hut em HTML5/JavaScript PEPC – O solucionador paralelo de Coulomb bastante eficiente, um código de árvore Barnes-Hut paralelo de código aberto com kernel de interação intercambiável para uma infinidade de aplicações. Programa de simulação N-corpos em GPU paralela com percurso rápido em árvore de partículas sem pilha em beltoforion.de
Categoria:Integração numérica Categoria:Cosmologia física Categoria:Gravitação Categoria:Simulação