11

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.

Szabolcs
  • 2,620
  • 2
  • 19
  • 34
  • This is my first post here, I'd appreciate some help in tagging the question appropriately. – Szabolcs Jan 17 '12 at 10:34
  • 2
    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... – J. M. Jan 17 '12 at 11:38
  • 1
    +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). – Geoff Oxberry Jan 17 '12 at 11:42
  • I like this question too. I'm now interested in seeing an easily-obtainable implementation of crystallographic FTs myself... – J. M. Jan 17 '12 at 11:45
  • 1
    This, this, and this are a few more references that might be of use. – J. M. Jan 17 '12 at 13:22
  • @J.M. - Why post these as comments? They look like the basis for a worthwhile answer. – Mark Booth Jan 17 '12 at 14:41
  • @J.M. I agree with Mark, even if it's just a list of refs, it'd be worthwhile posting them as an answer. Comments are too volatile. Otherwise I was considering editing them into the question tomorrow. – Szabolcs Jan 17 '12 at 14:52
  • @Mark and Szabolcs: what Szabolcs said is sorta kinda the reason why I left 'em as comments. The letter of your question asks about implementations, as opposed to references. Although some of them do mention sundry FORTRAN code, I have been hard-pressed to find actual code. I'll think about it for a bit if I can make a decent answer out of a bunch o' links... – J. M. Jan 17 '12 at 14:56
  • @J.M. I understand your reticence, but I think your answer would be no less likely to be considered useful than Geoff's answer, which already has several upvotes, especially if you quote the relevant parts of the abstracts. You can always edit in more info later if you find it. – Mark Booth Jan 17 '12 at 15:23
  • 1
    @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. – Szabolcs Jan 17 '12 at 15:43
  • @Szabolcs - Yup, that's why abstract extracts can be really useful in helping reference type answers to provide immediate useful information. – Mark Booth Jan 17 '12 at 15:47
  • "The problem with references is that it's a lot of work to read them" - agreed. I had worked on this before for a pet project, but 1. what I wrote wasn't really fit for public consumption; and 2. I lost the code, since this was quite a long time ago. What I linked to were the papers I referred to when I was working on this. Unless you beat me to it, I might be able to do a decent summary of some of those, if that's fine and dandy... – J. M. Jan 17 '12 at 15:50
  • @J.M. Of course that's useful, but please do not spend much time on this. When I originally posted I thought there might be an existing library. I do not know how much time we'll spent on implementing this from scratch, as it is not essential for what we were doing ... – Szabolcs Jan 17 '12 at 16:02
  • @J.M. I agree with @MarkBooth; I think adding references is the best that can be done at the moment, and your references are useful also. If you post them as an answer, I'd upvote them. (I upvoted your comment.) – Geoff Oxberry Jan 18 '12 at 14:16
  • Good question! Is there a major downside to oversampling to a square-grid and then using a standard rectangular implementation? – meawoppl Mar 02 '12 at 23:46

1 Answers1

6

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.

Geoff Oxberry
  • 30,394
  • 9
  • 64
  • 127
  • 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? – Victor Liu Jan 19 '12 at 11:03
  • 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. – meawoppl Mar 02 '12 at 23:43