Métodos N-Corpos e de Malha de Partículas

O cálculo das forças gravitacionais ou eletrostáticas mútuas entre muitas partículas custa ingenuamente o quadrado do seu número, e os métodos rápidos N-corpos e de malha de partículas reduzem isso para quase linear, tornando possíveis simulações de galáxias e plasmas com milhões de partículas.

Definition

Os métodos N-corpos e de malha de partículas são algoritmos que aproximam as forças de longo alcance entre muitas partículas interagentes em tempo inferior ao quadrático, agrupando partículas distantes ou resolvendo o campo em uma grade.

Scope

Este tópico abrange algoritmos escaláveis para interações de partículas de longo alcance: códigos de árvore hierárquicos como Barnes-Hut, o método multipolar rápido e esquemas de malha de partículas e de partícula-partícula em malha baseados em grade. Aborda as compensações entre precisão e custo e o papel desses métodos em grandes simulações gravitacionais e eletrostáticas.

Core questions

• Por que a soma direta de forças de longo alcance par a par é proibitivamente cara?
• Como os códigos de árvore agrupam partículas distantes para reduzir o custo do cálculo da força?
• Como o método multipolar rápido alcança escalonamento quase linear com erro controlado?
• Como os métodos de malha de partículas resolvem o campo em uma grade para lidar com forças de longo alcance?

Key theories

Códigos de árvore hierárquicos

O algoritmo de Barnes-Hut agrupa partículas distantes em células cuja força coletiva é aproximada pelo seu centro de massa, reduzindo o custo da avaliação da força de quadrático para a ordem N log N.

Método multipolar rápido

O método multipolar rápido representa grupos de partículas por expansões multipolares truncadas e as traduz hierarquicamente, alcançando escalonamento quase linear com uma precisão rigorosamente controlável.

Métodos de malha de partículas

Os esquemas de malha de partículas e de partícula-partícula em malha interpolam cargas ou massas em uma grade, resolvem o campo com transformadas rápidas de Fourier e adicionam correções de curto alcance, lidando eficientemente com interações de longo alcance.

Clinical relevance

Esses métodos impulsionam simulações cosmológicas e galácticas N-corpos de formação de estrutura, simulações de plasma e a eletrostática de longo alcance de grandes sistemas moleculares, e o método multipolar rápido é reconhecido como um dos algoritmos mais importantes do século XX.

History

Os métodos de malha de partículas foram sistematizados por Hockney e Eastwood na década de 1980; o código de árvore Barnes-Hut de 1986 e o método multipolar rápido de Greengard e Rokhlin de 1987 transformaram a simulação N-corpos, possibilitando as grandes simulações cosmológicas e moleculares que se seguiram.

Key figures

• Josh Barnes
• Piet Hut
• Leslie Greengard
• Vladimir Rokhlin

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

Por que não simplesmente calcular cada força par a par diretamente?

Os custos da soma direta crescem como o quadrado do número de partículas, então dobrar as partículas quadruplica o trabalho, o que se torna impossível para os milhões ou bilhões de partículas em simulações cosmológicas e grandes moleculares. Métodos rápidos reduzem isso para um custo quase linear.

Como os métodos de árvore e multipolares controlam seu erro?

Eles aproximam a influência de grupos distantes de partículas, e a aproximação é refinada incluindo mais termos multipolares ou usando um critério de abertura mais rigoroso, de modo que a precisão pode ser trocada por velocidade de forma controlada.