Fast Chi-squared Period Search

Introduction

This is the Website for the Fast Chi-Squared Algorithm, a fast, powerful technique for detecting periodicity. It was developed for analyzing variable stars, but is applicable to many of the other applications where the Fast Fourier Transforms (FFTs) or other periodograms (such as Lomb-Scargle) are currently used.

The Fast Chi-squared technique takes a data set (e.g. the brightness of a star measured at many different times during a series of observations) and finds the periodic function that has the best frequency and shape (to an arbitrary number of harmonics) to fit the data.

Among its advantages are

Statistical efficiency: all of the data are used, weighted by their individual error bars, giving a result with a significance calibrated in well-understood Chi-squared statistics.
Sensitivity to harmonic content: many conventional techniques look only at the significance (or the amplitude) of the fundamental sinusoid and discard the power of the higher harmonics.
Insensitivity to the sample timing: you won't find a period of 24 hours just because you take your observations at night. You do not need to window your data.
The frequency search is gridded more tightly than the traditional "integer number of cycles over the span of observations", eliminating power loss from peaks that fall between the grid points.
Computational speed: The complexity of the algorithm is O(NlogN), where N is the number of frequencies searched, due to its use of the FFT.

A more complete description of the algorithm is given in Palmer, D.M., 2009 (ApJ, vol. 695, p496-502 ; arXiv:0901.1913; doi: 10.1088/0004-637X/695/1/496) "A Fast Chi-squared Technique For Period Search of Irregularly Sampled Data."

Reference Implementation

An implementation of this algorithm can be downloaded as this tarball, which includes source code (released under the GPL), makefiles, and test data. It has been tested under Mac OS X, Linux, and Windows (under Cygwin). The current version is 1.03 as of 2010-08-04, with a modification history given by this changelog.

Installation

This software uses the Gnu Scientific Library to implement the FFT and linear algebra components of the algorithm. If you do not have this library and associated header files, they can be installed from source or by using a package manager, e.g.

Mac OS X	% `fink install gsl`
Ubuntu Linux	% `sudo apt-get install libgsl0-dev`
Redhat Linux	% `sudo apt-get install libgsl-devel`
Windows with Cygwin	use setup.exe to install libs->gsl-devel

Download the tarball FastChi2-1.03.tar.gz to a destination directory and extract it, which produces a subdirectory named FastChi2-1.03. Cd to that directory and run make to compile it.

The complete installation process, described in the INSTALL file, should look something like this:


            % tar xzf FastChi2-1.03.tar.gz 
        
    % cd FastChi2-1.03
        
    % make
        
    cc `gsl-config --cflags` -O3   -c -o fastchi2.o fastchi2.c
        
    cc `gsl-config --cflags` -O3   -c -o chi2driver.o chi2driver.c
        
    which gsl-config
        
    /sw/bin/gsl-config
        
    cc -o runchi2 fastchi2.o chi2driver.o `gsl-config --libs`

After the program has been compiled, the executable, named runchi2, is in the current directory. It may be executed where it is, or manually moved to a binary directory in your PATH.

Testing and Understanding

To test that the code is working, make check. This creates a temporary directory /tmp/fastchi2/ which has the results of running the program on sample data from the Hipparcos spacecraft's observations of variable stars.


            % make check
        
    # run test suites, exiting non-zero if they fail, printing diagnostics
        
    cd testdata && ./runtest
        
    Usage: ./../runchi2 nharmonics freqmax
        
    	[-f freqmin]
        
    	[-d detrendorder]
        
    	[-t t0]
        
    	[-T timespan]
        
    	[-s oversampling]
        
    	[-m chi2margin]
        
    	[-i infile]
        
    	[-o outfile]
        
    	[-O outfile_with_frequency_adjustment]
        
    	[-e stderrfile]
        
    	[-D diagnosticfile]
        
    	[-c 'comment string']
        
    
        
    Now running on 187 Hipparcos periodic variables.
        
    On a ~2.5 GHz machine this takes roughly 1 second per star.
        
    
        
    + pwd
        
    /tmp/FastChi2-1.03/testdata
        
    + ./../runchi2 3 12 -i ./heptest.in -O /tmp/fastchi2/heptest.out -e /tmp/fastchi2/heptest.err
        
    
        
    real	1m17.161s
        
    user	1m17.051s
        
    sys	0m0.095s
        
    + set +x
        
    
        
    Of 174 stars with nominal periods from this data or the 
        
    previous literature, runchi2 identifies:
        
       71 at the nominal period (+/- 1e-4 cycles/day or 1%)
        
       23 at the 1/2 period alias
        
       25 at the 2x period alias
        
       25 at the 3x period alias
        
    (Some variation may occur on different machines, using different versions of
        
    compilers and libraries.  The reference run has 174 stars,
        
    with 71, 23, 25, and 25 matching periods)
        
    This indicates that the software build  PASSES
        
    %

To unpack this a bit:

The file testdata/heptest.in contains brightness measurements (roughly 100 samples each) made by Hipparcos for each of 187 stars with known periodic variation. File formats and descriptions of the arguments are in the README file. Not all of these stars have valid data or Hipparcos periods listed, for various reasons, but 174 of them do.

The executable runchi2 is run on this input file to search each star for the best third-harmonic fit at frequencies up to 12 cycles/day. The output files are stored in the /tmp/fastchi2 directory.

Comparing the output of the program to the original Hipparcos periods finds that 40% of these stars have their best chi-squared improvement at periods consistent with those in the Hipparcos catalog. A comparable number are found at harmonically related frequencies, for a yield of more than 80%. (The periods listed in the Hipparcos catalog are sometimes derived using additional data beyond that analyzed here.)

Distinguishing the 'true' fundamental frequency from alias frequencies at small integer ratios that have formally better fits requires further analysis informed by an understanding of the physical system involved. For example, an eclipsing binary comprising two similar stars will tend to be better-fit at the 1/2 period alias due to the symmetry of the light curve. See the original paper for more details.

The make check run stores its results in the file /tmp/fastchi2/heptest.periods on your computer. This gives the HIP catalog number, the Hipparcos derived period, the Fast-Chi-squared period, and the ratio of the two. The Hipparcos website includes a Java applet light curve plotter that allows you to plot the Hipparcos Epoch Photometry data as a function of phase for any period you choose. Comparing light curves at the published period versus the period from the Fast Chi-Squared algorithm will help you understand why the program finds the results it does.

For More Information

For questions about this website, or about details of this program or algorithm that are not included in the original paper, I may be reached at .

David Palmer: The Fast Chi-squared Period Search

Introduction

Reference Implementation

Installation

Testing and Understanding

For More Information