तेज़ बहुध्रुव विधि: Difference between revisions
From Vigyanwiki
(Created page with "__NOTOC__ फास्ट मल्टीपोल विधि (एफएमएम) एक संख्यात्मक विश्लेषण तकनीक है...") |
No edit summary |
||
| Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
फास्ट मल्टीपोल विधि (एफएमएम) एक [[संख्यात्मक विश्लेषण]] तकनीक है जिसे एन-बॉडी समस्या|''एन''-बॉडी समस्या में लंबी दूरी की ताकतों की गणना में तेजी लाने के लिए विकसित किया गया था। यह सिस्टम ग्रीन के फ़ंक्शन (कई-निकाय सिद्धांत) का विस्तार करके ऐसा करता है। [[मल्टीपोल विस्तार]] का उपयोग करके ग्रीन का फ़ंक्शन, जो किसी को उन स्रोतों को समूहित करने की अनुमति देता है जो एक साथ पास होते हैं और उनके साथ ऐसा व्यवहार करते हैं जैसे कि वे एक ही स्रोत हों।<ref>Rokhlin, Vladimir (1985). "[https://www.sciencedirect.com/science/article/pii/0021999185900026 Rapid Solution of Integral Equations of Classic Potential Theory]." J. Computational Physics Vol. 60, pp. 187–207.</ref> | फास्ट मल्टीपोल विधि (एफएमएम) एक [[संख्यात्मक विश्लेषण]] तकनीक है जिसे एन-बॉडी समस्या|''एन''-बॉडी समस्या में लंबी दूरी की ताकतों की गणना में तेजी लाने के लिए विकसित किया गया था। यह सिस्टम ग्रीन के फ़ंक्शन (कई-निकाय सिद्धांत) का विस्तार करके ऐसा करता है। [[मल्टीपोल विस्तार]] का उपयोग करके ग्रीन का फ़ंक्शन, जो किसी को उन स्रोतों को समूहित करने की अनुमति देता है जो एक साथ पास होते हैं और उनके साथ ऐसा व्यवहार करते हैं जैसे कि वे एक ही स्रोत हों।<ref>Rokhlin, Vladimir (1985). "[https://www.sciencedirect.com/science/article/pii/0021999185900026 Rapid Solution of Integral Equations of Classic Potential Theory]." J. Computational Physics Vol. 60, pp. 187–207.</ref> | ||
एफएमएम को [[कम्प्यूटेशनल इलेक्ट्रोमैग्नेटिक्स]] समस्याओं पर लागू [[सीमा तत्व विधि]] (एमओएम) में [[पुनरावृत्त सॉल्वर]] को तेज करने में भी लागू किया गया है।<ref>[[Nader Engheta]], William D. Murphy, [[Vladimir Rokhlin (American scientist)|Vladimir Rokhlin]], and [[Marius Vassiliou]] (1992), “The Fast Multipole Method for Electromagnetic Scattering Computation,” IEEE Transactions on Antennas and Propagation 40, 634–641.</ref> एफएमएम को पहली बार [[ लेस्ली ग्रीन्गार्ड ]] और व्लादिमीर रोक्लिन जूनियर द्वारा इस तरह से पेश किया गया था।<ref>{{cite web |url=http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html |title=फास्ट मल्टीपोल विधि|access-date=2010-12-10 |url-status=dead |archive-url=https://web.archive.org/web/20110603231158/http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html |archive-date=2011-06-03 }} <!--link redirects to the members list--></ref> और वेक्टर [[हेल्महोल्ट्ज़ समीकरण]] के बहुध्रुवीय विस्तार पर आधारित है। एफएमएम का उपयोग करके दूर-दूर के आधार कार्यों के बीच बातचीत का इलाज करने से, संबंधित मैट्रिक्स तत्वों को स्पष्ट रूप से संग्रहीत करने की आवश्यकता नहीं होती है, जिसके परिणामस्वरूप आवश्यक मेमोरी में महत्वपूर्ण कमी आती है। यदि एफएमएम को पदानुक्रमित तरीके से लागू किया जाता है, तो यह पुनरावृत्त सॉल्वर में मैट्रिक्स-वेक्टर उत्पादों की जटिलता में सुधार कर सकता है <math>\mathcal{O}(N^2)</math> को <math>\mathcal{O}(N)</math> परिमित अंकगणित में, यानी, एक सहनशीलता दी गई <math>\varepsilon</math>, मैट्रिक्स-वेक्टर उत्पाद को सहनशीलता के भीतर होने की गारंटी है <math>\varepsilon.</math> सहनशीलता पर जटिलता की निर्भरता <math>\varepsilon</math> है <math>\mathcal{O}(\log(1/\varepsilon))</math>, यानी, एफएमएम की जटिलता है <math>\mathcal{O}(N\log(1/\varepsilon))</math>. इसने एमओएम की प्रयोज्यता के क्षेत्र को पहले की तुलना में कहीं अधिक बड़ी समस्याओं तक विस्तारित कर दिया है। | एफएमएम को [[कम्प्यूटेशनल इलेक्ट्रोमैग्नेटिक्स]] समस्याओं पर लागू [[सीमा तत्व विधि]] (एमओएम) में [[पुनरावृत्त सॉल्वर]] को तेज करने में भी लागू किया गया है।<ref>[[Nader Engheta]], William D. Murphy, [[Vladimir Rokhlin (American scientist)|Vladimir Rokhlin]], and [[Marius Vassiliou]] (1992), “The Fast Multipole Method for Electromagnetic Scattering Computation,” IEEE Transactions on Antennas and Propagation 40, 634–641.</ref> एफएमएम को पहली बार [[ लेस्ली ग्रीन्गार्ड |लेस्ली ग्रीन्गार्ड]] और व्लादिमीर रोक्लिन जूनियर द्वारा इस तरह से पेश किया गया था।<ref>{{cite web |url=http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html |title=फास्ट मल्टीपोल विधि|access-date=2010-12-10 |url-status=dead |archive-url=https://web.archive.org/web/20110603231158/http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html |archive-date=2011-06-03 }} <!--link redirects to the members list--></ref> और वेक्टर [[हेल्महोल्ट्ज़ समीकरण]] के बहुध्रुवीय विस्तार पर आधारित है। एफएमएम का उपयोग करके दूर-दूर के आधार कार्यों के बीच बातचीत का इलाज करने से, संबंधित मैट्रिक्स तत्वों को स्पष्ट रूप से संग्रहीत करने की आवश्यकता नहीं होती है, जिसके परिणामस्वरूप आवश्यक मेमोरी में महत्वपूर्ण कमी आती है। यदि एफएमएम को पदानुक्रमित तरीके से लागू किया जाता है, तो यह पुनरावृत्त सॉल्वर में मैट्रिक्स-वेक्टर उत्पादों की जटिलता में सुधार कर सकता है <math>\mathcal{O}(N^2)</math> को <math>\mathcal{O}(N)</math> परिमित अंकगणित में, यानी, एक सहनशीलता दी गई <math>\varepsilon</math>, मैट्रिक्स-वेक्टर उत्पाद को सहनशीलता के भीतर होने की गारंटी है <math>\varepsilon.</math> सहनशीलता पर जटिलता की निर्भरता <math>\varepsilon</math> है <math>\mathcal{O}(\log(1/\varepsilon))</math>, यानी, एफएमएम की जटिलता है <math>\mathcal{O}(N\log(1/\varepsilon))</math>. इसने एमओएम की प्रयोज्यता के क्षेत्र को पहले की तुलना में कहीं अधिक बड़ी समस्याओं तक विस्तारित कर दिया है। | ||
रोक्लिन जूनियर और ग्रीनगार्ड द्वारा प्रस्तुत एफएमएम को 20वीं सदी के शीर्ष दस [[कलन विधि]] में से एक कहा गया है।<ref>{{cite journal |author-first=Barry Arthur |author-last=Cipra |author-link=Barry Arthur Cipra |date=May 16, 2000 |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4 |pages=2 |publisher=[[Society for Industrial and Applied Mathematics]] |url=https://archive.siam.org/news/news.php?id=637 |access-date=February 27, 2019 }}</ref> एफएमएम एल्गोरिदम एक निश्चित प्रकार के घने मैट्रिक्स को शामिल करते हुए मैट्रिक्स-वेक्टर गुणन की जटिलता को कम करता है जो कई भौतिक प्रणालियों से उत्पन्न हो सकता है। | रोक्लिन जूनियर और ग्रीनगार्ड द्वारा प्रस्तुत एफएमएम को 20वीं सदी के शीर्ष दस [[कलन विधि]] में से एक कहा गया है।<ref>{{cite journal |author-first=Barry Arthur |author-last=Cipra |author-link=Barry Arthur Cipra |date=May 16, 2000 |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4 |pages=2 |publisher=[[Society for Industrial and Applied Mathematics]] |url=https://archive.siam.org/news/news.php?id=637 |access-date=February 27, 2019 }}</ref> एफएमएम एल्गोरिदम एक निश्चित प्रकार के घने मैट्रिक्स को शामिल करते हुए मैट्रिक्स-वेक्टर गुणन की जटिलता को कम करता है जो कई भौतिक प्रणालियों से उत्पन्न हो सकता है। | ||
| Line 31: | Line 31: | ||
* [http://www.fastfieldsolvers.com FastFieldSolvers] एम.आई.टी. में विकसित फास्टहेनरी और फास्टकैप नामक उपकरणों के वितरण को बनाए रखता है। मैक्सवेल समीकरणों के समाधान और एफएमएम का उपयोग करके सर्किट परजीवियों (अधिष्ठापन और समाई) के निष्कर्षण के लिए। | * [http://www.fastfieldsolvers.com FastFieldSolvers] एम.आई.टी. में विकसित फास्टहेनरी और फास्टकैप नामक उपकरणों के वितरण को बनाए रखता है। मैक्सवेल समीकरणों के समाधान और एफएमएम का उपयोग करके सर्किट परजीवियों (अधिष्ठापन और समाई) के निष्कर्षण के लिए। | ||
* [https://github.com/exafmm/exaFMM ExaFMM] ExaFMM लाप्लास/हेल्महोल्ट्ज़ कर्नेल के लिए एक CPU/GPU सक्षम 3D FMM कोड है जो समानांतर स्केलेबिलिटी पर केंद्रित है। | * [https://github.com/exafmm/exaFMM ExaFMM] ExaFMM लाप्लास/हेल्महोल्ट्ज़ कर्नेल के लिए एक CPU/GPU सक्षम 3D FMM कोड है जो समानांतर स्केलेबिलिटी पर केंद्रित है। | ||
* [http://calfmm-public.gforge.inria.fr/doc/ ScalFMM] ScalFMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे [[ इन्रिया ]] बोर्डो में विकसित किया गया है, जिसमें सामान्यता और समानांतरीकरण ([[ओपनएमपी]]/[[ संदेश पासिंग इंटरफ़ेस ]] का उपयोग करके) पर अत्यधिक जोर दिया गया है। | * [http://calfmm-public.gforge.inria.fr/doc/ ScalFMM] ScalFMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे [[ इन्रिया |इन्रिया]] बोर्डो में विकसित किया गया है, जिसमें सामान्यता और समानांतरीकरण ([[ओपनएमपी]]/[[ संदेश पासिंग इंटरफ़ेस | संदेश पासिंग इंटरफ़ेस]] का उपयोग करके) पर अत्यधिक जोर दिया गया है। | ||
* [https://jacksondebuhr.github.io/dashmm/ DASHMM] DASHMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे एसिंक्रोनस मल्टी-टास्किंग HPX-5 रनटाइम सिस्टम का उपयोग करके इंडियाना यूनिवर्सिटी में विकसित किया गया है। यह साझा और वितरित मेमोरी कंप्यूटर पर एकीकृत निष्पादन प्रदान करता है और 3डी लाप्लास, युकावा और हेल्महोल्ट्ज़ कर्नेल प्रदान करता है। | * [https://jacksondebuhr.github.io/dashmm/ DASHMM] DASHMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे एसिंक्रोनस मल्टी-टास्किंग HPX-5 रनटाइम सिस्टम का उपयोग करके इंडियाना यूनिवर्सिटी में विकसित किया गया है। यह साझा और वितरित मेमोरी कंप्यूटर पर एकीकृत निष्पादन प्रदान करता है और 3डी लाप्लास, युकावा और हेल्महोल्ट्ज़ कर्नेल प्रदान करता है। | ||
* [https://zhang416.github.io/recfmm/ RECFMM] मल्टीकोर पर गतिशील समानता के साथ अनुकूली एफएमएम। | * [https://zhang416.github.io/recfmm/ RECFMM] मल्टीकोर पर गतिशील समानता के साथ अनुकूली एफएमएम। | ||
Revision as of 22:27, 13 August 2023
फास्ट मल्टीपोल विधि (एफएमएम) एक संख्यात्मक विश्लेषण तकनीक है जिसे एन-बॉडी समस्या|एन-बॉडी समस्या में लंबी दूरी की ताकतों की गणना में तेजी लाने के लिए विकसित किया गया था। यह सिस्टम ग्रीन के फ़ंक्शन (कई-निकाय सिद्धांत) का विस्तार करके ऐसा करता है। मल्टीपोल विस्तार का उपयोग करके ग्रीन का फ़ंक्शन, जो किसी को उन स्रोतों को समूहित करने की अनुमति देता है जो एक साथ पास होते हैं और उनके साथ ऐसा व्यवहार करते हैं जैसे कि वे एक ही स्रोत हों।[1] एफएमएम को कम्प्यूटेशनल इलेक्ट्रोमैग्नेटिक्स समस्याओं पर लागू सीमा तत्व विधि (एमओएम) में पुनरावृत्त सॉल्वर को तेज करने में भी लागू किया गया है।[2] एफएमएम को पहली बार लेस्ली ग्रीन्गार्ड और व्लादिमीर रोक्लिन जूनियर द्वारा इस तरह से पेश किया गया था।[3] और वेक्टर हेल्महोल्ट्ज़ समीकरण के बहुध्रुवीय विस्तार पर आधारित है। एफएमएम का उपयोग करके दूर-दूर के आधार कार्यों के बीच बातचीत का इलाज करने से, संबंधित मैट्रिक्स तत्वों को स्पष्ट रूप से संग्रहीत करने की आवश्यकता नहीं होती है, जिसके परिणामस्वरूप आवश्यक मेमोरी में महत्वपूर्ण कमी आती है। यदि एफएमएम को पदानुक्रमित तरीके से लागू किया जाता है, तो यह पुनरावृत्त सॉल्वर में मैट्रिक्स-वेक्टर उत्पादों की जटिलता में सुधार कर सकता है को परिमित अंकगणित में, यानी, एक सहनशीलता दी गई , मैट्रिक्स-वेक्टर उत्पाद को सहनशीलता के भीतर होने की गारंटी है सहनशीलता पर जटिलता की निर्भरता है , यानी, एफएमएम की जटिलता है . इसने एमओएम की प्रयोज्यता के क्षेत्र को पहले की तुलना में कहीं अधिक बड़ी समस्याओं तक विस्तारित कर दिया है।
रोक्लिन जूनियर और ग्रीनगार्ड द्वारा प्रस्तुत एफएमएम को 20वीं सदी के शीर्ष दस कलन विधि में से एक कहा गया है।[4] एफएमएम एल्गोरिदम एक निश्चित प्रकार के घने मैट्रिक्स को शामिल करते हुए मैट्रिक्स-वेक्टर गुणन की जटिलता को कम करता है जो कई भौतिक प्रणालियों से उत्पन्न हो सकता है।
एफएमएम को हार्ट्री-फॉक विधि में कूलम्ब इंटरैक्शन और क्वांटम रसायन विज्ञान में घनत्व कार्यात्मक सिद्धांत गणनाओं के कुशलतापूर्वक इलाज के लिए भी लागू किया गया है।
यह भी देखें
- बार्न्स-हट अनुकरण
- मल्टीपोल विस्तार
- एन-बॉडी सिमुलेशन|एन-बॉडी सिमुलेशन
संदर्भ
- ↑ Rokhlin, Vladimir (1985). "Rapid Solution of Integral Equations of Classic Potential Theory." J. Computational Physics Vol. 60, pp. 187–207.
- ↑ Nader Engheta, William D. Murphy, Vladimir Rokhlin, and Marius Vassiliou (1992), “The Fast Multipole Method for Electromagnetic Scattering Computation,” IEEE Transactions on Antennas and Propagation 40, 634–641.
- ↑ "फास्ट मल्टीपोल विधि". Archived from the original on 2011-06-03. Retrieved 2010-12-10.
- ↑ Cipra, Barry Arthur (May 16, 2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". SIAM News. Society for Industrial and Applied Mathematics. 33 (4): 2. Retrieved February 27, 2019.
बाहरी संबंध
- Gibson, Walton C. The Method of Moments in Electromagnetics. Chapman & Hall/CRC, 2008. ISBN 978-1-4200-6145-1
- Abstract of Greengard and Rokhlin's original paper
- A short course on fast multipole methods by Rick Beatson and Leslie Greengard.
- JAVA Animation of the Fast Multipole Method Nice animation of the Fast Multipole Method with different adaptations.
मुफ़्त सॉफ़्टवेयर
- Puma-EM एक उच्च प्रदर्शन, समानांतर, ओपन सोर्स मेथड ऑफ मोमेंट्स / मल्टीलेवल फास्ट मल्टीपोल मेथड इलेक्ट्रोमैग्नेटिक्स कोड।
- KIFMM3d कर्नेल-इंडिपेंडेंट फास्ट मल्टीपोल 3डी मेथड (kifmm3d) एक नया एफएमएम कार्यान्वयन है जिसमें अंतर्निहित कर्नेल के स्पष्ट मल्टीपोल विस्तार की आवश्यकता नहीं होती है। और यह कर्नेल मूल्यांकन पर आधारित है।
- FastBEM 2डी/3डी क्षमता, लोच, स्टोक्स प्रवाह और ध्वनिक समस्याओं को हल करने के लिए मुफ्त तेज मल्टीपोल सीमा तत्व कार्यक्रम।
- FastFieldSolvers एम.आई.टी. में विकसित फास्टहेनरी और फास्टकैप नामक उपकरणों के वितरण को बनाए रखता है। मैक्सवेल समीकरणों के समाधान और एफएमएम का उपयोग करके सर्किट परजीवियों (अधिष्ठापन और समाई) के निष्कर्षण के लिए।
- ExaFMM ExaFMM लाप्लास/हेल्महोल्ट्ज़ कर्नेल के लिए एक CPU/GPU सक्षम 3D FMM कोड है जो समानांतर स्केलेबिलिटी पर केंद्रित है।
- ScalFMM ScalFMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे इन्रिया बोर्डो में विकसित किया गया है, जिसमें सामान्यता और समानांतरीकरण (ओपनएमपी/ संदेश पासिंग इंटरफ़ेस का उपयोग करके) पर अत्यधिक जोर दिया गया है।
- DASHMM DASHMM एक C++ सॉफ्टवेयर लाइब्रेरी है जिसे एसिंक्रोनस मल्टी-टास्किंग HPX-5 रनटाइम सिस्टम का उपयोग करके इंडियाना यूनिवर्सिटी में विकसित किया गया है। यह साझा और वितरित मेमोरी कंप्यूटर पर एकीकृत निष्पादन प्रदान करता है और 3डी लाप्लास, युकावा और हेल्महोल्ट्ज़ कर्नेल प्रदान करता है।
- RECFMM मल्टीकोर पर गतिशील समानता के साथ अनुकूली एफएमएम।
श्रेणी:संख्यात्मक विश्लेषण श्रेणी:संख्यात्मक अंतर समीकरण श्रेणी:कम्प्यूटेशनल विज्ञान
