[Ifeffit] more fun with FFTs

[Grant Bunker]

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 at millenia.cars.aps.anl.gov wrote:

> Send Ifeffit mailing list submissions to
> 	ifeffit at 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 at millenia.cars.aps.anl.gov
>
> You can reach the person managing the list at
> 	ifeffit-owner at 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 <newville at cars.uchicago.edu>
> Subject: Re: [Ifeffit] FFT in Ifeffit
> To: XAFS Analysis using Ifeffit <ifeffit at millenia.cars.aps.anl.gov>
> Message-ID: <Pine.LNX.4.44.0406072214290.13810-100000 at corvette>
> 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 at millenia.cars.aps.anl.gov
> > http://millenia.cars.aps.anl.gov/mailman/listinfo/ifeffit
> >
>
>
>
> ------------------------------
>
> _______________________________________________
> Ifeffit mailing list
> Ifeffit at millenia.cars.aps.anl.gov
> http://millenia.cars.aps.anl.gov/mailman/listinfo/ifeffit
>
>
> End of Ifeffit Digest, Vol 16, Issue 7
> **************************************
>