नया एमआईटी एल्गोरिथ्म तेजी से फूरियर रूपांतरण के दर्जनों गुना तेज करता है

इस सप्ताह असतत ACM एल्गोरिदम पर एक संगोष्ठी में, MIT के शोधकर्ताओं के एक समूह ने नई स्पार्स फास्ट फूरियर ट्रांसफॉर्म ( FF ) एल्गोरिदम पेश किया, जो कुछ समस्याओं में क्लासिक एफएफटी की तुलना में दसियों या सैकड़ों गुना तेज हो सकता है।

फूरियर रूपांतरण में गुणांक प्राप्त करना शामिल है ("आयाम") जब प्रारंभिक कार्य प्राथमिक घटकों में विघटित होता है - विभिन्न आवृत्तियों के साथ हार्मोनिक दोलन। तेजी से फूरियर रूपांतरण आपको इस प्रक्रिया को दो वेक्टर में गुणांक वेक्टर को विभाजित करके, उनके लिए डीएफटी की पुनरावृत्ति रूप से गणना करके और परिणामों को एक एफएफटी में जोड़कर गति प्रदान करने की अनुमति देता है। यह माना जाता है कि एफटीएस विधि 1805 में गॉस द्वारा प्रस्तावित की गई थी और 1965 में इसे फिर से खोजा गया था, जिसके बाद आधुनिक कंप्यूटरों के प्रसार के साथ इसका व्यापक रूप से उपयोग किया गया था। पिछले 50 वर्षों में, एफएफटी की दक्षता बढ़ाने के लिए कई प्रयास किए गए हैं, उदाहरण के लिए, एफएफटीडब्ल्यू ।

नई MIT एल्गोरिथ्म FFTW की तुलना में तेज होने का दावा किया जाता है। तुलना वैज्ञानिक कार्य में , साथ ही परियोजना पृष्ठ पर दी गई है ।

SFFT एल्गोरिथ्म (स्पार्स फास्ट फूरियर ट्रांसफॉर्म) दो मौजूदा फिल्टर (गाऊसी फिल्टर और चेबीशेव फिल्टर) के आधार पर बनाया गया था और इसका उद्देश्य जल्दी से एक "विरल" संकेत के साथ टुकड़े ढूंढना और उनमें से प्रत्येक में प्रारंभिक आयाम निर्धारित करना है। सिग्नल को टुकड़ों में विभाजित किया जाता है (तेजी से नमूनाकरण) जब तक कि एक एकल आयाम के साथ विरल संकेत नहीं रहता है। और पहले से ही, एक नया एल्गोरिथ्म इसे क्लासिक एफएफटी की तुलना में 10 हजार गुना तेज बताता है।

यह विधि सार्वभौमिक नहीं है, और अब वैज्ञानिक यह निर्धारित करने की कोशिश कर रहे हैं कि कौन से विशिष्ट अनुप्रयोगों में यह उत्पादकता में सबसे बड़ी वृद्धि देगा।

MIT के माध्यम से