Perpustakaan untuk transformasi Fourier pada kisi segitiga

11

Saya mencari implementasi yang cukup cepat dari transformasi Fourier diskrit (DFT) pada kisi segitiga atau heksagonal segitiga 2D.

Saya akan menghargai petunjuk untuk implementasi tersebut (terutama yang mudah digunakan dari Python atau Mathematica), dan juga untuk deskripsi bagaimana mengurangi masalah ini ke DFT 1D, yang sudah dibangun ke dalam banyak sistem.

Szabolcs
sumber
Ini adalah posting pertama saya di sini, saya sangat menghargai bantuan dalam menandai pertanyaan dengan tepat.
Szabolcs
2
Apa yang Anda butuhkan di sini adalah transformasi Fourier kristalografi. Sebagai referensi, ini , ini , ini , dan ini , tapi saya kesulitan menemukan rutinitas FORTRAN yang dapat diunduh secara bebas. Anda mungkin harus memutar implementasi Anda sendiri ...
JM
1
+1 untuk pertanyaan. Saya pikir tag baik-baik saja untuk saat ini; jika seseorang berpikir bahwa pertanyaan harus diberi tag berbeda, mereka akan mengeditnya (jika tidak bisa, mereka akan bertanya kepada seseorang yang bisa).
Geoff Oxberry
1
Ini , ini , dan ini adalah beberapa referensi lagi yang mungkin berguna.
JM
1
@ Mark Saya telah menemukan beberapa referensi juga (sebelum posting), termasuk yang diberikan oleh Geoff, tetapi saya tidak menemukan kode yang berfungsi. Namun, saya belum menemukan istilah "transformasi Fourier kristalografi". Ini sebenarnya pertanyaan oleh seorang teman yang agak malu untuk mengirim (tapi saya juga tertarik). Masalah dengan referensi adalah bahwa banyak pekerjaan untuk membacanya dan menemukan yang tepat. Saya akhirnya akan kembali dan memposting tentang hasilnya.
Szabolcs

Jawaban:

5

Ada beberapa makalah oleh Markus Püschel di situs webnya di sini yang membahas algoritma Cooley-Tukey (jadi saya kira "cepat") untuk transformasi kisi, seperti DFT pada kisi 2-D segitiga dan heksagonal. Dalam kasus segitiga, ia menyebut DFT transformasi segitiga diskrit (DTT). Markus memiliki kode yang disebut SPIRAL yang secara otomatis menghasilkan kode untuk transformasi, tetapi tampaknya pekerjaan DTT ini bukan bagian dari SPIRAL, dan tidak ada implementasi di situs webnya yang dapat saya temukan. Saya mulai berpikir bahwa @ JM benar dan Anda mungkin perlu menjalankan implementasi Anda sendiri.

Satu hal yang dicatat oleh abstrak adalah bahwa untuk kisi segitiga dan heksagonal 2-D, transform tidak dapat dipisahkan menjadi komponen 1-D, sehingga Anda tidak akan dapat mengurangi masalah menjadi dua transformasi 1-D.

Geoff Oxberry
sumber
Saya selalu bertanya-tanya bagaimana ini berbeda dari sekedar melakukan FFT biasa di sepanjang arah dasar kisi. Apakah keuntungan mempertahankan simetri ini? Mengapa itu penting?
Victor Liu
Saya curiga ketika Anda membentuk matriks sirkuler (sebelumnya?) Anda tidak akan memiliki properti bagus yang sama seperti sebelumnya. . . Pemahaman saya tentang FFT adalah karena simetri dan kemiripan diri dari matriks transformasi Anda dapat menggunakan metode pemecahan yang benar-benar cerdas.
meawoppl