Konvolusi, Fast Fourier Transform, dan Polinomial (2022)

 (alvarorevuelta.com)
1 poin oleh GN⁺ 2024-07-02 | 1 komentar | Bagikan ke WhatsApp
  • Jika polinomial berderajat besar diekspansi dengan cara ala sekolah menengah, semua pasangan suku harus dikalikan, sehingga biaya O(n²) cepat menjadi bottleneck
  • Perkalian vektor koefisien polinomial sama dengan konvolusi sinyal diskret, dan hasil dari [2, 3, 4] dan [5, 6, 7] adalah [10, 27, 52, 45, 28]
  • DFT memindahkan sinyal diskret ke domain frekuensi, dan FFT menghitung transformasi yang sama dalam O(n log n), sehingga membuat perbedaan pada input besar
  • Konvolusi di domain waktu berubah menjadi perkalian per elemen di domain frekuensi, jadi dengan mentransformasikannya memakai FFT, mengalikannya, lalu mengembalikannya dengan IFFT, perkalian polinomial dapat diproses lebih cepat
  • Pada derajat kecil, biaya pulang-pergi FFT/IFFT dapat meniadakan keuntungannya, tetapi semakin besar derajatnya, metode FFT semakin efisien

Mengapa perkalian polinomial menjadi lambat

  • Polinomial P(x) dinyatakan sebagai bentuk penjumlahan suku-suku berupa koefisien a_k dan pangkat dari variabel x
    • Contoh P(x)=5x²+2x+9 adalah polinomial berderajat 2
    • Vektor koefisien dapat ditampilkan sebagai [5, 2, 9] atau [9, 2, 5], tergantung notasinya
  • Penjumlahan dan pengurangan relatif sederhana karena cukup menjumlahkan atau mengurangkan suku dengan derajat yang sama
    • Di Python, kita dapat mengiterasi setiap koefisien dengan zip(p, q) lalu menghitung a + b atau a - b
    • Jika derajatnya berbeda, zip_longest dapat digunakan
  • Perkalian membutuhkan setiap suku dikalikan satu sama lain lalu suku-suku dengan derajat yang sama dijumlahkan kembali, sehingga jumlah komputasinya membesar
    • Hasil dari (2x²+3x+4) × (5x²+6x+7) adalah 10x⁴+27x³+52x²+45x+28
    • Kompleksitas metode ini adalah O(n²), dan semakin besar derajatnya, semakin banyak perkalian yang diperlukan

Vektor koefisien dan konvolusi

  • Dalam domain diskret, konvolusi dua sinyal p dan q didefinisikan sebagai y[n]=Σ p[k]·q[n-k]
  • Perhitungannya dilakukan dengan membalik q, lalu menggesernya dari kiri ke kanan di atas p, sambil menjumlahkan hasil kali elemen yang saling tumpang tindih
  • Contoh sinyalnya adalah sebagai berikut
    • p = [2, 3, 4]
    • q = [5, 6, 7]
  • Jika q dibalik lalu digeser, setiap koefisien output terbentuk dalam urutan berikut
    • 2×5 = 10
    • 2×6 + 3×5 = 27
    • 2×7 + 3×6 + 4×5 = 52
    • 3×7 + 4×6 = 45
    • 4×7 = 28
  • Hasil konvolusinya adalah y = [10, 27, 52, 45, 28]
    • Ini sama dengan koefisien dari 10x⁴+27x³+52x²+45x+28 yang diperoleh melalui perkalian polinomial
    • Karena itu, perkalian polinomial dapat dilihat sebagai konvolusi vektor koefisien

Transformasi Fourier dan FFT

  • Transformasi Fourier mengubah sinyal dari domain waktu ke domain frekuensi
    • Dari sudut pandang waktu, sinyal dilihat sebagai nilai pada titik waktu tertentu
    • Dari sudut pandang frekuensi, sinyal ditafsirkan sebagai jumlah berbagai frekuensi osilasi yang berbeda
  • Frekuensi osilasi direpresentasikan dengan sinus dan kosinus, masing-masing memiliki koefisien dan fase
  • Jika FFT diterapkan pada gelombang sinus murni 5Hz, di domain frekuensi ia tampak seperti delta pada posisi 5Hz
    • Ini menunjukkan bahwa gelombang sinus di domain waktu dapat direpresentasikan oleh satu sinus 5Hz
  • Istilah terkait dibedakan sebagai berikut
    • Fourier Transform(FT): transformasi Fourier yang didefinisikan pada domain kontinu
    • Discrete Fourier Transform(DFT): transformasi Fourier yang didefinisikan untuk sinyal diskret
    • Fast Fourier Transform(FFT): algoritme yang menghitung DFT dalam O(n log n), bukan O(n²)
  • DFT mengubah sinyal waktu diskret x[n] menjadi X[k] di domain frekuensi
    • Setiap X[k] dihitung dengan mengalikan sampel input dengan bilangan kompleks yang merepresentasikan frekuensi tertentu, lalu menjumlahkannya

Mengubahnya menjadi perkalian di domain frekuensi

  • Keunggulan utama DFT dan domain frekuensi adalah konvolusi dapat diubah menjadi perkalian per elemen
    • Melakukan konvolusi dua sinyal di domain waktu sama dengan mengalikan dua sinyal di domain frekuensi
    • Perkalian dapat dihitung lebih cepat daripada konvolusi
  • Prosedur untuk melakukan perkalian polinomial dengan cepat adalah sebagai berikut
    • Ubah polinomial ke domain frekuensi dengan FFT: O(n log n)
    • Kalikan per elemen di domain frekuensi: O(n)
    • Ubah hasilnya kembali ke domain waktu dengan IFFT: O(n log n)
  • Secara keseluruhan, dengan menggunakan FFT, perkalian polinomial dapat dilakukan dengan kompleksitas O(n log n)
  • Untuk polinomial besar, ini lebih cepat daripada perkalian ala sekolah menengah O(n²)

Implementasi Python dan benchmark

  • multiply_naive menggunakan loop ganda untuk mengalikan semua pasangan koefisien dan menambahkannya ke posisi hasil i + j
    • Panjang hasilnya adalah len(p) + len(q) - 1
    • Kompleksitasnya adalah O(n²)
  • multiply_fft melakukan perkalian koefisien berbasis FFT/IFFT
    • Ia menghitung panjang berupa pangkat dua yang setidaknya sebesar len(p) + len(q) - 1 agar hasilnya dapat ditampung
    • Kedua input dipadding dengan np.pad
    • Nilai yang ditransformasikan dengan np.fft.fft dikalikan per elemen
    • Setelah dikembalikan dengan np.fft.ifft, bagian realnya dibulatkan dan dikonversi menjadi koefisien bilangan bulat
  • Pada contoh input p = [2, 3, 4], q = [5, 6, 7], kedua metode mengembalikan [10, 27, 52, 45, 28]
  • Dalam benchmark, metode FFT dibandingkan dengan multiply_convolve, yang menggunakan np.convolve, bukan multiply_naive
    • Ini karena loop Python pada multiply_naive lambat, sehingga sulit dibandingkan secara langsung dengan metode FFT yang menggunakan np.fft.fft
    • np.convolve melakukan operasi yang sama dengan kode C tingkat rendah
  • Derajat dinaikkan dalam rentang range(1, 30000, 1000), dan pada setiap derajat dibuat dua polinomial dengan koefisien acak antara 1 hingga 999999
    • Setiap metode diukur waktu rata-ratanya dengan n_runs = 5
    • Pada derajat rendah, metode FFT mungkin tidak menguntungkan karena biaya transformasi pulang-pergi FFT/IFFT
    • Ketika derajat meningkat, metode FFT menunjukkan hasil yang jauh lebih efisien

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-02
Komentar Hacker News

  • Yang selalu mengganggu dari penjelasan seperti ini adalah biasanya mereka melupakan galat numerik
    Perkalian koefisien tidak bisa begitu saja diabstraksikan sebagai “waktu konstan”. Kalau mau begitu, dari awal seluruh operasi perkalian juga bisa diabstraksikan dengan cara yang sama. Jika memperhitungkan presisi numerik, kompleksitasnya lebih mendekati O(n (log n)^3) [1]
    [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

    • Batas galat yang dikutip dalam tulisan itu terlalu pesimistis. Edisi terbaru Knuth sudah memuat batas yang benar, karena saya yang memberitahukannya
    • Akan bagus kalau operasi berbasis quaternion yang muncul di tulisan OP bisa dimanfaatkan untuk mengurangi galat perkalian, atau bahkan menghilangkannya sama sekali [1],[2],[3]
      [1] One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation:
      https://www.mdpi.com/2079-9292/12/24/4974
      [2] Convolution Theorems for Quaternion Fourier Transform: Properties and Applications:
      https://onlinelibrary.wiley.com/doi/10.1155/2013/162769
      [3] On the Matrix Form of the Quaternion Fourier Transform and Quaternion Convolution:
      https://arxiv.org/abs/2307.01836
    • Jika koefisiennya bilangan bulat, hasil yang eksak bisa diperoleh dengan NTT memakai modulus yang cukup besar, dan terutama di perangkat keras, waktu perkaliannya juga bisa menjadi lebih cepat
    • Karena itulah ilmu komputer dan rekayasa perangkat lunak dibedakan :)

  • Dengan metode ini, kita bisa mengalikan angka-angka panjang. Intinya adalah perkalian polinomial sama dengan perkalian angka panjang biasa tanpa carry
    Misalnya jika ada angka 1000 digit, setiap digit dijadikan koefisien dari polinomial dengan 1000 elemen. Lalu polinomial-polynomial ini bisa dikalikan dengan metode FFT yang dijelaskan dalam tulisan. Untuk mengubah hasilnya kembali menjadi angka, carry harus diproses. Jika suatu elemen lebih besar dari 10, kelebihannya diteruskan ke digit berikutnya, lalu koefisien-koefisiennya diubah menjadi angka
    Gagasan dasarnya seperti ini, dan ada bagian-bagian halus terkait presisi yang dibutuhkan untuk carry serta jaminan bahwa hasil FFT tetap benar jika dibulatkan ke bilangan bulat terdekat. Cara seperti inilah yang dipakai GMP, pustaka utama di bidang ini, untuk perkalian bilangan besar

    • Seperti yang disebutkan, bilangan desimal bisa direpresentasikan sebagai polinomial dengan x=10, jadi masuk akal. Misalnya 983 = 9x^2 + 8x + 3, yaitu [9, 8, 3]
      Saya penasaran seberapa besar angkanya agar ini benar-benar berarti, dan dipakai untuk apa

  • Kalau belum menontonnya, video ini bagus untuk dilihat
    https://youtu.be/h7apO7q16V0?si=bmgUEMTQSqU3flIv
    Video itu benar-benar luar biasa dalam menurunkan algoritma FFT dari perkalian polinomial. Saya menontonnya lagi kira-kira setiap 6 bulan

  • Sifat FFT bahwa “konvolusi adalah perkalian titik-demi-titik” juga berlaku pada grup perkalian siklik apa pun. Untuk penurunan yang lebih aljabar, lihat https://www.sciencedirect.com/science/article/pii/S002200007...
    Ini kadang disebut “FFT harmonik”, dan ada juga FFT non-harmonik: [LCH14] “additive NTT” di atas GF(2^n), [HLP24] circle FFT di atas lingkaran satuan X^2+Y^2=1 pada medan hingga, serta [BCKL21] ecfft di atas deret isogeni kurva eliptik
    [LCH14]: https://arxiv.org/abs/1404.3458
    [HLP24]: https://eprint.iacr.org/2024/278
    [BCKL21]: https://arxiv.org/pdf/2107.08473

  • Siapa orang pertama yang mengusulkan penggunaan FFT untuk perkalian polinomial yang lebih cepat?
    Belakangan saya penasaran dan mencoba mencarinya; meski tidak terlalu berhasil menelusuri sitasinya, saya bisa mundur sampai makalah David Eppstein tahun 1995 [0]. Di sana, ini digunakan untuk menyelesaikan masalah jumlah parsial secara efisien setelah pembaruan inkremental. Saya cukup yakin hal ini pasti sudah ada lebih awal di TAOCP milik Knuth
    Fakta bahwa masalah jumlah parsial eksak yang mengizinkan pengulangan bisa diselesaikan dalam waktu subeksponensial dengan perkalian polinomial FFT juga cukup mengejutkan [1]. Yang penting, algoritma ini O(N log N), tetapi N di sini bukan ukuran himpunan, melainkan elemen maksimum, jadi ini bukan semacam kontra-contoh untuk P ≠ NP
    [0] https://escholarship.org/content/qt6sd695gn/qt6sd695gn.pdf
    [1] https://x.com/festivitymn/status/1788362552998580473?s=46&t=...

  • Saya pikir semua machine learning adalah pekerjaan menyelesaikan persamaan konvolusi
    Makalah ini membahasnya dalam konteks reinforcement learning https://arxiv.org/abs/1712.06115, tetapi sebagian besar pendekatan cocok masuk ke paradigma ini

    • Bukankah itu pada dasarnya berarti metode kernel?

  • Saya baru saja mengimplementasikan algoritma (matrix profile) yang menggunakan FFT untuk menghitung inner product pada kumpulan besar subsekuens deret waktu. Panjang deret waktu n bisa mencapai ratusan juta
    Perhitungan konvolusi cepat dengan FFT mengurangi waktu komputasi dari O(n) menjadi O(log n), dan pada skala ini peningkatan kecepatannya luar biasa. Jika memakai GPU, bisa lebih cepat lagi, misalnya memproses 10 juta titik data dalam 0,1 detik di laptop

  • “Trik” inti operasi ini tampaknya adalah pemahaman berikut:

    Dengan kata lain, melakukan konvolusi dua sinyal di domain waktu sama dengan mengalikan dua sinyal di domain frekuensi.
    Ini tulisan bagus yang memecah ide rumit menjadi langkah-langkah yang jauh lebih kecil, sehingga bahkan saya yang lemah matematika pun entah bagaimana bisa memahaminya. Tapi apakah ada satu langkah di tengah yang terlewat? Atau sengaja ditinggalkan sebagai latihan untuk pembaca? Di titik itu saya sudah mengerahkan kemampuan matematika semaksimal mungkin, jadi rasanya agak seperti “lalu gambar sisa burung hantu sialan itu”. Cuma saya yang merasa begitu? Tulisannya sendiri benar-benar bagus

    • Entah ini membantu atau tidak: perkalian dua polinomial yang dipelajari di sekolah sebenarnya adalah konvolusi
      Ada sifat bahwa “melakukan konvolusi dua sinyal di domain waktu sama dengan mengalikan dua sinyal di domain frekuensi”, dan FFT memungkinkan kita mengubah dari domain waktu ke domain frekuensi. Jadi polinomial dipindahkan ke domain frekuensi dengan FFT, lalu di domain itu cukup dilakukan perkalian. Itu lebih cepat daripada konvolusi. Saya penasaran apakah ini memperjelas langkah yang hilang; kalau ada bagian yang terlewat, tulisannya bisa diperbarui

  • Kalau begitu, apakah faktorisasi bilangan bulat adalah dekonvolusi diskret? Saya penasaran apakah dengan menempatkan representasi FFT, yaitu operasi kebalikan dari perkalian titik demi titik, berdampingan dengan tableax, yaitu perkalian panjang biasa/penjumlahan carry, simetrinya bisa dipecah sehingga kita memperoleh informasi yang cukup untuk algoritma cepat

  • Tentu saja, perkalian polinomial secara naif lambat terhadap derajat polinomial. Namun, kapan sebenarnya kita perlu menangani dua polinomial derajat 100?
    Karena alasan ini, ada kesan bahwa sistem aljabar komputer tidak menggunakan metode seperti ini

    • Sistem aljabar komputer, misalnya chebfun di Matlab, mengubah fungsi arbitrer menjadi polinomial derajat 100 atau lebih agar lebih mudah menemukan akar, nilai optimum, dan sebagainya
    • Ini sangat umum dalam koreksi kesalahan dan pemrosesan sinyal
      https://www.youtube.com/watch?v=CcZf_7Fb4Us
      https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor... adalah salah satu contohnya
    • Karena ingin merekayasa balik parameter checksum CRC untuk berkas besar, saya membuat program[1] yang mengubah berkas menjadi polinomial GF(2) berderajat jutaan dan menghitung pembagi persekutuan terbesarnya. Tanpa perkalian berbasis FFT, ini mustahil dilakukan dalam waktu yang masuk akal
      [1]: https://github.com/8051enthusiast/delsum
    • Sudut pandang konvolusi seperti ini dan kernel GPU cepat untuk FFT digunakan dalam beberapa model state-space sebelum Mamba untuk pemodelan sekuens panjang; di sini polinomialnya adalah sekuens input
      Tulisan blog Hazy Research dari 2020–2023 memuat banyak informasi tentang pendekatan ini
    • Lihat https://news.ycombinator.com/item?id=40306339
      “(...) dalam riset fisika, saya pernah menangani ekspresi sepanjang hampir 1 terabyte dengan lebih dari 100 juta suku”