एफएफटीडब्ल्यू: Difference between revisions
No edit summary |
|||
| Line 5: | Line 5: | ||
==लाइब्रेरी== | ==लाइब्रेरी== | ||
एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और | एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और एक (छोटे परिवर्तनों में परिवर्तन का एक विशेष अपघटन) चुनकर डेटा को तेजी से परिवर्तित करता है, जिसका अनुमान या उपाय विशेष परिस्थितियों में बेहतर होता है। यह छोटे अभाज्य कारकों के साथ आकार के सरणियों पर सबसे अच्छा काम करता है, जिसमें दो की घातें इष्टतम होती हैं और बड़े अभाज्य सबसे निकृष्ट स्थिति होती हैं (लेकिन फिर भी O(n log n))। समग्र आकारों के परिवर्तनों को छोटे परिवर्तनों में विघटित करने के लिए, यह कौली-टुकी एफएफटी एल्गोरिदम (विभिन्न गुणनखंडन और/या विभिन्न मेमोरी-एक्सेस पैटर्न के अनुरूप) के कई प्रकारों में से चुनता है, जबकि अभाज्य आकारों के लिए यह या तो रेडर या ब्लूस्टीन के एफएफटी एल्गोरिदम का उपयोग करता है।<ref name="Frigo2005"/> एक बार जब परिवर्तन को पर्याप्त रूप से छोटे आकार के उप-रूपांतरणों में विभाजित कर दिया जाता है, तो एफएफटीडब्ल्यू इन छोटे आकारों के लिए हार्ड-कोडेड अनरोल्ड एफएफटी का उपयोग करता है जो कोड जनरेशन द्वारा उत्पादित किए गए थे (संकलन समय पर, रन समय पर नहीं); ये रूटीन विभिन्न प्रकार के एल्गोरिदम का उपयोग करते हैं जिनमें कूली-ट्यूकी वेरिएंट, राडार का एल्गोरिदम और [[प्राइम-फैक्टर एफएफटी एल्गोरिदम]] शामिल हैं।<ref name="Frigo2005"/> | ||
पर्याप्त रूप से बड़ी संख्या में दोहराए गए परिवर्तनों के लिए दिए गए सरणी आकार और [[प्लेटफ़ॉर्म (कंप्यूटिंग)]] पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को मापना फायदेमंद है। ये माप, जिन्हें लेखक ज्ञान कहते हैं, बाद में उपयोग के लिए किसी फ़ाइल या स्ट्रिंग में संग्रहीत किए जा सकते हैं। | पर्याप्त रूप से बड़ी संख्या में दोहराए गए परिवर्तनों के लिए दिए गए सरणी आकार और [[प्लेटफ़ॉर्म (कंप्यूटिंग)]] पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को मापना फायदेमंद है। ये माप, जिन्हें लेखक ज्ञान कहते हैं, बाद में उपयोग के लिए किसी फ़ाइल या स्ट्रिंग में संग्रहीत किए जा सकते हैं। | ||
Revision as of 18:25, 30 July 2023
फास्टेस्ट फूरियर ट्रांसफॉर्म इन द वेस्ट (एफएफटीडब्ल्यू) मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में माटेओ फ्रिगो और स्टीवन जी. जॉनसन द्वारा विकसित असतत फूरियर ट्रांसफॉर्म (डीएफटी) की गणना के लिए एक सॉफ्टवेयर लाइब्रेरी है।[1][2][3]
एफएफटीडब्ल्यू फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) के सबसे नवीनतम मुक्त सॉफ्टवेयर कार्यान्वयनों में से एक है। यह अनियमित आकार और आयाम के वास्तविक और जटिल-मूल्यवान सरणियों के लिए एफएफटी एल्गोरिथ्म को प्रयुक्त करता है।
लाइब्रेरी
एफएफटीडब्ल्यू विभिन्न प्रकार के एल्गोरिदम का समर्थन करके और एक (छोटे परिवर्तनों में परिवर्तन का एक विशेष अपघटन) चुनकर डेटा को तेजी से परिवर्तित करता है, जिसका अनुमान या उपाय विशेष परिस्थितियों में बेहतर होता है। यह छोटे अभाज्य कारकों के साथ आकार के सरणियों पर सबसे अच्छा काम करता है, जिसमें दो की घातें इष्टतम होती हैं और बड़े अभाज्य सबसे निकृष्ट स्थिति होती हैं (लेकिन फिर भी O(n log n))। समग्र आकारों के परिवर्तनों को छोटे परिवर्तनों में विघटित करने के लिए, यह कौली-टुकी एफएफटी एल्गोरिदम (विभिन्न गुणनखंडन और/या विभिन्न मेमोरी-एक्सेस पैटर्न के अनुरूप) के कई प्रकारों में से चुनता है, जबकि अभाज्य आकारों के लिए यह या तो रेडर या ब्लूस्टीन के एफएफटी एल्गोरिदम का उपयोग करता है।[1] एक बार जब परिवर्तन को पर्याप्त रूप से छोटे आकार के उप-रूपांतरणों में विभाजित कर दिया जाता है, तो एफएफटीडब्ल्यू इन छोटे आकारों के लिए हार्ड-कोडेड अनरोल्ड एफएफटी का उपयोग करता है जो कोड जनरेशन द्वारा उत्पादित किए गए थे (संकलन समय पर, रन समय पर नहीं); ये रूटीन विभिन्न प्रकार के एल्गोरिदम का उपयोग करते हैं जिनमें कूली-ट्यूकी वेरिएंट, राडार का एल्गोरिदम और प्राइम-फैक्टर एफएफटी एल्गोरिदम शामिल हैं।[1]
पर्याप्त रूप से बड़ी संख्या में दोहराए गए परिवर्तनों के लिए दिए गए सरणी आकार और प्लेटफ़ॉर्म (कंप्यूटिंग) पर कुछ या सभी समर्थित एल्गोरिदम के प्रदर्शन को मापना फायदेमंद है। ये माप, जिन्हें लेखक ज्ञान कहते हैं, बाद में उपयोग के लिए किसी फ़ाइल या स्ट्रिंग में संग्रहीत किए जा सकते हैं।
एफएफटीडब्ल्यू में एक गुरु इंटरफ़ेस है जो अंतर्निहित एफएफटीडब्ल्यू आर्किटेक्चर में जितना संभव हो सके लचीलेपन को उजागर करने का इरादा रखता है। यह, अन्य बातों के अलावा, एक ही कॉल में बहु-आयामी परिवर्तनों और एकाधिक परिवर्तनों की अनुमति देता है (उदाहरण के लिए, जहां डेटा को मेमोरी में इंटरलीव किया जाता है)।
एफएफटीडब्ल्यू के पास आउट-ऑफ-ऑर्डर ट्रांसफ़ॉर्म (संदेश पासिंग इंटरफ़ेस (एमपीआई) संस्करण का उपयोग करके) के लिए सीमित समर्थन है। Cooley-Tukey FFT एल्गोरिथम#डेटा रीऑर्डरिंग, बिट रिवर्सल और इन-प्लेस एल्गोरिदम में ओवरहेड होता है, जिससे मनमाने आकार और आयाम के इन-प्लेस परिवर्तनों से बचना गैर-तुच्छ है। यह अप्रलेखित है कि यह ओवरहेड किस परिवर्तन के लिए महत्वपूर्ण है।
एफएफटीडब्ल्यू को जीएनयू जनरल पब्लिक लाइसेंस के तहत लाइसेंस प्राप्त है। इसे एमआईटी द्वारा व्यावसायिक रूप से भी लाइसेंस प्राप्त है ($12,500 तक की लागत पर)।[4] और वाणिज्यिक MATLAB में उपयोग किया जाता है[5] एफएफटी की गणना के लिए मैट्रिक्स पैकेज। एफएफटीडब्ल्यू सी (प्रोग्रामिंग भाषा) भाषा में लिखा गया है, लेकिन फोरट्रान और एडा (प्रोग्रामिंग भाषा) इंटरफेस मौजूद हैं, साथ ही कुछ अन्य भाषाओं के लिए इंटरफेस भी मौजूद हैं। जबकि लाइब्रेरी स्वयं सी है, कोड वास्तव में 'नामक प्रोग्राम से उत्पन्न होता हैgenfft', जो OCaml में लिखा गया है।[6]
1999 में, FFTW ने न्यूमेरिकल सॉफ्टवेयर के लिए जे. एच. विल्किंसन पुरस्कार जीता।
यह भी देखें
संदर्भ
- ↑ 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.
