Métodos N-cuerpos y de malla de partículas
El cálculo ingenuo de las fuerzas gravitacionales o electrostáticas mutuas entre muchas partículas cuesta el cuadrado de su número, y los métodos rápidos N-cuerpos y de malla de partículas reducen esto a casi lineal, lo que hace posibles simulaciones de galaxias y plasmas con millones de partículas.
Definition
Los métodos N-cuerpos y de malla de partículas son algoritmos que aproximan las fuerzas de largo alcance entre muchas partículas que interactúan en menos de tiempo cuadrático al agrupar partículas distantes o resolver el campo en una cuadrícula.
Scope
Este tema cubre algoritmos escalables para interacciones de partículas de largo alcance: códigos de árbol jerárquicos como Barnes-Hut, el método multipolar rápido y esquemas de malla de partículas basados en cuadrículas y de partícula-partícula-malla de partículas. Aborda las compensaciones entre precisión y costo y el papel de estos métodos en grandes simulaciones gravitacionales y electrostáticas.
Core questions
- ¿Por qué la suma directa de fuerzas de largo alcance por pares es prohibitivamente costosa?
- ¿Cómo agrupan los códigos de árbol las partículas distantes para reducir el costo del cálculo de la fuerza?
- ¿Cómo logra el método multipolar rápido una escala casi lineal con un error controlado?
- ¿Cómo resuelven los métodos de malla de partículas el campo en una cuadrícula para manejar fuerzas de largo alcance?
Key theories
- Códigos de árbol jerárquicos
- El algoritmo de Barnes-Hut agrupa partículas distantes en celdas cuya fuerza colectiva se aproxima por su centro de masa, reduciendo el costo de la evaluación de la fuerza de cuadrático a un orden de N log N.
- Método multipolar rápido
- El método multipolar rápido representa grupos de partículas mediante expansiones multipolares truncadas y las traduce jerárquicamente, logrando una escala casi lineal con una precisión rigurosamente controlable.
- Métodos de malla de partículas
- Los esquemas de malla de partículas y de partícula-partícula-malla de partículas interpolan cargas o masas en una cuadrícula, resuelven el campo con transformadas rápidas de Fourier y añaden correcciones de corto alcance, manejando eficientemente las interacciones de largo alcance.
Clinical relevance
Estos métodos impulsan las simulaciones cosmológicas y galácticas N-cuerpos de formación de estructuras, las simulaciones de plasma y la electrostática de largo alcance de grandes sistemas moleculares, y el método multipolar rápido es reconocido como uno de los algoritmos más importantes del siglo XX.
History
Los métodos de malla de partículas fueron sistematizados por Hockney y Eastwood en la década de 1980; el código de árbol Barnes-Hut de 1986 y el método multipolar rápido de Greengard y Rokhlin de 1987 transformaron la simulación N-cuerpos, permitiendo las grandes simulaciones cosmológicas y moleculares que siguieron.
Key figures
- Josh Barnes
- Piet Hut
- Leslie Greengard
- Vladimir Rokhlin
Related topics
Seminal works
- barneshut1986
- greengard1987
Frequently asked questions
- ¿Por qué no simplemente calcular cada fuerza por pares directamente?
- Los costos de la suma directa crecen como el cuadrado del número de partículas, por lo que duplicar las partículas cuadruplica el trabajo, lo que se vuelve imposible para los millones o miles de millones de partículas en simulaciones cosmológicas y moleculares grandes. Los métodos rápidos reducen esto a un costo casi lineal.
- ¿Cómo controlan su error los métodos de árbol y multipolares?
- Estos métodos aproximan la influencia de grupos distantes de partículas, y la aproximación se refina incluyendo más términos multipolares o utilizando un criterio de apertura más estricto, de modo que la precisión se puede intercambiar por velocidad de manera controlada.