[Ifeffit] more fun with FFTs

Just to amplify Matt's remarks - the purpose of padding with zeros is to deliver a finer grid in r-space. There is a relationship between the r-space grid dr, the k-space grid dk, and the number of points in the array (N): N dk dR = Pi. So, for a k-space grid of .05/A and 2048 points, you get an r-grid spacing of .0307 A. This gives pretty good sampling of the fourier transform. If you only use say 256 points in your array (i.e. you don't pad with zeroes) the r-space sampling is .245 A, which is too coarse to be useful. You might ask whether zero padding botches up the data. It can be shown (I worked it out once) that zero padding is exactly equivalent to an interpolation of the unpadded data witha specific interpolation kernel (a sinc function or something as I recall). What happens is that as you pad with more zeros into a longer array, the sampling in r-space increases, and ultimately the curve looks just like what you would get with a continuous fourier transform (with cutoff effects from the finite k-space window). grant On Tue, 8 Jun 2004 ifeffit-request@millenia.cars.aps.anl.gov wrote:

Send Ifeffit mailing list submissions to ifeffit@millenia.cars.aps.anl.gov

To subscribe or unsubscribe via the World Wide Web, visit http://millenia.cars.aps.anl.gov/mailman/listinfo/ifeffit or, via email, send a message with subject or body 'help' to ifeffit-request@millenia.cars.aps.anl.gov

You can reach the person managing the list at ifeffit-owner@millenia.cars.aps.anl.gov

When replying, please edit your Subject line so it is more specific than "Re: Contents of Ifeffit digest..."

Today's Topics:

1. Re: FFT in Ifeffit (Matt Newville)

----------------------------------------------------------------------

Message: 1 Date: Mon, 7 Jun 2004 22:55:28 -0500 (CDT) From: Matt Newville Subject: Re: [Ifeffit] FFT in Ifeffit To: XAFS Analysis using Ifeffit Message-ID: Content-Type: TEXT/PLAIN; charset=US-ASCII

Hi Scott,

All Fourier transforms in Ifeffit use arrays of length 2048, padding with zeros as needed.

In earlier versions of Feffit, doing repeated FTs in the fitting loop was noticeably slow. This is probably one of the reasons fitting in R-space was uncommon. Anyway, using arrays of length N_fft = 1024, 512, or 256 definitely helped speed things up.

In principle, one could use N_fft ~= N_idp, but it turns out that if you use too few FT points, you can easily get into a real 'false, local, minima'. So Feffit used 1024,512,or 256 for fits, and then go back to 2048 to write out the data. Strictly speaking, the FFT doesn't need to use an array size that is a power of 2, but it turns out to make a very noticeable difference with the FFT routines used.

With Ifeffit, several "anti-optimizations" were made that make the fits slightly slower but be more straightforward and simple (relatively speaking, anyway!). The use of double precision and N_fft=2048 being the main examples. Part of the reason for sticking with 2048 is that you want to be able to view the data at any point in the process so 'pretty output' is always needed. Also, I doubt many people will be trying to run artemis on a 386 or a microVAX.

--Matt

...

As I was working on my talk for the EXAFS workshop, I came across a rather technical question: how does Ifeffit choose the number of points for the Fourier transforms? As I recall, FEFFIT used an algorithm which required an integer power of 2, so its default behavior was to use the smallest integer power of 2 greater than the number of points in the chi(k) data, and then pad the rest with 0's. This default behavior could also be over-ridden if desired.

It doesn't look to me like Ifeffit is handling that in the same way--is it always using a very large number of points and padding with 0's, or is it using an algorithm that doesn't require the integer power of 2, or is it interpolating the chi(k) on to a grid of the appropriate size first, or...?

I appreciate any info you can give me on this.

--Scott Calvin Sarah Lawrence College _______________________________________________ Ifeffit mailing list Ifeffit@millenia.cars.aps.anl.gov http://millenia.cars.aps.anl.gov/mailman/listinfo/ifeffit

------------------------------

_______________________________________________ Ifeffit mailing list Ifeffit@millenia.cars.aps.anl.gov http://millenia.cars.aps.anl.gov/mailman/listinfo/ifeffit

End of Ifeffit Digest, Vol 16, Issue 7 **************************************