एफएफटीडब्ल्यू: Difference between revisions
| Line 5: | Line 5: | ||
==लाइब्रेरी== | ==लाइब्रेरी== | ||
एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और एक (छोटे परिवर्तनों में परिवर्तन का एक विशेष अपघटन) चुनकर डेटा को तेजी से परिवर्तित करता है, जिसका अनुमान या उपाय विशेष परिस्थितियों में बेहतर होता है। यह छोटे अभाज्य कारकों के साथ आकार के सरणियों पर सबसे अच्छा काम करता है, जिसमें दो की घातें इष्टतम होती हैं और बड़े अभाज्य सबसे निकृष्ट स्थिति होती हैं (लेकिन फिर भी O(n log n))। समग्र आकारों के परिवर्तनों को छोटे परिवर्तनों में विघटित करने के लिए, यह कौली-टुकी एफएफटी एल्गोरिदम (विभिन्न | एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और एक (छोटे परिवर्तनों में परिवर्तन का एक विशेष अपघटन) चुनकर डेटा को तेजी से परिवर्तित करता है, जिसका अनुमान या उपाय विशेष परिस्थितियों में बेहतर होता है। यह छोटे अभाज्य कारकों के साथ आकार के सरणियों पर सबसे अच्छा काम करता है, जिसमें दो की घातें इष्टतम होती हैं और बड़े अभाज्य सबसे निकृष्ट स्थिति होती हैं (लेकिन फिर भी O(n log n))। समग्र आकारों के परिवर्तनों को छोटे परिवर्तनों में विघटित करने के लिए, यह कौली-टुकी एफएफटी एल्गोरिदम (विभिन्न फैक्टीराइज़ेशन और/या विभिन्न मेमोरी-एक्सेस पैटर्न के अनुरूप) के कई प्रकारों में से चुनता है, जबकि अभाज्य आकारों के लिए यह या तो रेडर या ब्लूस्टीन के एफएफटी एल्गोरिदम का उपयोग करता है।<ref name="Frigo2005"/> एक बार जब परिवर्तन को पर्याप्त रूप से छोटे आकार के उप-रूपांतरणों में विभाजित कर दिया जाता है, तो एफएफटीडब्ल्यू इन छोटे आकारों के लिए हार्ड-कोडेड अनरोल्ड एफएफटी का उपयोग करता है जो कोड जनरेशन द्वारा उत्पादित किए गए थे (संकलन समय पर, रन समय पर नहीं); ये रूटीन विभिन्न प्रकार के एल्गोरिदम का उपयोग करते हैं जिनमें कूली-ट्यूकी वेरिएंट, राडार का एल्गोरिदम और [[प्राइम-फैक्टर एफएफटी एल्गोरिदम]] शामिल हैं।<ref name="Frigo2005"/> | ||
बार-बार होने वाले परिवर्तनों की पर्याप्त संख्या के लिए दिए गए ऐरे साइज और [[प्लेटफ़ॉर्म (कंप्यूटिंग)|प्लेटफ़ॉर्म]] पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को | बार-बार होने वाले परिवर्तनों की पर्याप्त संख्या के लिए दिए गए ऐरे साइज और [[प्लेटफ़ॉर्म (कंप्यूटिंग)|प्लेटफ़ॉर्म]] पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को निष्पादन लाभप्रद है। ये माप, जिन्हें लेखक "ज्ञान" के रूप में संदर्भित करते हैं, को बाद में उपयोग के लिए एक फ़ाइल या स्ट्रिंग में संग्रहीत किया जा सकता है। | ||
एफएफटीडब्ल्यू में एक "गुरु इंटरफ़ेस" है जो "अंतर्निहित एफएफटीडब्ल्यू आर्किटेक्चर में फ्लेक्सिबिलिटी के जितना संभव हो उतना अनावृत करने का उद्देश्य रखता है"। यह, अन्य बातों के अतिरिक्त, एक ही कॉल में बहु-आयामी परिवर्तनों और एकाधिक परिवर्तनों की अनुमति देता है (उदाहरण के लिए, जहां डेटा को मेमोरी में इंटरलीव्ड किया जाता है)। | एफएफटीडब्ल्यू में एक "गुरु इंटरफ़ेस" है जो "अंतर्निहित एफएफटीडब्ल्यू आर्किटेक्चर में फ्लेक्सिबिलिटी के जितना संभव हो उतना अनावृत करने का उद्देश्य रखता है"। यह, अन्य बातों के अतिरिक्त, एक ही कॉल में बहु-आयामी परिवर्तनों और एकाधिक परिवर्तनों की अनुमति देता है (उदाहरण के लिए, जहां डेटा को मेमोरी में इंटरलीव्ड किया जाता है)। | ||
| Line 13: | Line 13: | ||
एफएफटीडब्ल्यू के पास ''आउट-ऑफ़-ऑर्डर ट्रांसफ़ॉर्म'' (मैसेज पासिंग इंटरफ़ेस (एमपीआई) संस्करण का उपयोग करके) के लिए सीमित समर्थन है। डेटा को पुन: व्यवस्थित करने में एक ओवरहेड खर्च होता है, जिससे अनियमित आकार और आयाम के स्थान-परिवर्तनों से बचना असतहीय है। यह अप्रलेखित है कि किस परिवर्तन के लिए यह ओवरहेड महत्वपूर्ण है। | एफएफटीडब्ल्यू के पास ''आउट-ऑफ़-ऑर्डर ट्रांसफ़ॉर्म'' (मैसेज पासिंग इंटरफ़ेस (एमपीआई) संस्करण का उपयोग करके) के लिए सीमित समर्थन है। डेटा को पुन: व्यवस्थित करने में एक ओवरहेड खर्च होता है, जिससे अनियमित आकार और आयाम के स्थान-परिवर्तनों से बचना असतहीय है। यह अप्रलेखित है कि किस परिवर्तन के लिए यह ओवरहेड महत्वपूर्ण है। | ||
एफएफटीडब्ल्यू को [[जीएनयू जनरल पब्लिक लाइसेंस]] के अंतर्गत लाइसेंस प्राप्त है। इसे एमआईटी<ref>{{Cite web | url=http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x | title=View Technologies | MIT Technology Licensing Office}}</ref> द्वारा व्यावसायिक रूप से लाइसेंस प्राप्त है (12,500 डॉलर तक की लागत पर) और इसका उपयोग एफएफटी की गणना के लिए वाणिज्यिक मैटलैब<ref>{{Cite web |title=FFTW - Fastest Fourier Transform in the West {{!}} MIT Technology Licensing Office |url=https://tlo.mit.edu/technologies/fftw-fastest-fourier-transform-west |access-date=2023-02-07 |website=tlo.mit.edu}}</ref> मैट्रिक्स पैकेज में किया जाता है। एफएफटीडब्ल्यू C लैंग्वेज में लिखा गया है, लेकिन [[फोरट्रान]] और [[एडा (प्रोग्रामिंग भाषा)|एडा]] इंटरफ़ेस मौजूद हैं, साथ ही कुछ अन्य भाषाओं के लिए भी इंटरफ़ेस मौजूद हैं। जबकि लाइब्रेरी स्वयं C है, कोड वास्तव में '<code>genfft</code>' नामक प्रोग्राम से उत्पन्न होता है, जो [[OCaml]] में लिखा जाता है।<ref name="FFTW FAQ">[http://www.fftw.org/faq/section2.html#languages "FFTW FAQ"]</ref> | |||
1999 में, एफएफटीडब्ल्यू ने न्यूमेरिकल सॉफ्टवेयर के लिए जे. एच. विल्किंसन पुरस्कार जीता। | 1999 में, एफएफटीडब्ल्यू ने न्यूमेरिकल सॉफ्टवेयर के लिए जे. एच. विल्किंसन पुरस्कार जीता। | ||
Revision as of 19:08, 30 July 2023
फास्टेस्ट फूरियर ट्रांसफॉर्म इन द वेस्ट (एफएफटीडब्ल्यू) मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में माटेओ फ्रिगो और स्टीवन जी. जॉनसन द्वारा विकसित असतत फूरियर ट्रांसफॉर्म (डीएफटी) की गणना के लिए एक सॉफ्टवेयर लाइब्रेरी है।[1][2][3]
एफएफटीडब्ल्यू फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) के सबसे नवीनतम मुक्त सॉफ्टवेयर कार्यान्वयनों में से एक है। यह अनियमित आकार और आयाम के वास्तविक और जटिल-मूल्यवान सरणियों के लिए एफएफटी एल्गोरिथ्म को प्रयुक्त करता है।
लाइब्रेरी
एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और एक (छोटे परिवर्तनों में परिवर्तन का एक विशेष अपघटन) चुनकर डेटा को तेजी से परिवर्तित करता है, जिसका अनुमान या उपाय विशेष परिस्थितियों में बेहतर होता है। यह छोटे अभाज्य कारकों के साथ आकार के सरणियों पर सबसे अच्छा काम करता है, जिसमें दो की घातें इष्टतम होती हैं और बड़े अभाज्य सबसे निकृष्ट स्थिति होती हैं (लेकिन फिर भी O(n log n))। समग्र आकारों के परिवर्तनों को छोटे परिवर्तनों में विघटित करने के लिए, यह कौली-टुकी एफएफटी एल्गोरिदम (विभिन्न फैक्टीराइज़ेशन और/या विभिन्न मेमोरी-एक्सेस पैटर्न के अनुरूप) के कई प्रकारों में से चुनता है, जबकि अभाज्य आकारों के लिए यह या तो रेडर या ब्लूस्टीन के एफएफटी एल्गोरिदम का उपयोग करता है।[1] एक बार जब परिवर्तन को पर्याप्त रूप से छोटे आकार के उप-रूपांतरणों में विभाजित कर दिया जाता है, तो एफएफटीडब्ल्यू इन छोटे आकारों के लिए हार्ड-कोडेड अनरोल्ड एफएफटी का उपयोग करता है जो कोड जनरेशन द्वारा उत्पादित किए गए थे (संकलन समय पर, रन समय पर नहीं); ये रूटीन विभिन्न प्रकार के एल्गोरिदम का उपयोग करते हैं जिनमें कूली-ट्यूकी वेरिएंट, राडार का एल्गोरिदम और प्राइम-फैक्टर एफएफटी एल्गोरिदम शामिल हैं।[1]
बार-बार होने वाले परिवर्तनों की पर्याप्त संख्या के लिए दिए गए ऐरे साइज और प्लेटफ़ॉर्म पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को निष्पादन लाभप्रद है। ये माप, जिन्हें लेखक "ज्ञान" के रूप में संदर्भित करते हैं, को बाद में उपयोग के लिए एक फ़ाइल या स्ट्रिंग में संग्रहीत किया जा सकता है।
एफएफटीडब्ल्यू में एक "गुरु इंटरफ़ेस" है जो "अंतर्निहित एफएफटीडब्ल्यू आर्किटेक्चर में फ्लेक्सिबिलिटी के जितना संभव हो उतना अनावृत करने का उद्देश्य रखता है"। यह, अन्य बातों के अतिरिक्त, एक ही कॉल में बहु-आयामी परिवर्तनों और एकाधिक परिवर्तनों की अनुमति देता है (उदाहरण के लिए, जहां डेटा को मेमोरी में इंटरलीव्ड किया जाता है)।
एफएफटीडब्ल्यू के पास आउट-ऑफ़-ऑर्डर ट्रांसफ़ॉर्म (मैसेज पासिंग इंटरफ़ेस (एमपीआई) संस्करण का उपयोग करके) के लिए सीमित समर्थन है। डेटा को पुन: व्यवस्थित करने में एक ओवरहेड खर्च होता है, जिससे अनियमित आकार और आयाम के स्थान-परिवर्तनों से बचना असतहीय है। यह अप्रलेखित है कि किस परिवर्तन के लिए यह ओवरहेड महत्वपूर्ण है।
एफएफटीडब्ल्यू को जीएनयू जनरल पब्लिक लाइसेंस के अंतर्गत लाइसेंस प्राप्त है। इसे एमआईटी[4] द्वारा व्यावसायिक रूप से लाइसेंस प्राप्त है (12,500 डॉलर तक की लागत पर) और इसका उपयोग एफएफटी की गणना के लिए वाणिज्यिक मैटलैब[5] मैट्रिक्स पैकेज में किया जाता है। एफएफटीडब्ल्यू C लैंग्वेज में लिखा गया है, लेकिन फोरट्रान और एडा इंटरफ़ेस मौजूद हैं, साथ ही कुछ अन्य भाषाओं के लिए भी इंटरफ़ेस मौजूद हैं। जबकि लाइब्रेरी स्वयं C है, कोड वास्तव में 'genfft' नामक प्रोग्राम से उत्पन्न होता है, जो OCaml में लिखा जाता है।[6]
1999 में, एफएफटीडब्ल्यू ने न्यूमेरिकल सॉफ्टवेयर के लिए जे. एच. विल्किंसन पुरस्कार जीता।
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 Frigo M, Johnson SG (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
- ↑ Frigo M, Johnson SG (1998). "FFTW: An adaptive software architecture for the FFT". Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181). Vol. 3. pp. 1381–1384. CiteSeerX 10.1.1.47.8661. doi:10.1109/ICASSP.1998.681704. ISBN 978-0-7803-4428-0. S2CID 12560207.
- ↑ Johnson SG, Frigo M (September 2008). "ch.11: Implementing FFTs in practice". In C. S. Burrus (ed.). फास्ट फूरियर ट्रांसफॉर्म. Houston TX: Connexions: Rice University.
- ↑ "View Technologies | MIT Technology Licensing Office".
- ↑ "FFTW - Fastest Fourier Transform in the West | MIT Technology Licensing Office". tlo.mit.edu. Retrieved 2023-02-07.
- ↑ "FFTW FAQ"
बाहरी संबंध
- No URL found. Please specify a URL here or add one to Wikidata.
