கேள்வி: விரைவு ஃபூரியே உருமாற்றம் - துல்லியமான தன்மையும் தோராயமாக்கல்களும் பற்றி நீங்கள் என்ன அறிந்துள்ளீர்கள்?
பதில்: கீழே விவாதிக்கப்பட்டுள்ள அனைத்து FFT வழிமுறைகளும் DFT ஐ துல்லியமாகக் கணக்கிடுகின்றன (துல்லியமான எண் கணிதத்தில், அதாவது ஃப்ளோட்டிங் - பாயிண்ட் பிழைகளைப் புறக்கணிக்கின்றன). இருப்பினும், DFT ஐ ''தோராயமாகக்'' கணக்கிடும் ஒரு சில "FFT" வழிமுறைகளும் முன்மொழியப்பட்டுள்ளன, அவை அதிகமான கணக்கீடுகளின் சிரமத்துடன் ஒப்பிடுகையில் சீரற்ற முறையிலான மிகச் சிறிய பிழைகளைக் கொண்டிருக்கலாம். அது போன்ற வழிமுறைகள் அதிகரிக்கப்பட்ட வேகம் அல்லது பிற பண்புகளுக்கான தோராயமாக்கல் பிழைகளைக் கையாளுகின்றன. எடுத்துக்காட்டுக்கு, ஈடில்மேன் மற்றும் பலரால் முன்மொழியப்பட்ட (1999) ஒரு தோராய FFT வழிமுறையானது இணைக் கணக்கீட்டுக்கான குறைவான தகவல்தொடர்பு தேவைகளைக் கொண்டுள்ளது. அதற்கு ஒரு வேகப் பன்முக முறை உதவியாக உள்ளது. குவோ மற்றும் பர்ரஸ் அவர்களால் முமொழியப்பட்ட (1996) ஒரு சிற்றலை-அடிப்படையிலான தோராய FFT, ஒரு துல்லியமான FFT கொண்டு சாத்தியப்படுவதை விட அடர்த்தியற்ற உள்ளீடுகள்/வெளியீடுகளை (நேரம்/அதிர்வெண் இடமறிதல்) முக்கியமாகக் கருத்தில்கொள்கிறது. DFT வெளியீடுகளுக்கான துணைக்குழுவின் தோராயக் கணக்கீட்டுக்கான மற்றொரு வழிமுறை ஷெண்ட்டோவ் மற்றும் பலரால் கண்டுபிடிக்கப்பட்டது. (1995). இருப்பினும், அடர்த்தியற்ற மற்றும் அடர்த்தியான ஆகிய இரு வகை தரவுகளுக்கும் ஈடில்மேன் வழிமுறையே சிறப்பாகப் பயன்பட்டது. ஏனெனில் அது தரவின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்காமல் ஃபூரியே அணியின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்கிறது. புள்ளி இலக்க எண் கணிதங்கள் பயன்படுத்தப்படும் போது "துல்லியமான" FFT வழிமுறைகளிலும் பிழைகள் உள்ளன வரையறுக்கப்பட்ட-துல்லியம், ஆனால் இந்தப் பிழைகள் வழக்கமாக மிகச் சிறியன. பெரும்பாலான FFT வழிமுறைகள், எ.கா. கூலி-டக்கி, சிறந்த எண்ணியல் பண்புகளைக் கொண்டுள்ளன. ε என்பது மெஷின் ஃப்ளோட்டிங் பாயிண்ட் தொடர்பு நிலையாக உள்ள, நீவ் DFT சூத்திரத்துக்கான (ஜெண்டில்மேன் மற்றும் சாண்டி, 1966) O(ε''N'' 3/2) உடன் ஒப்பிடுகையில் கூலி டக்கி வழிமுறைக்கான தொடர்புப் பிழையிலான மேல் வரம்பானது O(ε log ''N'' ) ஆக உள்ளது. உண்மையில், சராசரி வர்க்கமூலப் (rms) பிழைகள் இந்த மேல் வரம்புகளைக் காட்டிலும் சிறந்தவை. அவற்றின் மதிப்பு கூலி டக்கி முறைக்கு O(ε √log ''N'' ) என்றும் நீவ் DFTக்கு (ஸ்கேட்ஸ்மேன், 1996) O(ε √''N'' ) என்றும் உள்ளது. இருப்பினும், இந்த முடிவுகள் FFT இல் (அதாவது, திரிகோணமிதி சார்புகளின் மதிப்புகள்) பயன்படுத்தப்படும் சுழற்றுக் காரணிகளின் துல்லியத் தன்மையால் நுட்பமாக பாதிக்கப்படக்கூடியவை, மேலும் கவனக்குறைவான FFT செயல்படுத்தல்கள் மிக மோசமான துல்லியத்தன்மையைக் கொண்டிருப்பது அரிதானதல்ல, எ.கா. அவை துல்லியமற்ற திரிகோணமிதி மறுநிகழ்வு சூத்திரங்களைப் பயன்படுத்தலாம். ரேடர்-ப்ரென்னர் வழிமுறை போன்று, கூலி டக்கி தவிர்த்த சில FFTகள், உண்மையில் குறைவான நம்பகத்தன்மை கொண்டவை. நிலையான-புள்ளி எண்கணிதத்தில், FFT வழிமுறைகளால் சேர்ந்த வரையறுக்கப்பட்ட-துல்லியப் பிழைகள் மிக மோசமானவை, கூலி டக்கி வழிமுறைக்கு (வெல்ச், 1969) அவற்றின் rms பிழைகள் O(√''N'' ) என்ற அளவில் உள்ளன. மேலும், துல்லியத் தன்மை இழப்பதைக் குறைப்பதற்காக இந்த அளவு துல்லியமான தன்மையை அடைவதற்கும் கூட, அளவிடுவதில் அதிகக் கவனம் தேவைப்படுகிறது. மேலும் நிலையான-புள்ளி FFT வழிமுறைகளில் கூலி-டக்கி போன்ற பிரித்துக்கணக்கிடலின் ஒவ்வொரு இடை நிலையிலும் மறு அளவீடும் தேவைப்படுகிறது. ஒரு FFT செயல்படுத்தலின் சரியான தன்மையை உறுதிப்படுத்த, உருமாற்றத்தின் சீரற்ற உள்ளீடுகளின் நேரியல் தன்மை, தூண்டல் எதிர்வினை மற்றும் கால உருமாற்றப் பண்புகளைச் சோதிக்கும் ஒரு எளிய செயலின் மூலம் (எர்கன், 1995) O(''N'' log ''N'' ) நேரத்தில், உறுதியான உத்தரவாதங்களைப் பெற முடியும்.
கேள்வி: விரைவு ஃபூரியே உருமாற்றம் - பலபரிமாண FFTகள் பற்றி தகவல் சொல்.
பதில்: பலபரிமாண DFT கட்டுரையில் வரையறுக்கப்பட்டுள்ளபடி, பின்வரும் பல பரிமாண DFT :X_\mathbf{k} = \sum_{\mathbf{n}=0}^{\mathbf{N}-1} e^{-2\pi i \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n} ஆனது \mathbf{n}=(n_1, n_2, \ldots, n_d) முனைகளை உடைய d-பரிமாண வெக்டார் கொண்ட x_\mathbf{n} எனும் ஒரு அணியை d குழு கூடு கூட்டல்களுக்கு (ஒவ்வொரு j க்கும் n_j = 0 \ldots N_j-1 க்கும் மேலாக) மாற்றுகிறது. இதில் பிரிவு \mathbf{n} / \mathbf{N}, \mathbf{n} / \mathbf{N} = (n_1/N_1, \cdots, n_d/N_d) என வரையறுக்கப்படுகிறது, அது ஒவ்வொரு உறுப்புவாரியாக செயல்படுத்தப்படுகிறது. சமமான விதத்தில், அது ஒற்றைப் பரிமாண DFTகளின் d குழுக்களின் தொடர்ச்சியான கூட்டமைப்பே ஆகும். இது ஒரு நேரத்தில் ஒரு பரிமாணத்தின் வழியாக மட்டுமே (ஏதேனும் ஒரு வரிசையில்) செயல்படுத்தப்படுகிறது. இந்தக் கணக்கீட்டியல் கருத்துக் கண்ணோட்டமானது எளிய மற்றும் மிகப் பொதுவான பல பரிமாண DFT வழிமுறையை வழங்குகிறது. அது (கீழே விவரிக்கப்படும் இரு பரிமாண நிகழ்வைக் கொண்டு) நிரை-நிரல் வழிமுறை என அழைக்கப்படுகிறது. அதாவது, ஒருவர் வெறுமென d ஒற்றைப் பரிமாண FFTகளின் தொடரை மட்டுமே செயல்படுத்துகிறார் (மேலே கூறப்பட்ட வழிமுறைகளில் ஏதேனும் ஒன்றின் மூலம்): முதலில் n_1 பரிமாணத்தின் வழியே மாற்றம் செய்கிறீர்கள், பின்னர் n_2 பரிமாணம், இதே போல் தொடர்கிறீர்கள் (அல்லது உண்மையில் எந்த வரிசையிலும் இது சரியாக முடிவைக் கொடுக்கும்). இந்த முறையானது O(N \log N) சிக்கலான தன்மையைக் கொண்டிருப்பதாக எளிதாக நிரூபிக்கப்பட்டது. இதில் N = N_1 N_2 \cdots N_d என்பது மாற்றப்பட்ட தரவுப் புள்ளிகளின் மொத்த எண்ணிக்கையாகும். குறிப்பாக, N_1, போன்ற அளவுடைய N/N_1 உருமாற்றங்கள் உள்ளன, ஆகவே FFTகளின் தொடரின் சிக்கலான தன்மை பின்வருமாறு: : \begin{align} &amp; {} \qquad \frac{N}{N_1} O(N_1 \log N_1) + \cdots + \frac{N}{N_d} O(N_d \log N_d) \\[6pt] &amp; = O\left(N \left[\log N_1 + \cdots + \log N_d\right]\right) = O(N \log N). \end{align} இரு பரிமாணங்களில், x_\mathbf{k} ஐ ஒரு n_1 \times n_2 அணியாகக் கருதலாம். மேலும் இந்த வழிமுறையானது முதலில் அணியின் அனைத்து நிரைகளின் FFT ஐ செயல்படுத்தி பின்னர் அனைத்து நிரல்களின் FFT ஐ செயல்படுத்தும் முறையைக் கொண்டது (அல்லது மறுதிசையில்), இதனாலே இம்முறைக்கு இந்தப் பெயர் வந்தது. இரு பரிமாணத்திற்கும் அதிகமான நிகழ்வில், பல சமயங்களில் பதுக்கக இட அமைப்பை மீண்டும் மீண்டும் குழுப்படுத்துதல் என்பது பயன்மிக்கதாக இருக்கும். எடுத்துக்காட்டுக்கு, ஒரு முப்பரிமாண FFT ஆனது முதலில் ஒவ்வொரு நிலையான n_1 க்குமான ஒவ்வொரு தள "ஸ்லைஸின்" இரு-பரிமாண FFTகளை செயல்படுத்தலாம், பின்னர் அது ஒற்றைப் பரிமாண FFTகளை n_1 திசையில் செயல்படுத்தலாம். பொதுவாக, ஒரு தொலைத்தொடுகோட்டு சிறப்பு பதுக்கக-நினைவகக் குறை வழிமுறையில், மீண்டும் மீண்டும் மாற்றம் செய்யப்படும் பரிமாணங்களை மீண்டும் மீண்டும் (n_1, \cdots, n_{d/2}) மற்றும் (n_{d/2+1}, \cdots, n_d) என இரு குழுவாகப் பிரிக்கும் நிகழ்வு இடம்பெறுகிறது (d என்பது இரட்டையாக இல்லாதபட்சத்தில் அது முழுமையாக்கும்) (காண்க: ஃப்ரிகோ மற்றும் ஜான்சன், 2005). இருப்பினும், இது இரு-நிரல் வழிமுறையின் நேர்பாங்கான வகையாக உள்ளது, இதற்கு அடிப்படை நிகழ்வாக மொத்தம் ஒற்றைப் பரிமாண FFT வழிமுறையே தேவைப்படுகிறது, மேலும் இதில் O(N \log N) சிக்கலான தன்மை மட்டுமே உள்ளது. மாற்றம் செய்யப்படும் பரிமாணங்களுக்கிடையே அணி இடமாற்றத்தைச் செயல்படுத்துவது என்பது இன்னுமொரு வகையாகும், ஆகவே உருமாற்றமானது அருகாமைத் தரவின் மீதே செயல்படுகிறது. குறிப்பாக இது அருகாமையிலல்லாத தரவை அணுகுவது என்பது அதிக நேரம் எடுத்துக்கொள்ளும் நிகழ்வாக உள்ள, மையத்திற்கு புறத்தேயான மற்றும் பகிரப்பட்ட நினைவக சூழ்நிலைகளுக்கு முக்கியமானதாகும். நிரை-நிரல் வழிமுறையிலிருந்து வேறுபட்டுள்ள பிற பலபரிமாண FFT வழிமுறைகளும் உள்ளன, இருப்பினும் அவை அனைத்திலும் O(N \log N) சிக்கலான தன்மை உள்ளது. மிக எளிய நிரல்-நிரை அல்லாத FFT வெக்டார்-ரேடிக்ஸ் FFT வழிமுறையாக இருக்கலாம், அது வழக்கமான கூலி-டக்கி வழிமுறையின் பொதுமையாக்கலாக உள்ளது, அதில் நாம் உருமாற்றப் பரிமாணங்களை ஒவ்வொரு படியிலும் \mathbf{r}=(r_1, r_2, \cdots, r_d) என்ற ரேடிக்ஸ் வெக்டாரால் வகுக்கிறோம். (இதில் பதுக்கக நன்மைகளும் இருக்கலாம்.) அனைத்து ரேடிக்ஸ்களும் சமமாக இருப்பது என்பது வெக்டார்-ரேடிக்ஸின் எளிய நிகழ்வாகும் (எ.கா. வெக்டார்-ரேடிக்ஸ்-2, பரிமாணங்கள் ''அனைத்தையும்'' இரண்டால் வகுக்கிறது), ஆனால் இது அவசியம் என்பதல்ல. ஒரு நேரத்தில் ஒன்றல்லாத ஒரே ஒரு ரேடிக்ஸைக் கொண்டுள்ள வெக்டார், அதாவது \mathbf{r}=(1, \cdots, 1, r, 1, \cdots, 1), கட்டாயமாக ஒரு நிரை-நிரல் வழிமுறையாகவே இருக்கும். மற்ற மிகச் சிக்கலான முறைகளில் நுஸ்ஸம்பரின் (1977) பல்லுறுப்புக்கோவை உருமாற்ற வழிமுறைகள் போன்றவை அடங்கும். அதன்படி உருமாற்றங்கள் சுழற்சிகளாகவும் பல்லுறுப்புக்கோவை விளைபலன்களாகவும் கருதப்படுகின்றன. மேலும் தகவல்களுக்கும் குறிப்புதவிகளுக்கும் டுஹாமெல் மற்றும் வெட்டெர்லி (1990) என்பதைக் காண்க.