11
$\begingroup$

I am looking for reasonably fast implementations of the discrete Fourier transform (DFT) on a 2D triangular or hexagonal lattice.

I would appreciate pointers to such implementations (especially ones easily usable from Python or Mathematica), and also to descriptions of how to reduce this problem to the 1D DFT, which is already built into many systems.

$\endgroup$
  • $\begingroup$ This is my first post here, I'd appreciate some help in tagging the question appropriately. $\endgroup$ – Szabolcs Jan 17 '12 at 10:34
  • 2
    $\begingroup$ What you seem to need here is a crystallographic Fourier transform. For references, there's this, this, this, and this, but I'm having trouble finding FORTRAN routines that one can download freely. You might have to roll your own implementation... $\endgroup$ – J. M. Jan 17 '12 at 11:38
  • 1
    $\begingroup$ +1 for the question. I think the tags are fine for now; if someone thinks the question should be tagged differently, they'll edit it (if they can't, they'll ask someone who can). $\endgroup$ – Geoff Oxberry Jan 17 '12 at 11:42
  • 1
    $\begingroup$ This, this, and this are a few more references that might be of use. $\endgroup$ – J. M. Jan 17 '12 at 13:22
  • 1
    $\begingroup$ @Mark I have found a couple of references as well (before posting), including the one given by Geoff, but I did not find any working code. Still, I haven't found the term "crystallographic Fourier transform". This is actually a question by a friend who was a bit shy to post (but I'm also interested). The problem with references is that it's a lot of work to read them and find the right one. I'll come back eventually and post about the outcome. $\endgroup$ – Szabolcs Jan 17 '12 at 15:43
5
$\begingroup$

There are several papers by Markus Püschel on his web site here that discuss Cooley-Tukey-like (so I'm guessing "fast") algorithms for lattice transforms, such as DFTs on triangular and hexagonal 2-D lattices. In the triangular case, he calls the DFT the discrete triangle transform (DTT). Markus has a code called SPIRAL that automatically generates code for transforms, but it appears that this DTT work is not part of SPIRAL, and there is no implementation on his web site that I can find. I'm beginning to think that @J.M. is right and that you might need to roll your own implementation.

One thing that the abstracts note is that for 2-D triangular and hexagonal lattices, the transform is not separable into 1-D components, so you won't be able to reduce the problem to two 1-D transforms.

$\endgroup$
  • $\begingroup$ I have always wondered how this is different than just doing an ordinary FFT along the lattice basis directions. Is the advantage that this preserves symmetries? Why is that important? $\endgroup$ – Victor Liu Jan 19 '12 at 11:03
  • $\begingroup$ I suspect when you form your (previously?) circulant matrix it won't have the same nice properties as before. . . My understanding of FFT's is that because of the symmetries and self-similarities of the transformation matrix you can make use of really intelligent solving methods. $\endgroup$ – meawoppl Mar 2 '12 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.