एन-बॉडी और पार्टिकल-मेश विधियाँ
कई कणों के बीच पारस्परिक गुरुत्वाकर्षण या इलेक्ट्रोस्टैटिक बलों की गणना करने में स्वाभाविक रूप से उनकी संख्या का वर्ग खर्च होता है, और तेज़ एन-बॉडी और पार्टिकल-मेश विधियाँ इसे लगभग रैखिक तक कम कर देती हैं, जिससे आकाशगंगाओं और प्लाज्मा के दस लाख-कण सिमुलेशन संभव हो पाते हैं।
Definition
एन-बॉडी और पार्टिकल-मेश विधियाँ ऐसे एल्गोरिदम हैं जो दूर के कणों को समूहित करके या ग्रिड पर क्षेत्र को हल करके कई अंतःक्रियात्मक कणों के बीच लंबी दूरी की ताकतों को द्विघात समय से कम में अनुमानित करते हैं।
Scope
यह विषय लंबी दूरी की कण अंतःक्रियाओं के लिए स्केलेबल एल्गोरिदम को शामिल करता है: बार्न्स-हट जैसे पदानुक्रमित ट्री कोड, फास्ट मल्टीपोल विधि, और ग्रिड-आधारित पार्टिकल-मेश और पार्टिकल-पार्टिकल पार्टिकल-मेश योजनाएँ। यह सटीकता-बनाम-लागत के व्यापार-बंद और बड़े गुरुत्वाकर्षण और इलेक्ट्रोस्टैटिक सिमुलेशन में इन विधियों की भूमिका पर प्रकाश डालता है।
Core questions
- जोड़ीदार लंबी दूरी की ताकतों का सीधा योग निषिद्ध रूप से महंगा क्यों है?
- ट्री कोड दूर के कणों को बल-गणना लागत को कम करने के लिए कैसे समूहित करते हैं?
- फास्ट मल्टीपोल विधि नियंत्रित त्रुटि के साथ लगभग-रैखिक स्केलिंग कैसे प्राप्त करती है?
- पार्टिकल-मेश विधियाँ लंबी दूरी की ताकतों को संभालने के लिए ग्रिड पर क्षेत्र को कैसे हल करती हैं?
Key theories
- पदानुक्रमित ट्री कोड
- बार्न्स-हट एल्गोरिथम दूर के कणों को कोशिकाओं में समूहित करता है जिनकी सामूहिक शक्ति उनके द्रव्यमान के केंद्र द्वारा अनुमानित की जाती है, जिससे बल मूल्यांकन की लागत द्विघात से N log N के क्रम तक कम हो जाती है।
- फास्ट मल्टीपोल विधि
- फास्ट मल्टीपोल विधि कणों के समूहों को खंडित मल्टीपोल विस्तारों द्वारा दर्शाती है और उन्हें पदानुक्रमित रूप से अनुवादित करती है, जिससे कठोरता से नियंत्रणीय सटीकता के साथ लगभग-रैखिक स्केलिंग प्राप्त होती है।
- पार्टिकल-मेश विधियाँ
- पार्टिकल-मेश और पार्टिकल-पार्टिकल पार्टिकल-मेश योजनाएँ आवेशों या द्रव्यमानों को एक ग्रिड पर इंटरपोलेट करती हैं, फास्ट फूरियर ट्रांसफॉर्म के साथ क्षेत्र को हल करती हैं, और छोटी दूरी के सुधार जोड़ती हैं, जिससे लंबी दूरी की अंतःक्रियाओं को कुशलता से संभाला जाता है।
Clinical relevance
ये विधियाँ संरचना निर्माण के ब्रह्मांडीय और गांगेय एन-बॉडी सिमुलेशन, प्लाज्मा सिमुलेशन, और बड़े आणविक प्रणालियों के लंबी दूरी के इलेक्ट्रोस्टैटिक्स को संचालित करती हैं, और फास्ट मल्टीपोल विधि को बीसवीं शताब्दी के सबसे महत्वपूर्ण एल्गोरिदम में से एक के रूप में मान्यता प्राप्त है।
History
पार्टिकल-मेश विधियों को 1980 के दशक में हॉकनी और ईस्टवुड द्वारा व्यवस्थित किया गया था; 1986 का बार्न्स-हट ट्री कोड और ग्रींगार्ड और रोखलिन की 1987 की फास्ट मल्टीपोल विधि ने एन-बॉडी सिमुलेशन को बदल दिया, जिससे बाद में बड़े ब्रह्मांडीय और आणविक सिमुलेशन संभव हो पाए।
Key figures
- Josh Barnes
- Piet Hut
- Leslie Greengard
- Vladimir Rokhlin
Related topics
Seminal works
- barneshut1986
- greengard1987
Frequently asked questions
- प्रत्येक जोड़ीदार बल की सीधे गणना क्यों नहीं की जाती?
- प्रत्यक्ष योग की लागत कण संख्या के वर्ग के रूप में बढ़ती है, इसलिए कणों को दोगुना करने से काम चौगुना हो जाता है, जो ब्रह्मांडीय और बड़े आणविक सिमुलेशन में लाखों या अरबों कणों के लिए असंभव हो जाता है। तेज़ विधियाँ इसे लगभग-रैखिक लागत तक कम कर देती हैं।
- ट्री और मल्टीपोल विधियाँ अपनी त्रुटि को कैसे नियंत्रित करती हैं?
- वे कणों के दूर के समूहों के प्रभाव का अनुमान लगाती हैं, और अनुमान को अधिक मल्टीपोल शब्दों को शामिल करके या एक सख्त उद्घाटन मानदंड का उपयोग करके परिष्कृत किया जाता है, ताकि सटीकता को नियंत्रित तरीके से गति के साथ बदला जा सके।