A transit-search pipeline records the brightness of a candidate host star at evenly…

PHYSICS · Multi-part · Fermi University Physics · Mathematical Methods for Physics · Computational Physics · Scientific programming for physicists

Scientific Computing for Physicists, Ch Spectra with error bars: the fast transform, convolution and spectral estimation

Problem

A transit-search pipeline records the brightness of a candidate host star at

N = 2^{16} = 65536

evenly spaced points before searching for planetary transits. ((a)) Starting from

X_k=\sum_{n=0}^{N-1}x_nW_N^{kn}

with

W_N=e^{-2\pi i/N}

, split the sum over even- and odd-indexed samples and derive

X_k=E_k+W_N^kO_k

and

X_{k+N/2}=E_k-W_N^kO_k

for

k=0,\dots,N/2-1

, where

E_k

O_k

are the length-

N/2

DFTs of the even and odd samples. Counting one operation per output sample for the multiply-and-combine step that produces

X_k

and

X_{k+N/2}

from

E_k

O_k

, write the recursion

T(N)=2T(N/2)+N

for the total number of operations, solve it for

N=2^m

, and evaluate

T(N)

N=65536

. ((b)) Before the transit search the light curve is smoothed with a boxcar (moving-average) filter of

M=121

points, by multiplying the two records' length-

L

DFTs and inverse transforming. Starting from the orthogonality relation

\frac{1}{L}\sum_{n=0}^{L-1}e^{2\pi i(k-k')n/L}=\delta_{kk'}

, prove that multiplying two length-

L

DFTs and inverse transforming produces the circular convolution (modulo

L

) of the two zero-padded length-

L

sequences. State the smallest

L

that makes this circular convolution equal the ordinary (linear) convolution of the

N

-point light curve with the

M

-point boxcar, and give the smallest power of two no less than that

L

, suitable for a radix-2 transform.