Kompleksitas menghitung transformasi Fourier diskrit?

Apa kompleksitas (pada RAM bilangan bulat standar) komputasi standar diskrit Fourier transform dari vektor bilangan bulat?$n$

Algoritma klasik untuk transformasi Fourier cepat , yang tidak tepat ^[1] dikaitkan dengan Cooley dan Tukey, biasanya digambarkan sebagai berjalan dalam waktu . Tapi sebagian besar operasi aritmatika dieksekusi dalam algoritma ini mulai dengan kompleks th akar kesatuan, yang (untuk sebagian besar ) tidak rasional, evaluasi sehingga tepat dalam waktu yang konstan tidak masuk akal. Masalah yang sama muncul dengan algoritma waktu -naif (dikalikan dengan matriks Vandermonde dari akar kompleks persatuan).n n O ( n 2$O(n \log n)$$n$$n$$O(n^2)$

Bahkan tidak jelas bagaimana merepresentasikan output DFT dengan tepat (dalam bentuk apa pun yang bermanfaat). Dengan kata lain, tidak jelas bahwa komputasi DFT sebenarnya mungkin!

Jadi anggaplah kita hanya membutuhkan bit presisi di setiap nilai output. Apa kompleksitas menghitung transformasi Fourier diskrit, sebagai fungsi dari dan ? (Untuk konkret, jangan ragu untuk menganggap adalah kekuatan )n b n $b$$n$$b$$n$$2$

Atau apakah setiap contoh "FFT" dalam literatur sebenarnya berarti " transformasi bilangan- cepat "? ^[2]

Lihat pertanyaan terkait saya tentang kompleksitas eliminasi Gaussian dan jalur terpendek Euclidean .

_{^[1] Ini harus benar-benar disebut (beberapa awalan) algoritma Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey.}

_{^[2] Dan jika demikian, mengapa sebagian besar buku teks hanya menggambarkan algoritma bilangan kompleks?}

Jawaban ini adalah varian dari analisis algoritma pertama ("Methode A") oleh Schonhage dan Strassen untuk perkalian bilangan bulat panjang.

Asumsikan kita ingin menghitung FFT dengan panjang . Skala masukan Anda sehingga semua nilai-nilai yang lebih kecil dari 1. Mari kita asumsikan bahwa kita menghitung dengan m -bit titik tetap aritmatika ( m bit setelah titik biner). Mari δ = 2 1 / 2 - m menjadi ( "kompleks") unit posisi paling. Biarkan ω = exp ( 2 π i / K ) .$K = 2^k$$m$$m$$\delta = 2^{1/2 -m}$$\omega = \exp(2\pi i/K)$

1) Seseorang dapat menghitung perkiraan sedemikian rupa sehingga | ω ′ j - ω j | ≤ ( 2 k - 1 ) δ untuk semua 0 ≤ j ≤ K - 1 . Ini dapat dilakukan dalam waktu O ( K M ( m ) ) di mana M ( m ) adalah waktu yang diperlukan untuk mengalikan angka m- bit. (lihat Knuth Vol. 2, ed. 3, halaman 309).$\omega_j'$$|\omega_j' - \omega^j| \le (2k-1)\delta$$0 \le j \le K-1$$O(K M(m))$$M(m)$$m$

Jika standar integer RAM berarti biaya logaritmik, maka . Jika standar integer RAM berarti RAM kata, maka M ( m ) = O ( m ) . (Schönhage dan Strassen menunjukkan dalam "Methode A" bagaimana mengurangi waktu linier penggandaan angka m- bit ke m penggandaan angka bit O ( log m ) . Yang terakhir dapat dilakukan dengan biaya satuan.)$M(m) = O(m \log m)$$M(m) = O(m)$$m$$m$$O(\log m)$

2) FFT Cooley-Tukey klasik menghitung operasi dari bentuk . Kami menggunakan m -bit titik tetap aritmatika, opertions ini menjadi sebuah ' = t r u n c a t e ( b ' + ω ' j c ' ) . Jika kita tahu b ' dan c ' sampai kesalahan dari ε , kita mendapatkan sebuah ' hingga kesalahan dari 2 ε + $a = b + \omega^j c$$m$$a' = truncate(b' + \omega_j' c')$$b'$$c'$$\epsilon$$a'$ .$2\epsilon + 2k\delta$

3) Menggunakan induksi, mudah untuk melihat bahwa kita mendapatkan hasil akhir dengan kesalahan . Untuk mendapatkan ketelitian b pada akhirnya, m ≥ k + log k + b + O ( 1 ) . $(2^k - 1) \cdot 2k\delta$$b$$m \ge k + \log k + b + O(1)$

4) Jadi waktu berjalan terakhir adalah .$O(K k M(k+b))$

Ini juga harus bekerja dengan angka floating point: 1) masih dapat dilakukan dengan aritmatika titik tetap, 2) juga berlaku untuk angka floating point.

Dalam aritmatika titik tetap, saya pikir, itu bahkan dapat dilakukan lebih cepat. Pertama-tama kita mengurangi perhitungan FFT menjadi penggandaan polinomial menggunakan trik Bluestein. Panjang koefisien yang dibutuhkan untuk mendapatkan ketelitian yang diinginkan adalah . Kemudian kita mengurangi multiplikasi polinomial menjadi multiplikasi bilangan bulat panjang. (Tambahkan koefisien ke angka panjang dan pisahkan dengan blok nol panjang O ( k + b ) .) Panjang bilangan bulat adalah O ( K ( k + b ) ) .$O(k + b)$$O(k+b)$$O(K(k+b))$

Ini bukan jawaban yang lengkap, tetapi saya dapat mengarahkan Anda ke beberapa makalah yang relevan dan juga menjelaskan mengapa tidak mudah untuk mengekstrak jawaban atas pertanyaan spesifik Anda dari literatur.

Mari saya mulai dengan bertanya, mengapa Anda ingin tahu jawaban untuk pertanyaan ini? Biasanya, orang-orang yang peduli dengan masalah semacam ini adalah mereka yang dihadapkan dengan penerapan FFT kinerja tinggi untuk aplikasi praktis. Orang-orang seperti itu kurang peduli tentang kompleksitas asimptotik dalam beberapa model komputasi ideal daripada tentang memaksimalkan kinerja di bawah kendala perangkat keras dan perangkat lunak tertentu. Misalnya, pengembang Transformasi Fourier Tercepat di Barat menulis di makalah mereka:

Pilihan terbaik tergantung pada perincian perangkat keras seperti jumlah register, latensi dan throughput instruksi, ukuran dan asosiasi cache, struktur dari pipa prosesor, dll.

Ini adalah masalah yang biasanya tidak ingin dikuasai oleh para ahli teori, tetapi mereka sangat penting dalam implementasi aktual. Jika seorang ahli teori menyatakan, "Saya sudah menemukan kompleksitas bit asimptotik absolut terbaik dalam model RAM," praktisi mungkin berkata, "Itu bagus," tetapi mungkin menemukan hasil teoritis seperti itu tidak berguna untuk tujuannya.

Karena itu, saya berpikir bahwa taruhan terbaik Anda adalah dengan melihat literatur analisis numerik. Sebagai contoh, Tasche dan Zeuner telah mencermati stabilitas numerik dari algoritma FFT. Ini mungkin masih belum persis seperti yang Anda inginkan, karena konsensus umum di antara para praktisi tampaknya adalah untuk mencapai jumlah presisi numerik tertentu, pendekatan praktis terbaik adalah dengan menghitung angka-angka tertentu yang disebut "faktor-faktor ganda" dengan akurasi tinggi. Jika Anda hanya melakukan satu FFT, maka ini tidak akan menjadi pendekatan tercepat karena Anda tidak bisa mengamortisasi biaya perhitungan satu kali Anda atas sejumlah besar perhitungan FFT. Namun, analisis mereka tentang kesalahan pembulatan kasus terburuk masih harus relevan dengan pertanyaan Anda.