# விரைவு ஃபூரியே உருமாற்றம்

## கணக்கீட்டு சிக்கல்கள்

### சிக்கலான தன்மையின் வரம்புகள் மற்றும் செயல்பாடு எண்ணிக்கைகள்

விரைவு ஃபூரியே உருமாற்றங்களின் சிக்கலான தன்மையின் கீழ் வரம்புகள் மற்றும் செயல்பாடுகளின் துல்லியமான எண்ணிக்கை ஆகியவை நீண்டகாலமாக இருந்துவரும் கோட்பாட்டியல் கருத்தின் ஓர் அடிப்படைக் கேள்வியாகும், அதுமட்டுமின்றி பல கணக்குகள் இன்னும் தீர்க்கப்படாமலே உள்ளன. DFTகளுக்கு உண்மையிலேயே <math>\Omega(N \log N)</math> (அதாவது <math>N \log N</math> என்னும் அளவில் அல்லது அதைவிட அதிக) செயல்பாடுகள் தேவை என பெரிதாக நிரூபிக்கப்படவில்லை, அடுக்கு இரண்டு என்ற அளவிலான சிறிய நிகழ்வுகளுக்கும் அது நிரூபிக்கப்படவில்லை, இருப்பினும் குறைவான சிக்கலான தன்மை கொண்டுள்ள வழிமுறைகளும் இல்லை. வழக்கமாக குறிப்பாக, இது போன்ற கேள்விகளின் மையமாக இருப்பது எண் கணித செயல்பாடுகளின் எண்ணிக்கையே ஆகும், இருப்பினும் தற்கால கணினிகளிலான உண்மையான செயல்திறனானது தேக்ககம் அல்லது CPU பைப்லைன் உகந்ததாக்கல் போன்ற பிற பல காரணிகளால் தீர்மானிக்கப்படுகிறது.  
வினோக்ராடின் (1978) முன்னோடிப் பணிகளைத் தொடர்ந்து, FFT க்கு தேவையான மெய் பெருக்கல்களின் எண்ணிக்கைக்கான ஒரு இறுக்கமான <math>\Theta(N)</math> கீழ் வரம்பு *அறியப்பட்டது*. அடுக்கு இரண்டு மற்றும் நீளம் <math>N=2^m</math> கொண்ட ஒரு DFTஐக் கணக்கிட வெறும் <math>4N-2\log_2^{2}N-2\log_2 N-4</math> விகிதமுறா மெய் பெருக்கல்களே தேவை எனக் காண்பிக்க முடியும். மேலும், இந்த எண்ணிக்கையை அடையும் வெளிப்படையான வழிமுறைகள் அறியப்பட்டன (ஹெயிட்மேன் & புர்ரஸ், 1986. டுஹேமல், 1990). துரதிருஷ்டவசமாக, குறைந்தது, வன்பொருள் பெருக்கிகளைக் கொண்ட நவீன கணினிகளில் இந்த வழிமுறைகளுக்கு நடைமுறையில் அதிக கூட்டல்கள் தேவைப்பட்டன.  
தேவையான கூட்டல்களின் எண்ணிக்கையிலான ஓர் இறுக்கமான கீழ் வரம்பு *அறியப்படவில்லை* , இருப்பினும் வழிமுறைகளிலான சில கட்டுப்படுத்தல் கருதுகோள்களின் அடிப்படையில் சில கீழ் வரம்புகள் நிரூபிக்கப்பட்டுள்ளன. 1973 ஆம் ஆண்டில், வழிமுறைகளுக்கான கூட்டல் எண்ணிக்கையிலான ஒரு <math>\Omega(N \log N)</math> கீழ் வரம்பை மார்கென்ஸ்டர்ன் (Morgenstern) நிரூபித்தார். அதில் பெருக்கல் தொடர்பான மாறிலிகளுக்கு கட்டுண்ட எண்ணளவுகள் இருந்தன (இது பெரும்பாலான FFT வழிமுறைகளுக்கு மெய்யாகும், ஆனால் அனைத்து வழிமுறைகளுக்குமல்ல). பேன் (Pan) (1986) ஒரு <math>\Omega(N \log N)</math> கீழ் வரம்பை நிரூபித்தார், அவர் FFT வழிமுறையின் "ஒத்திசைவின்மை" அளவிலான வரம்பைக் கருத்தில் கொண்டார். ஆனால் இந்தக் கருதுகோளின் பொதுத்தன்மையானது தெளிவாக இல்லை. <math>N</math> இன் அடுக்கு இரண்டு என்ற நிபந்தனைக்கு, பாப்படிமித்ரியோ (Papadimitriou) (1979), கூலி டக்கி வழிமுறையைப் பயன்படுத்திப் பெறப்பட்ட சிக்கலெண் கூட்டல்களின் எண் <math>N \log_2 N</math> ஆனது வழிமுறையின் வரைபடத்தின் சில குறிப்பிட்ட கருதுகோள்களின் அடிப்படையில் *சிறந்ததாக* உள்ளது என விவாதித்தார் (அவரது கருதுகோள்கள் பிற அம்சங்களுடன் ஒன்றின் மூலங்களிலுள்ள கூட்டல் உறுப்புகள் எதுவும் பயன்படுத்தப்படவில்லை என்பதையும் குறிப்பிடுகிறது). (இந்த விவாதமானது குறைந்தபட்சம் <math>2 N \log_2 N</math> மெய் கூட்டல்கள் தேவைப்படுகின்றன எனக் குறிப்பிடுகின்றது, இருப்பினும் இது இறுக்கமான வரம்பு கிடையாது, ஏனெனில் சிக்கலெண் பெருக்கலின் பகுதியாக கூடுதல் கூட்டல்கள் தேவைப்படுகின்றன.) இதுவரை வெளியிடப்பட்ட FFT வழிமுறை எதுவும், <math>N</math> இன் அடுக்கு இரண்டுக்கான <math>N \log_2 N</math> க்கும் குறைவான சிக்கலெண் கூட்டல்கள் எண்ணிக்கையை (அல்லது அதற்கு சமமான எண்ணிக்கையை) சாத்தியமாக்கவில்லை.  
*மொத்த* மெய் பெருக்கங்கள் மற்றும் கூட்டல்களின் எண்ணிக்கையைக் குறைப்பது மூன்றாவது சிக்கலாகும், இது சில நேரங்களில் "எண் கணிதவியல் சிக்கலான தன்மை" என அழைக்கப்படுகிறது (இருப்பினும் இந்தச் சூழலில் அது கருதப்படும் தொலைத் தொடுகோட்டு ரீதியான சிக்கலான தன்மையாக இல்லாமல் துல்லியமான எண்ணிக்கையாக உள்ளது). இறுக்கமான எல்லை எதுவும் நிரூபிக்கப்படவும் இல்லை. இருப்பினும் 1968 ஆம் ஆண்டிலிருந்து, <math>N</math> இன் அடுக்கு இரண்டுக்கான வெளியிடப்பட்ட குறைந்தபட்ச எண்ணிக்கை ஸ்ப்ளிட்-ரேடிக்ஸ் FFT வழிமுறையின் மூலம் சாத்தியப்பட்டுள்ளது. அதற்கு <math>N > 1</math> என்ற நிபந்தனையில், <math>4N\log_2 N-6N+8</math> மெய்ப் பெருக்கங்களும் கூட்டல்களும் தேவைப்பட்டன. இது சமீபத்தில் <math>\sim \frac{34}{9} N \log_2 N</math> எனக் குறைக்கப்பட்டது (ஜான்சன் மற்றும் ஃப்ரிகோ, 2007; லண்டி மற்றும் வேன் பஸ்கிர்க், 2007).  
FFT வழிமுறைகளின் சிக்கலான தன்மையைக் குறைக்க அல்லது நிரூபிப்பதற்கான பெரும்பாலான முயற்சிகள் சாதாரண சிக்கலான தரவு நிகழ்வுகளிலேயே கவனம் செலுத்தியுள்ளன, ஏனெனில் அவை எளிமையானவை. இருப்பினும், சிக்கலான தரவு FFTகள் மெய்-தரவு FFTகள், இலக்கமியல் கொசைன் உருமாற்றங்கள், இலக்கமியல் ஹார்ட்லி உருமாற்றங்கள் போன்ற தொடர்புடைய சிக்கல்களுக்கான வழிமுறைகளுடன் மிகவும் நெருக்கமான தொடர்புடையவை. அதாவது இதில் ஏதேனும் ஒன்றின் மேம்பாடு உடனடியாக மற்றவற்றின் மேம்பாடுகளுக்கு வழிவகுக்கும் (டுஹாமெல் & வெட்டர்லி, 1990).