N체 및 입자-메시 방법

수많은 입자들 사이의 상호 중력 또는 정전기력을 계산하는 데에는 입자 수의 제곱에 비례하는 비용이 발생하지만, 빠른 N체 및 입자-메시 방법은 이를 거의 선형적인 수준으로 줄여 수백만 개의 입자를 포함하는 은하 및 플라즈마 시뮬레이션을 가능하게 합니다.

Definition

N체 및 입자-메시 방법은 멀리 떨어진 입자들을 그룹화하거나 그리드 상에서 장을 해결함으로써, 상호작용하는 많은 입자들 사이의 장거리 힘을 이차 시간 미만으로 근사하는 알고리즘입니다.

Scope

이 주제는 장거리 입자 상호작용을 위한 확장 가능한 알고리즘을 다룹니다: Barnes-Hut과 같은 계층적 트리 코드, 고속 다중극자 방법, 그리고 그리드 기반 입자-메시 및 입자-입자 입자-메시 방식. 또한 정확도와 비용 간의 상충 관계 및 대규모 중력 및 정전기 시뮬레이션에서 이러한 방법들의 역할에 대해 다룹니다.

Core questions

• 쌍별 장거리 힘의 직접 합산이 엄청나게 비효율적인 이유는 무엇입니까?
• 트리 코드는 멀리 떨어진 입자들을 어떻게 그룹화하여 힘 계산 비용을 줄입니까?
• 고속 다중극자 방법은 제어된 오차로 거의 선형적인 스케일링을 어떻게 달성합니까?
• 입자-메시 방법은 장거리 힘을 처리하기 위해 그리드 상에서 장을 어떻게 해결합니까?

Key theories

계층적 트리 코드

Barnes-Hut 알고리즘은 멀리 떨어진 입자들을 집단적인 힘이 질량 중심으로 근사되는 셀로 그룹화하여, 힘 평가 비용을 이차에서 N log N 차수로 줄입니다.

고속 다중극자 방법

고속 다중극자 방법은 입자 그룹을 절단된 다중극자 전개로 표현하고 이를 계층적으로 변환하여, 엄격하게 제어 가능한 정확도로 거의 선형적인 스케일링을 달성합니다.

입자-메시 방법

입자-메시 및 입자-입자 입자-메시 방식은 전하 또는 질량을 그리드에 보간하고, 고속 푸리에 변환으로 장을 해결하며, 단거리 보정을 추가하여 장거리 상호작용을 효율적으로 처리합니다.

Clinical relevance

이러한 방법들은 구조 형성의 우주론적 및 은하 N체 시뮬레이션, 플라즈마 시뮬레이션, 그리고 대규모 분자 시스템의 장거리 정전기학을 구동하며, 고속 다중극자 방법은 20세기 가장 중요한 알고리즘 중 하나로 인정받고 있습니다.

History

입자-메시 방법은 1980년대 Hockney와 Eastwood에 의해 체계화되었습니다. 1986년 Barnes-Hut 트리 코드와 1987년 Greengard와 Rokhlin의 고속 다중극자 방법은 N체 시뮬레이션을 변화시켰고, 이후 대규모 우주론 및 분자 시뮬레이션을 가능하게 했습니다.

Key figures

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

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

모든 쌍별 힘을 직접 계산하면 안 되는 이유는 무엇입니까?

직접 합산 비용은 입자 수의 제곱에 비례하여 증가하므로, 입자 수를 두 배로 늘리면 작업량이 네 배가 되어 우주론 및 대규모 분자 시뮬레이션의 수백만 또는 수십억 개의 입자에는 불가능해집니다. 빠른 방법은 이 비용을 거의 선형적인 수준으로 줄입니다.

트리 및 다중극자 방법은 오차를 어떻게 제어합니까?

이 방법들은 멀리 떨어진 입자 그룹의 영향을 근사하며, 근사는 더 많은 다중극자 항을 포함하거나 더 엄격한 개방 기준을 사용하여 정제되므로, 정확도와 속도를 제어된 방식으로 교환할 수 있습니다.