Biblioteka transformacji Fouriera na sieci trójkątnej

11

Szukam dość szybkich implementacji dyskretnej transformaty Fouriera (DFT) na trójkątnej lub heksagonalnej sieci 2D.

Byłbym wdzięczny za wskazówki dotyczące takich implementacji (szczególnie tych, które można łatwo wykorzystać z Pythona lub Mathematiki), a także opisów, jak zredukować ten problem do 1D DFT, który jest już wbudowany w wiele systemów.

Szabolcs
źródło
To jest mój pierwszy post tutaj, byłbym wdzięczny za pomoc w odpowiednim oznaczeniu pytania.
Szabolcs
2
Wydaje się, że potrzebujesz tutaj krystalograficznej transformacji Fouriera. Dla odniesienia jest to , to , to i to , ale mam problem ze znalezieniem procedur FORTRAN, które można pobrać za darmo. Może być konieczne wdrożenie własnej implementacji ...
JM
1
+1 za pytanie. Myślę, że na razie tagi są w porządku; jeśli ktoś uważa, że ​​pytanie powinno być oznaczone inaczej, to je edytuje (jeśli nie może, zapyta kogoś, kto może).
Geoff Oxberry
1
To , to i to jeszcze kilka referencji, które mogą się przydać.
JM
1
@ Mark Znalazłem również kilka odnośników (przed wysłaniem), w tym ten podany przez Geoffa, ale nie znalazłem żadnego działającego kodu. Mimo to nie znalazłem terminu „krystalograficzna transformata Fouriera”. To jest właściwie pytanie znajomego, który był nieco nieśmiały, aby opublikować (ale jestem również zainteresowany). Problem z referencjami polega na tym, że przeczytanie ich i znalezienie właściwego jest dużo pracy. Wrócę w końcu i piszę o wyniku.
Szabolcs

Odpowiedzi:

5

Na jego stronie internetowej znajduje się kilka artykułów Markusa Püschela , które omawiają podobne do Cooleya-Tukeya (więc zgaduję „szybkie”) algorytmy transformacji sieci, takie jak DFT na trójkątnych i heksagonalnych sieciach 2D. W przypadku trójkąta nazywa DFT dyskretną transformatą trójkąta (DTT). Markus ma kod o nazwie SPIRAL, który automatycznie generuje kod do transformacji, ale wydaje się, że ta praca DTT nie jest częścią SPIRAL i nie ma implementacji na jego stronie internetowej, którą mogę znaleźć. Zaczynam myśleć, że @JM ma rację i że może być konieczne wdrożenie własnej implementacji.

Jedną rzeczą, na którą zwracają uwagę streszczenia, jest to, że w przypadku trójwymiarowych sieci trójkątnych i heksagonalnych 2-transformacji transformacji nie da się rozdzielić na komponenty 1-D, więc nie będzie można zredukować problemu do dwóch transformacji 1-D.

Geoff Oxberry
źródło
Zawsze zastanawiałem się, jak to się różni od zwykłego wykonywania FFT wzdłuż kierunków bazowych sieci. Czy zaletą jest to, że pozwala to zachować symetrię? Dlaczego to takie ważne?
Victor Liu,
Podejrzewam, że kiedy utworzysz swoją (wcześniej?) Macierz krążącą, nie będzie miała takich samych dobrych właściwości jak poprzednio. . . Rozumiem FFT, ponieważ ze względu na symetrie i samopodobieństwo macierzy transformacji można korzystać z naprawdę inteligentnych metod rozwiązywania.
meawoppl