Biblioteca para transformada de Fourier en celosía triangular

11

Estoy buscando implementaciones razonablemente rápidas de la transformada discreta de Fourier (DFT) en una red 2D triangular o hexagonal.

Apreciaría los consejos para tales implementaciones (especialmente las que se pueden usar fácilmente desde Python o Mathematica), y también para las descripciones de cómo reducir este problema al 1D DFT, que ya está integrado en muchos sistemas.

Szabolcs
fuente
Esta es mi primera publicación aquí, agradecería un poco de ayuda para etiquetar la pregunta adecuadamente.
Szabolcs
2
Lo que parece necesitar aquí es una transformada cristalográfica de Fourier. Para referencias, hay esto , esto , esto y esto , pero tengo problemas para encontrar rutinas FORTRAN que se pueden descargar libremente. Puede que tenga que lanzar su propia implementación ...
JM
1
+1 para la pregunta. Creo que las etiquetas están bien por ahora; si alguien piensa que la pregunta debe etiquetarse de manera diferente, la editarán (si no pueden, le preguntarán a alguien que sí puede).
Geoff Oxberry
1
Esto , esto y esto son algunas referencias más que podrían ser útiles.
JM
1
@ Mark También he encontrado un par de referencias (antes de publicar), incluida la que Geoff proporcionó, pero no encontré ningún código de trabajo. Aún así, no he encontrado el término "transformada de Fourier cristalográfica". Esta es realmente una pregunta de un amigo que fue un poco tímido para publicar (pero también estoy interesado). El problema con las referencias es que es mucho trabajo leerlas y encontrar la correcta. Volveré eventualmente y publicaré sobre el resultado.
Szabolcs

Respuestas:

5

Hay varios documentos de Markus Püschel en su sitio web aquí que analizan algoritmos similares a Cooley-Tukey (así que supongo que son "rápidos") para las transformaciones de red, como los DFT en redes triangulares y hexagonales en 2-D. En el caso triangular, llama al DFT la transformada de triángulo discreto (DTT). Markus tiene un código llamado SPIRAL que genera automáticamente código para transformaciones, pero parece que este trabajo de TDT no es parte de SPIRAL, y no hay implementación en su sitio web que pueda encontrar. Estoy empezando a pensar que @JM tiene razón y que es posible que deba implementar su propia implementación.

Una cosa que los resúmenes señalan es que para las redes triangulares y hexagonales 2D, la transformación no se puede separar en componentes 1-D, por lo que no podrá reducir el problema a dos transformaciones 1-D.

Geoff Oxberry
fuente
Siempre me he preguntado en qué se diferencia esto de simplemente hacer una FFT común a lo largo de las direcciones de la red. ¿Es la ventaja que esto conserva simetrías? ¿Por qué es eso importante?
Victor Liu el
Sospecho que cuando forma su matriz circulante (¿anterior?) No tendrá las mismas propiedades agradables que antes. . . Mi comprensión de los FFT es que, debido a las simetrías y las auto-similitudes de la matriz de transformación, puede utilizar métodos de resolución realmente inteligentes.
meawoppl