روش‌های N-جسمی و ذره-شبکه

محاسبه نیروهای گرانشی یا الکترواستاتیکی متقابل بین ذرات متعدد به روش ساده، مربعی از تعداد آنها هزینه دارد، و روش‌های سریع N-جسمی و ذره-شبکه این هزینه را به نزدیک خطی کاهش می‌دهند، که شبیه‌سازی‌های میلیون ذره‌ای کهکشان‌ها و پلاسماها را ممکن می‌سازد.

Definition

روش‌های N-جسمی و ذره-شبکه الگوریتم‌هایی هستند که نیروهای دوربرد بین بسیاری از ذرات متقابل را در زمانی کمتر از زمان درجه دوم با گروه‌بندی ذرات دور یا حل میدان روی یک شبکه، تخمین می‌زنند.

Scope

این موضوع الگوریتم‌های مقیاس‌پذیر برای تعاملات ذرات دوربرد را پوشش می‌دهد: کدهای درختی سلسله‌مراتبی مانند بارنز-هات، روش چندقطبی سریع، و طرح‌های ذره-شبکه و ذره-ذره ذره-شبکه مبتنی بر شبکه. این موضوع به مبادلات دقت در مقابل هزینه و نقش این روش‌ها در شبیه‌سازی‌های گرانشی و الکترواستاتیکی بزرگ می‌پردازد.

Core questions

• چرا جمع مستقیم نیروهای دوربرد زوجی به طور غیرقابل قبولی پرهزینه است؟
• کدهای درختی چگونه ذرات دور را گروه‌بندی می‌کنند تا هزینه محاسبه نیرو را کاهش دهند؟
• روش چندقطبی سریع چگونه به مقیاس‌پذیری نزدیک خطی با خطای کنترل‌شده دست می‌یابد؟
• روش‌های ذره-شبکه چگونه میدان را روی یک شبکه حل می‌کنند تا نیروهای دوربرد را مدیریت کنند؟

Key theories

کدهای درختی سلسله‌مراتبی

الگوریتم بارنز-هات ذرات دور را در سلول‌هایی گروه‌بندی می‌کند که نیروی جمعی آنها با مرکز جرمشان تخمین زده می‌شود، و هزینه ارزیابی نیرو را از درجه دوم به مرتبه N log N کاهش می‌دهد.

روش چندقطبی سریع

روش چندقطبی سریع گروه‌هایی از ذرات را با بسط‌های چندقطبی کوتاه شده نمایش می‌دهد و آنها را به صورت سلسله‌مراتبی ترجمه می‌کند، و به مقیاس‌پذیری نزدیک خطی با دقت قابل کنترل دقیق دست می‌یابد.

روش‌های ذره-شبکه

طرح‌های ذره-شبکه و ذره-ذره ذره-شبکه بارها یا جرم‌ها را روی یک شبکه درون‌یابی می‌کنند، میدان را با تبدیل فوریه سریع حل می‌کنند، و اصلاحات کوتاه‌برد را اضافه می‌کنند، و به طور کارآمد تعاملات دوربرد را مدیریت می‌کنند.

Clinical relevance

این روش‌ها شبیه‌سازی‌های N-جسمی کیهان‌شناسی و کهکشانی شکل‌گیری ساختار، شبیه‌سازی‌های پلاسما، و الکترواستاتیک دوربرد سیستم‌های مولکولی بزرگ را هدایت می‌کنند، و روش چندقطبی سریع به عنوان یکی از مهم‌ترین الگوریتم‌های قرن بیستم شناخته شده است.

History

روش‌های ذره-شبکه توسط هاکنی و ایستوود در دهه 1980 سیستماتیک شدند؛ کد درختی بارنز-هات در سال 1986 و روش چندقطبی سریع گرینگارد و روخلین در سال 1987 شبیه‌سازی N-جسمی را متحول کردند و شبیه‌سازی‌های کیهان‌شناسی و مولکولی بزرگی را که پس از آن انجام شد، ممکن ساختند.

Key figures

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

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

چرا فقط هر نیروی زوجی را مستقیماً محاسبه نکنیم؟

هزینه‌های جمع مستقیم با مربع تعداد ذرات رشد می‌کند، بنابراین دو برابر کردن ذرات، کار را چهار برابر می‌کند، که برای میلیون‌ها یا میلیاردها ذره در شبیه‌سازی‌های کیهان‌شناسی و مولکولی بزرگ غیرممکن می‌شود. روش‌های سریع این هزینه را به نزدیک خطی کاهش می‌دهند.

روش‌های درختی و چندقطبی چگونه خطای خود را کنترل می‌کنند؟

آنها تأثیر گروه‌های دور از ذرات را تخمین می‌زنند، و این تخمین با گنجاندن جملات چندقطبی بیشتر یا استفاده از یک معیار باز شدن سخت‌گیرانه‌تر اصلاح می‌شود، بنابراین دقت را می‌توان به صورت کنترل‌شده با سرعت مبادله کرد.