طرق N-Body والشبكة الجزيئية

تكلف الحسابات المباشرة للقوى التجاذبية أو الكهروستاتيكية المتبادلة بين العديد من الجسيمات مربع عددها، بينما تعمل طرق N-body والشبكة الجزيئية السريعة على تقليل هذه التكلفة إلى ما يقرب من التكلفة الخطية، مما يجعل محاكاة المجرات والبلازما التي تحتوي على ملايين الجسيمات ممكنة.

Definition

طرق N-body والشبكة الجزيئية هي خوارزميات تقريبية للقوى بعيدة المدى بين العديد من الجسيمات المتفاعلة في وقت أقل من التربيعي عن طريق تجميع الجسيمات البعيدة أو حل المجال على شبكة.

Scope

يغطي هذا الموضوع الخوارزميات القابلة للتطوير لتفاعلات الجسيمات بعيدة المدى: رموز الشجرة الهرمية مثل بارنز-هوت (Barnes-Hut)، وطريقة الأقطاب المتعددة السريعة (fast multipole method)، ومخططات الشبكة الجزيئية القائمة على الشبكة (grid-based particle-mesh) والجسيم-جسيم الشبكة الجزيئية (particle-particle particle-mesh). ويتناول المفاضلات بين الدقة والتكلفة ودور هذه الطرق في المحاكاة التجاذبية والكهروستاتيكية الكبيرة.

Core questions

• لماذا يعتبر الجمع المباشر للقوى الثنائية بعيدة المدى باهظ التكلفة بشكل غير مقبول؟
• كيف تقوم رموز الشجرة بتجميع الجسيمات البعيدة لتقليل تكلفة حساب القوة؟
• كيف تحقق طريقة الأقطاب المتعددة السريعة قياسًا شبه خطي مع خطأ متحكم فيه؟
• كيف تحل طرق الشبكة الجزيئية المجال على شبكة للتعامل مع القوى بعيدة المدى؟

Key theories

رموز الشجرة الهرمية

تقوم خوارزمية بارنز-هوت بتجميع الجسيمات البعيدة في خلايا يتم تقريب قوتها الكلية بواسطة مركز كتلتها، مما يقلل تكلفة تقييم القوة من التربيعي إلى ترتيب N log N.

طريقة الأقطاب المتعددة السريعة

تمثل طريقة الأقطاب المتعددة السريعة مجموعات الجسيمات عن طريق توسعات متعددة الأقطاب مبتورة وتقوم بترجمتها هرميًا، مما يحقق قياسًا شبه خطي بدقة يمكن التحكم فيها بشكل صارم.

طرق الشبكة الجزيئية

تقوم مخططات الشبكة الجزيئية والجسيم-جسيم الشبكة الجزيئية باستيفاء الشحنات أو الكتل على شبكة، وتحل المجال باستخدام تحويلات فورييه السريعة، وتضيف تصحيحات قصيرة المدى، مما يتعامل بكفاءة مع التفاعلات بعيدة المدى.

Clinical relevance

تدفع هذه الطرق محاكاة N-body الكونية والمجرية لتكوين البنية، ومحاكاة البلازما، والكهروديناميكا بعيدة المدى للأنظمة الجزيئية الكبيرة، وتُعرف طريقة الأقطاب المتعددة السريعة بأنها واحدة من أهم خوارزميات القرن العشرين.

History

تم تنظيم طرق الشبكة الجزيئية بواسطة هوكني وإيستوود في الثمانينيات؛ وقد أحدث رمز شجرة بارنز-هوت عام 1986 وطريقة الأقطاب المتعددة السريعة لغرينغارد وروكلين عام 1987 تحولًا في محاكاة N-body، مما أتاح المحاكاة الكونية والجزيئية الكبيرة التي تلت ذلك.

Key figures

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

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

لماذا لا يتم حساب كل قوة ثنائية مباشرة؟

تنمو تكاليف الجمع المباشر كمربع عدد الجسيمات، لذا فإن مضاعفة الجسيمات تضاعف العمل أربع مرات، مما يصبح مستحيلًا لملايين أو مليارات الجسيمات في المحاكاة الكونية والجزيئية الكبيرة. تقلل الطرق السريعة هذه التكلفة إلى ما يقرب من التكلفة الخطية.

كيف تتحكم طرق الشجرة والأقطاب المتعددة في خطأها؟

إنها تقرب تأثير مجموعات الجسيمات البعيدة، ويتم تحسين التقريب عن طريق تضمين المزيد من حدود الأقطاب المتعددة أو استخدام معيار فتح أكثر صرامة، بحيث يمكن الموازنة بين الدقة والسرعة بطريقة محكمة.