Biblioteca para transformada de Fourier na estrutura triangular

11

Estou procurando implementações razoavelmente rápidas da transformada de Fourier discreta (DFT) em uma estrutura triangular ou hexagonal 2D.

Eu gostaria de receber sugestões de tais implementações (especialmente aquelas facilmente utilizáveis ​​em Python ou Mathematica) e também de descrições de como reduzir esse problema ao 1D DFT, que já está incorporado em muitos sistemas.

libraries fourier-analysis Szabolcs
fonte
Este é o meu primeiro post aqui, eu gostaria de receber alguma ajuda para marcar a pergunta adequadamente.
Szabolcs
2
O que você parece precisar aqui é de uma transformada de Fourier cristalográfica. Para referências, há isto , isto , isto e isto , mas estou tendo problemas para encontrar rotinas FORTRAN que podem ser baixadas livremente. Você pode ter que rolar sua própria implementação ...
JM
1
+1 para a pergunta. Eu acho que as tags estão boas por enquanto; se alguém achar que a pergunta deve ser marcada de maneira diferente, ela será editada (se não puder, perguntará a alguém que pode).
precisa saber é o seguinte
1
Isto , isto e isto são mais algumas referências que podem ser úteis.
JM
1
@ Mark Também encontrei algumas referências (antes de postar), incluindo a fornecida por Geoff, mas não encontrei nenhum código de trabalho. Ainda não encontrei o termo "transformada de Fourier cristalográfica". Esta é realmente uma pergunta de um amigo que era um pouco tímido para postar (mas também estou interessado). O problema com as referências é que é muito trabalhoso lê-las e encontrar a correta. Voltarei eventualmente e publicarei sobre o resultado.
Szabolcs

Respostas:

5

Existem vários artigos de Markus Püschel em seu site aqui que discutem algoritmos do tipo Cooley-Tukey (então, acho que "rápidos") para transformações de rede, como DFTs em redes 2-D triangulares e hexagonais. No caso triangular, ele chama a DFT de transformada em triângulo discreto (TDT). Markus tem um código chamado SPIRAL que gera automaticamente código para transformações, mas parece que esse trabalho de TDT não faz parte do SPIRAL e não há nenhuma implementação em seu site que eu possa encontrar. Estou começando a pensar que o @JM está certo e que você pode precisar implementar sua própria implementação.

Uma coisa que os resumos observam é que, para treliças triangulares e hexagonais 2-D, a transformação não é separável em componentes 1-D, portanto, você não poderá reduzir o problema para duas transformações 1-D.

Geoff Oxberry
fonte
Eu sempre me perguntei como isso é diferente do que apenas fazer uma FFT comum ao longo das direções da base de treliça. A vantagem é que isso preserva simetrias? Por que isso é importante?
Victor Liu
Eu suspeito que, quando você formar sua matriz circulante (anteriormente?), Ela não terá as mesmas boas propriedades de antes. . . Meu entendimento das FFT é que, devido às simetrias e auto-semelhanças da matriz de transformação, você pode fazer uso de métodos de solução realmente inteligentes.
precisa saber é