पैरारियल

पैरारियल संख्यात्मक विश्लेषण से एक समानांतर एल्गोरिदम है और प्रारंभिक मूल्य समस्याओं के समाधान के लिए उपयोग किया जाता है।

इसे 2001 में जैक्स-लुई लायंस, मैडे और टुरिनिसी द्वारा प्रस्तुत किया गया था। तब से यह समय एकीकरण में सबसे व्यापक रूप से अध्ययन किए जाने वाले समानांतर प्रणालियों में से एक बन गया है।

File:Parareal.svg

पैरारियल में पहले पुनरावृत्ति का चित्रण (मूल संस्करण से अनुकूलित)).

समय में समानांतर एकीकरण विधियां

उदाहरण के विपरीत रंज-कुट्टा या मल्टी-स्टेप विधियां, पैरारियल में कुछ गणनाएं समानांतर कंप्यूटिंग में की जा सकती हैं और इसलिए पैरारियल समय एकीकरण विधि में समानांतर का एक उदाहरण है। जबकि ऐतिहासिक रूप से आंशिक अंतर समीकरणों के संख्यात्मक आंशिक अंतर समीकरणों को समानांतर करने के अधिकांश प्रयास स्थानिक विवेकीकरण पर केंद्रित हैं, एक्सास्केल कंप्यूटिंग की चुनौतियों को देखते हुए, अस्थायी विवेकीकरण के समानांतर प्रणालियों को संख्यात्मक विश्लेषण सॉफ्टवेयर की सूची में समरूपता बढ़ाने के संभावित विधि के रूप में पहचाना गया है।

क्योंकि पैरारियल समानांतर में कई समय चरणों के लिए संख्यात्मक समाधान की गणना करता है, इसे चरणों में समानांतर विधि के रूप में वर्गीकृत किया गया है।

यह समानांतर रंज-कुट्टा या एक्सट्रपलेशन विधियों जैसी विधि में समानता का उपयोग करने वाले दृष्टिकोणों के विपरीत है, जहां स्वतंत्र चरणों की गणना तरंग रूप विश्राम जैसी सिस्टम विधियों में समानांतर या समानांतर में की जा सकती है।

इतिहास

पैरारियल को समय विधि में मल्टीग्रिड विधि या समय अक्ष के साथ प्रत्यक्ष एकाधिक शूटिंग विधि दोनों के रूप में प्राप्त किया जा सकता है।

समय में मल्टीग्रिड के साथ-साथ समय एकीकरण के लिए मल्टीपल शूटिंग को अपनाने के दोनों विचार 1980 और 1990 के दशक से चले आ रहे हैं।

पैरारियल व्यापक रूप से अध्ययन की जाने वाली विधि है और विभिन्न अनुप्रयोगों के लिए इसका उपयोग और संशोधन किया गया है।

प्रारंभिक मूल्य समस्याओं के समाधान को समानांतर करने के विचार और भी प्राचीन हैं: समय में समानांतर एकीकरण विधि का प्रस्ताव करने वाला पहला पेपर 1964 में सामने आया था।

एल्गोरिथम

समस्या

लक्ष्य प्रपत्र की प्रारंभिक मूल्य समस्या का समाधान करना है

${\frac {\mathrm {d} u}{\mathrm {d} t}}=f(t,u)\quad {\text{over}}\quad t\in [t_{0},T]\quad {\text{with}}\quad u(t_{0})=u^{0}.$

दाहिने हाथ की ओर $f$ को एक सुचारू (संभवतः अरेखीय) फलन माना जाता है। यह रेखा दृष्टिकोण की विधि में आंशिक अंतर समीकरण के स्थानिक विवेक के अनुरूप भी हो सकता है। हम इस समस्या को समान दूरी वाले बिंदु $(t_{0},t_{1},\ldots ,t_{N})$, जहां $t_{j+1}=t_{j}+\Delta T$ और $\Delta T=(T-t_{0})/N$, $N+1$ के अस्थायी आधार पर समाधान करना चाहते हैं। इस विवेक को आगे बढ़ाते हुए हमें एक विभाजित समय अंतराल प्राप्त होता है जिसमें $j=0,\ldots ,N-1$ के लिए समय स्लाइस $[t_{j},t_{j+1}]$ सम्मिलित होता है।

इसका उद्देश्य सीरियल टाइम-स्टेपिंग विधि (जैसे रनगे-कुट्टा) का उपयोग करके त्रुटिहीन समाधान $u(t_{j})$ के लिए संख्यात्मक अनुमान $U_{j}$ की गणना करना है जिसमें उच्च संख्यात्मक शुद्धता (और इसलिए उच्च कम्प्यूटेशनल लागत) है। हम इस विधि को फाइन सॉल्वर ${\mathcal {F}}$ के रूप में संदर्भित करते हैं, जो समय $t_{j}$ पर प्रारंभिक मान $U_{j}$ को समय $t_{j+1}$ पर टर्मिनल मान $U_{j+1}$ तक प्रसारित करता है। लक्ष्य ${\mathcal {F}}$ का उपयोग करके समाधान (उच्च संख्यात्मक शुद्धता के साथ) की गणना करना है, जो हमें प्राप्त होता है

$U_{j+1}={\mathcal {F}}(t_{j},t_{j+1},U_{j}),\quad {\text{where}}\quad U_{0}=u^{0}.$

इस (और सबसे पहले समानांतर में समाधान करने का प्रयास करने का कारण) समाधान के साथ समस्या यह है कि वास्तविक समय में गणना करना कम्प्यूटेशनल रूप से संभव नहीं है।

यह कैसे काम करता है

प्रारंभिक मूल्य समस्या का समाधान करने के लिए एकल प्रोसेसर का उपयोग करने के अतिरिक्त (जैसा कि पारंपरिक समय-चरण विधियों के साथ किया जाता है), पैरारियल $N$ प्रोसेसर का उपयोग करता है। इसका उद्देश्य समानांतर में $N$ छोटी प्रारंभिक मूल्य समस्याओं (प्रत्येक समय स्लाइस पर एक) का समाधान करने के लिए $N$ प्रोसेसर का उपयोग करना है। उदाहरण के लिए, संदेश पासिंग इंटरफ़ेस आधारित कोड में, $N$ प्रक्रियाओं की संख्या होगी, जबकि ओपनएमपी आधारित कोड में, $N$ थ्रेड (कंप्यूटिंग) की संख्या के बराबर होगी।

पैरारियल इस प्रारंभिक मूल्य समस्या को समानांतर में समाधान करने के लिए दूसरी टाइम-स्टेपिंग विधि का उपयोग करता है, जिसे कोर्स सॉल्वर ${\mathcal {G}}$ के रूप में जाना जाता है।

कोर्स सॉल्वर ठीक सॉल्वर की तरह ही काम करता है, लंबाई $\Delta T$ के समय अंतराल पर प्रारंभिक मूल्य का प्रचार करता है, चूंकि यह ${\mathcal {F}}$ (और इसलिए बहुत कम कम्प्यूटेशनल लागत पर) की तुलना में बहुत कम संख्यात्मक शुद्धता पर ऐसा करता है। एक कोर्स सॉल्वर का होना जो कि फाइन सॉल्वर की तुलना में बहुत कम कम्प्यूटेशनल रूप से एक्सपेंसिव है, पैरारियल के साथ समानांतर गति प्राप्त करने की कुंजी है।

अब से, हम समय $t_{j}$ और पुनरावृत्ति $k$ पर पैरारियल समाधान को $U_{j}^{k}$ द्वारा निरूपित करते हैं।

शून्य पुनरावृत्ति

सबसे पहले, समाधान के अनुमानित प्रारंभिक अनुमान की गणना करने के लिए कोर्स सॉल्वर को पूरे समय अंतराल $[t_{0},T]$ पर क्रमिक रूप से चलाएं:

$U_{j+1}^{0}={\mathcal {G}}(t_{j},t_{j+1},U_{j}^{0}),\quad j=0,\ldots ,N-1.$

अनुवर्ती पुनरावृत्तियाँ

इसके बाद, सबसे अद्यतित समाधान मानों से, समानांतर में, प्रत्येक समय स्लाइस पर अच्छे सॉल्वर चलाएं:

$\mathcal{F}$