Mock LISA Data Challenge -- Round 1

Results and Analysis from NASA Ames Research Center

David E. Thompson ([dethompson@mail.arc.nasa.gov]{.underline})

and

Rajkumar Thirumalainambi (<rajkumar@mail.arc.nas.gov>)

## Introduction

The Mock LISA Data Challenges (MLDC) consist in extracting the maximum
amount of information about the binary source(s) that generate
gravitational wave signal(s) contained in the (mock) data sets that were
distributed in late June 2006. The goals of this Challenge are: (1) to
foster the development and validation of building blocks of, and basic
tools for, LISA data analysis; and (2) to tackle analysis of data sets
containing a single signal or non-overlapping multiple signals embedded
in Gaussian and stationary noise, with no contribution from galactic
and/or extragalactic foregrounds.

The basic LISA response to gravitational waves can either be the *phase
response* used in the *LISA Simulator* or the *fractional frequency
response* used in *Synthetic LISA.* The phase and fractional frequency
formalisms are equivalent, and related by simple time integration. Both
data streams are distributed for the Challenges. The frequency
measurements have the advantage of being directly proportional to the
gravitational strain; the phase measurements have the advantage of
representing more closely the actual output of the LISA parameters. In
our approach, we focus on the LISA Simulator data sets (phase response)
for **Challenges 1.1.1a, 1.1.1b, 1.1.2, and 1.1.3**. We skipped over
Challenge 1.1.1c because the frequency range near 10mhZ is beyond the
low-pass filter range in the MLDC_galactic.c code (which is apparently
tailored to sources less than 5mHz). We did not attempt to create or
select an alternate high-pass filter code at this time. We do however
adopt the MLDC_galactic.c code in its entirety as provided by the
Challenge Team. We would like to have covered more of the Challenge --
Round 1; but due to extensive time in ramping up and in running multiple
simulations, we ran out of time before the 1 December 06 deadline. We
are however continuing on the remaining parts for Round 1, and are
awaiting the release of Round 2.

The approach adopted is user-refined multi-dimensional grid search
method, with prior FFTs to locate possible best-guess source frequencies
used to initiate search. This is a minor refinement of the exhaustive
grid search method in the MLDC_galactic.c code, and our modifications
are discussed below. Our concern has been to *succeed* in reproducing
correct results through use the provided exhaustive grid search methods
before trying to optimize the code or otherwise consider alternative
signal extraction methods. Our metrics for "correctness" are stability
in the converged frequency at the 9^th^ to 12^th^ significant figure
between search simulations; converged signal to noise ratio (SNR) of
greater than 15; and a converged positive log-likelihood value. These
values are provided in the MLDC code by the 'get_SNR_logL' routine
within the MLDC code's parameter search loops. Our deployment of the
code on various machines is discussed below; we are also attempting a
benchmarking of systems for these searches.

## Derived Parameters for the Challenges

LISA Challenge data are 1-year records with a sampling cadence of every
15seconds. A typical non-coalescing galactic binary system is described
by seven parameters, namely the amplitude, frequency, HEC colatitude,
HEC longitude, polarization angle, binary source inclination wrt
line-of-sight direction, and initial orbital phase. To describe more
complicated binary systems that change in time will require additional
parameters such as orbit eccentricity and first and second derivatives
of the frequency. In Challenges 1.1.1a and b, and in the verification
and resolvable binary Challenges (1.1.2 and 1.1.3), these seven
parameters are derived based on our modified multi-dimensional grid
search method. Both from published literature and from personal
conversations with Team members, we recognize that these seven
parameters can be conveniently divided into two categories, namely
stationary and non-stationary ones. During our search process, we have
effectively "separated" (stationary) frequency, theta, and phi from the
other parameters, and these are made to converge first (holding psi,
iota, and iphase outside the search). Once these three parameters are
stable in SNR and log-likelihood, their values are held (roughly)
constant while convergence is sought for psi, iota, and iphase. SNR and
log-likelihood continue to improve and refine. Finally, the amplitude is
found in a one-step search; the range is restricted to a range of
10^-21^ to 10^-25^ based on realistic physics. The details of our grid
search refinement are discussed in a following section.

## Initial Identification of signals based on FFT

The response of a space-borne instrument to a gravitational wave source
is encoded in the Michelson-like time-delay interferometry (TDI)
variables X, Y, Z. Rather than work with the correlated variables
directly, the MLDC_galactic.c code provides the signal combination
channels 'A' and 'E' to identify the signals. The A, E combinations
cancel the laser phase (shot noise) that would otherwise dominate the
Michelson signals; they are effectively orthogonal mappings of the
triangular (X,Y,Z) references into a Cartesian framework. The A and E
time-series are constructed based on the following equations:

> $$\begin{array}{r}
> A = \frac{2X - Y - Z}{3} \\
> E = \frac{Z - Y}{\sqrt{3}}
> \end{array}$$

Once A and E are created, we apply Matlab FFT routines to the A and E
time-series, and the power spectrum of the time series is computed based
on the resultant absolute value. The Figures 1 and 2 shows the power
spectrum of A and E for Challenges 1.1.1a and b. Since we know the
frequency range for specific challenges from MLDC, we focused on
narrowed frequency ranges. As an initial guess from Figures 1 and 2, a
center frequency and structurally driven range is selected for the
respective Challenges.

![](media/image1.jpeg){width="4.497222222222222in"
height="3.377083333333333in"}

**Figure 1**: Challenge 1.1.1a Power Spectrum of A and E channels

![](media/image2.jpeg){width="4.497222222222222in"
height="3.372916666666667in"}

**Figure 2**: Challenge 1.1.1 b Power Spectrum of A and E channels

Note that for Challenge 1.1.1a, the signal structure is very simple
compared to that for Challenge 1.1.1b. From Figure 1 and 2, the A and E
power spectra structure determines the cutoff frequency search range. In
Figure 2, there are various secondary peaks, and it is hard to visually
identify which frequency should be considered as an initial guess. We
start with the highest peak value in the power spectrum from A and E,
and the width for frequency search includes the entire relevant signal
structure (not just width at half-max, for example).

Challenges 1.1.2 and 1.1.3 provide a different issue not just because of
20 signals in the blind datasets (and for 1.1.2, do we "see" all 20
given sources), but also due to close proximity and overlap in the
signal structure in the frequency space for the resolvable binaries in
1.1.3. However, our initial approach is the same; that is, carry out FFT
on the A and E time-series and look for sources. Then select center
frequency and ranges for the search, and select starting values for the
other parameters. Derive f, theta, and phi first; derive psi, iota, and
iphase next; converge amplitude last, and check for continual
improvement in SNR and LogL.

# System Specifications

Challenge 1.1.1a and b were launched on our division's Sun Server that
has 8 x 900MHz processors with 16 GB RAM. In the Sun Sparc Server, one
CPU is allocated with 12.45 percent usage (maximum) limit for each
search process. Because of this obligatory low usage allocation, many
hours (days) were consumed in order to extract the stationary and
non-stationary source parameters. Typically 12-17 simulation runs were
made per challenge, each with a justifiable user-defined improvement in
grid refinement, and using previously converged values of the respective
parameters to restart the search in the next simulation. Because of the
long time needed for such runs, we sought a cluster node approach in
order to run the 20 source searches in Challenges 1.1.2 and 1.1.3.

We performed Challenges 1.1.2 and 1.1.3 with our available Red Hat Linux
cluster system to achieve greater speed in extracting the source
parameters. Each GW source was assigned a specific node, so that all 20
runs could be done in parallel. However, there is obviously no
interaction between the 20 searches, so each is a single thread. The
cluster system has a central server with 2GB RAM, currently with 40
nodes (2 processors per node), 20 nodes of which are allocated to our
MLDC project. Each node has 1GB RAM/node with AMD Athlon(tm) MP 2600+
(2200 MHz) processor. Onboard cache is 256 KB. The MLDC
multi-dimensional grid search is CPU intensive rather than memory
intensive. To overcome CPU intensive problem, dedicated nodes are used
for a specific search with a given template parameter. Each node has
dual processors and two search processes is performed per node. The CPU
usage is 100% for each search process. We also intend to re-run
Challenges 1.1.a and 1.1.b on this cluster (outside of the Round 1 MLDC
deadlines) now that we have access to this system.

## User-Refined Multi-dimensional Grid Search Details

As noted in an earlier section, to define simple galactic binary
sources, a minimum of 7 parameters have to be calculated. The grid
search is thus in the seven dimension space, and we want to obtain the
best convergence values for all parameters. Even after a signal
frequency has been found, extracting the most likely source parameters
for the remaining 6 parameters still requires searching a huge parameter
space. Finding all acceptable parameters, or finding the range of
acceptable parameters requires an even more thorough search. Given the
complexity of the search space, it is a challenge to decide how to move
from a coarse grid to a fine grid and still obtain the best acceptable
solution; in particular, this means how to guarantee that we remain and
evolve on the optimal log-likelihood surface for the parameter space.

Searching in only one dimension at a time on any grid, it is easy to get
stuck at any one point on a diagonal ridgeline, when the true value is
located a diagonal distance away on the same ridgeline. Searching at
least three dimensions (stationary or non-stationary) at a time avoids
this trivial trap, and has worked fairly well in our searches. Thus we
converge first the stationary, then the non-stationary, then the
amplitude.

Our deployed multi-dimensional grid search method and iteration steps
are as follows:

(i) Discretize the space in coarse grids (operationally defined and
    presented below) to cover the entire ranges of the parameters. Adopt
    the initial guess for the center frequency by evaluating the energy
    level at specific frequencies in the A and E FFTs. For the rest of
    the parameters, the midpoint of the full parameter range in radians
    is considered as the starting points for the search simulation.
    Start the search with the initial three dimensions of frequency,
    theta, and phi.

(ii) Compute the log-likelihood and SNR at each converged search step,
     and check that they both improve in a positive direction. Note that
     the MLDC_galactic.c code *requires* calculation of 'get_SNR_logL'
     at each step in the search across the grids. After each complete
     iteration, the current values of the converged 3 parameters are set
     as new initial templates for a refined grid and step size. (see
     mesh refinement section below)

(iii) Steps (i) and (ii) are applied recursively until the step size in
      each dimension reaches '1' (see below).

(iv) Once the initial 3 parameters are considered stable on the finest
     grid, the next three parameters are evaluated by replicating
     steps (i) through (iii) above for psi, iota and iphase, while
     keeping f, theta and phi at their converged values.

(v) The last parameter search is for amplitude, in a one-step
    search-grid, using the other 6 converged parameters.

(vi) **Note**: In each step, the log likelihood value must increase to a
     positive value or should stay stable. If it goes from positive to
     negative direction, the search process can be terminated and the
     template values should be adjusted.

Within 12 or 15 recursive simulations, the 6 parameters are converged
across a coarse grid to an increasingly finer grid. The grid search
adopted here is rectilinear grid search; progress is based on improved
values for log-likelihood and signal noise ratio. The SNR and
log-likelihood increase together linearly as the search changes from
coarse to fine grid. We change the grid in order to remain to the same
log-likelihood surface in 3- or 6-parameter space.

## Grid Refinement Protocol

# Challenges 1.1.1.a and 1.1.1.b (Single Galactic Binaries)

Initially the coarse grid is constructed to cover the entire relevant
range for a given parameter. Excepting frequency, other parameters are
started at their range mid-point and the spread covers both sides of the
mid-point. **Table 1** shows details of all simulation runs for
**Challenge 1.1.1a**. A total of 15 simulation runs were performed to
derive the 7 source parameters. The indicated 3-vector in each parameter
column, e.g. (-200,200,10), refers to the search frequency range covered
(-200 to +200) and with an iteration grid-step search increment of 10.
Changing 10  5  2  1 determines the shift from coarse grid to fine
grid; commensurate with this, the frequency search range also narrows.
By run 8, the frequency, theta, and phi have converged. The
log-likelihood and SNR values stabilize in runs 6, 7 and 8, and this
determines the final values of frequency, theta, and phi. These values
are then locked in and psi, iota, and iphase are searched. During these
search sequences, frequency, theta and phi are allowed to float, but are
confined to the converged region. The iterative grid-steps reduce from
50 to 1. The 12^th^ , 13^th^ , and 14^th^ runs show stability in the
log-likelihood and SNR across all 6 parameters. The last parameter is
dimensionless amplitude, which is searched in the range of 10^-21^ to
10^-25^. This run uses only a fine grid (iterative step as 1), and all
other parameters ranges are kept close to their converged values. The
highlighted values in **Table 1** in the log-likelihood and SNR columns
show stability across the respective three runs while the grid is
refined to its finest level. This stability is our confidence metric.

**Table 1**. Challenge 1.1.1a Grid Search Method

  -------- ----------- ----------- -------- -------- -------- -------- -------- ----------------------- ---------------------
  Run      Amplitude   Frequency   Theta    Phi      Psi      Iota     Phase    Log Likelihood          SNR

  1                    (-200, 200, (-160,   (-314,                              373.463                 29.038
                       10)         157, 10) 314, 10)                                                    

  2                    (-100, 100, (-160,   (-314,                              427.634                 31.908
                       5)          157, 10) 314, 10)                                                    

  3                    (-100, 100, (-160,   (-314,                              518.310                 36.564
                       2)          157, 5)  314, 5)                                                     

  4                    (-50, 50,   (-160,   (-314,                              518.790                 36.547
                       1)          157, 2)  314, 2)                                                     

  5                    (-25, 25,   (-80,    (-160,                              518.790                 36.547
                       1)          80, 2)   160, 2)                                                     

  6                    (-15, 15,   (-40,    (-80,                               **[518.871]{.mark}**    **[36.573]{.mark}**
                       1)          40, 1)   80, 1)                                                      

  7                    (-5, 5, 1)  (-20,    (-20,                               **[518.871]{.mark}**    **[36.573]{.mark}**
                                   20, 1)   20, 1)                                                      

  8                    (-5, 5, 1)  (-5, 5,  (-5, 5,                             **[518.871]{.mark}**    **[36.573]{.mark}**
                                   1)       1)                                                          

  9                    (-5, 5, 1)  (-5, 5,  (-5, 5,  (-320,   (-320,   (-320,   1287.708                50.748
                                   1)       1)       320, 50) 320, 50) 320, 50)                         

  10                   (-5, 5, 1)  (-5, 5,  (-5, 5,  (-160,   (-160,   (-160,   1300.135                50.996
                                   1)       1)       160, 40) 160, 40) 160, 40)                         

  11                   (-5, 5, 1)  (-5, 5,  (-5, 5,  (-160,   (-160,   (-160,   1302.737                51.503
                                   1)       1)       160, 20) 160, 20) 160, 20)                         

  12                   (-5, 5, 1)  (-5, 5,  (-5, 5,  (-80,    (-80,    (-80,    **[1302.998]{.mark}**   **[51.049]{.mark}**
                                   1)       1)       80, 10)  80, 10)  80, 10)                          

  13                   (-5, 5, 1)  (-5, 5,  (-5, 5,  (-40,    (-40,    (-40,    **[1302.998]{.mark}**   **[51.049]{.mark}**
                                   1)       1)       40, 5)   40, 5)   40, 5)                           

  14                   (-5, 5, 1)  (-5, 5,  (-5, 5,  (20, 20, (-20,    (-20,    **[1302.998]{.mark}**   **[51.049]{.mark}**
                                   1)       1)       1)       20, 1)   20, 1)                           

  **15**   **(-210,    **(-2, 2,   **(-2,   **(-2,   **(-2,   **(-2,   **(-2,   **1288.592**            **51.048**
           -250, 1)**  1)**        2, 1)**  2, 1)**  2, 1)**  2, 1)**  2, 1)**                          
  -------- ----------- ----------- -------- -------- -------- -------- -------- ----------------------- ---------------------

**Table 2** presents the resulting converged values for the source
parameters during our multi-dimensional grid search method for Blind
Challenge 1.1.1a, using the method refinement outlined in **Table 1**,
along with and the final log-likelihood and SNR values.

**Table 2**. Challenge 1.1.1a Source Results

  ------------------------------ ----------------------------------------
  **Variables for Challenge      **Converged Values**
  1.1.1a**                       

  Frequency (Hz) (f)             0.00106273333231683589

  Ecliptic latitude (theta)      2.14

  Ecliptic longitude (phi)       1.961593

  Polarization (psi)             0.380796

  Initial Phase (iphase)         5.0215930

  Inclination (iota)             -0.309204

  Amplitude (A)                  1.584893 x 10^-22^
  ------------------------------ ----------------------------------------

A similar approach is adopted for **Challenge 1.1.1b**. The range of
frequency is higher than the earlier challenge because of the more
complicated structure seen in Figure 2 for the A and E signatures. Refer
to **Table 3** below for the method protocol. Note, the range needed to
cover the entire frequency structure starts with (-10000, 10000), with
an initial grid step interval of 100. In each run for the initial three
parameters, the range and step size are decreased by half. The
log-likelihood and SNR values are seen to increase in each run until the
run step-size is '1' (finest grid). In the 6^th^ run, all step sizes in
the search have been reduced to 1. The next series of runs similarly
focus on the next three parameters, while floating the first three
parameters. The computation cost of Challenge 1.1.1a is comparatively
cheaper than for 1.1.1b. For Challenge 1.1.1b, the computation cost has
taken more than 12 cpu-hours for each run. Similar to the Challenge
1.1.1a presentation, **Table 3** below provide the details of the grid
refinement strategy, and the resulting final SNR and log-likelihood
values. Note the final SNR is 32.769, and the final log-likelihood value
is 536.81. Converged parameter results are given in **Table 4**.

**Table 4.** Challenge 1.1.1b Source Results

  ------------------------------ ----------------------------------------
  **Variables for Challenge      **Converged Values**
  1.1.1b**                       

  Frequency (Hz) (f)             0.00300037829081217398

  Ecliptic latitude (theta)      0.51

  Ecliptic longitude (phi)       4.621593

  Polarization (psi)             5.020796

  Initial Phase (iphase)         3.965159

  Inclination (iota)             5.090795

  Amplitude (A)                  3.981072 x 10^-23^
  ------------------------------ ----------------------------------------

**Table 3**. Challenge 1.1.1b Grid Search Method

  -------- ----------- -------------- -------------- -------------- --------------- --------------- --------------- ---------------------- ---------------------
  Run      Amplitude   Frequency      Theta          Phi            Psi             Iota            Phase           Log Likelihood         SNR

  1                    (-10000,       (-160, 160,    (-320, 320,                                                    47.760                 13.563
                       10000, 100)    20)            40))                                                                                  

  2                    (-10000,       (-80, 80, 10)  -160, 160, 20)                                                 47.760                 13.563
                       10000, 50)                                                                                                          

  3                    (-5000, 5000,  (-40, 40, 5)   (-80, 80, 10)                                                  156.689                18.377
                       25)                                                                                                                 

  4                    (-2500, 2500,  (-20, 20, 2)   (-40, 40, 5)                                                   156.689                18.377
                       10)                                                                                                                 

  5                    (-2500, 2500,  (-20, 20, 1)   (-40, 40, 1)                                                   158.240                18.436
                       5)                                                                                                                  

  6                    (-2000, 2000,  (-10, 10, 1)   (-20, 20, 1)                                                   **[247.797]{.mark}**   **[22.284]{.mark}**
                       1)                                                                                                                  

  7                    (-2,2,1)       (-2, 2,1)      (-2,2,1)       (-400,400,50)   (-400,400, 50)  (-400,400,50)   452.0413               30.1017

  8                    (-2,2,1)       (-2, 2,1)      (-2,2,1)       (-200,200,25)   (-200,200,25)   (-200,200,25)   477.397864             30.90725

  9                    (-2,2,1)       (-2, 2,1)      (-2,2,1)       (-200,200,10)   (-200,200,10)   (-200,200,10)   504.238                31.7573

  10                   (-2,2,1)       (-2, 2,1)      (-2,2,1)       (-150,150,5)    (-150,150,5)    (-150,150,5)    522.41                 32.33108

  11                   (-1,1,1)       (-1,1,1)       (-1,1,1)       (-30,30,1)      (-30,30,1)      (-30,30,1)      528.927                32.528

  **12**   **(-210,    **(-2,2,1)**   **(-2,2,1)**   **(-2,2,1)**   **(-2,2,1)**    **(-2,2,1)**    **(-2,2,1)**    **536.813**            **32.768807**
           250, 1)**                                                                                                                       
  -------- ----------- -------------- -------------- -------------- --------------- --------------- --------------- ---------------------- ---------------------

# Challenge 1.1.2 (Verification Binaries)

Given frequency, theta, and phi from the MLDC document, we searched for
psi, iota, iphase, and amplitude only. The psi, iota, and iphase has a
range from -320, 320 with a step size of '1'. The starting template
values for psi and iota are 'pi/2', and iphase is 'pi'.

Unlike Challenges 1.1.1a and b, we have not performed multi-dimensional
grid approach in Challenge 1.1.2. Instead, one full run, using the fine
grid only, was performed to finalize and extract the source parameters,
except amplitude. Each of the 20 targets was assigned to its own
cluster-node. Note that the signal noise ratio in EIPsc and in bltOPEN20
is below 10 \[highlighted in **Table 5**\]. We therefore suspect that
these converged results are wrong. These two experiments are being
repeated for validity and still the converged values are high. Also
note, the log-likelihood and SNR for source RXJ0806 reached abnormally
high positive values -- this is either a gross error or an extremely
well-done result! For the rest of the Verification Binaries, amplitude
was finalized during a *second* grid search process with fixed 6
dimension template parameters listed in **Table 5** and in the challenge
dataset \[f, theta, and phi\]. Note in the amplitude column, some of the
values have repeated among various sources. We do not understand this
repetition; were it only in the synthetic binaries, we could assume the
model was repeated. But some of the repeats are in the actual known
verification binaries as well. Overall, the final converged source
parameters, along with SNR and Log Likelihood, for Challenge 1.1.2 are
provided in **Table 5**.

**Table 5**. Challenge 1.1.2 Grid Search Method

  ----------- -------------- ---------------- ----------------- ----------- ------------------------ -----------------------
  Name        Amplitude      Psi              Iota              Phase       Log Likelihood           SNR

  RXJ0806     2.511886e-22   4.100796         3.100796          5.171593    **[121295.22]{.mark}**   **[495.7474]{.mark}**

  V407Vul     3.981072e-23   -1.039203673     0.590796326792    3.1815926   2355.71                  68.73176

  ESCet       3.981072e-23   0.527963         3.760796          4.191593    1997.919671              63.239764

  AMCVn       3.981072e-23   3.250796326795   -0.329203673205   0.0415926   742.366                  38.542

  HPLib       5.011872e-23   -0.789204        3.120796          0.741593    878.2624                 41.94

  EIPsc       1.0 e-22       4.750796         .020796           4.181593    26.676                   **[7.3216]{.mark}**

  bltOPEN7    5.011872e-23   -1.639204        .020796           0.041593    1389.132642              52.711

  bltOPEN8    3.981072e-23   -1.3692036       0.00079632        0.8315926   618.523                  35.228

  bltOPEN9    5.011872e-23   -1.099204        1.650796          1.571593    136.03                   16.518

  bltOPEN10   5.011872e-23   3.430796         -1.079204         4.241593    2175.848                 66.17954

  bltOPEN11   1.995262e-23   2.5207963        1.4507963         3.071593    77.807513                12.486965

  bltOPEN12   5.011872e-23   4.200796         4.740796          1.231593    544.5199                 33.008007

  bltOPEN13   5.011872e-23   -1.5792036       1.500796          5.2515926   535.628                  32.869728

  bltOPEN14   2.511886e-23   -1.45920367      4.460796          0.891593    124.513                  15.829

  bltOPEN15   2.511886e-23   4.500796         1.3007963         3.671593    103.0185                 14.357

  bltOPEN16   2.511886e-23   0.390796         1.600963          0.311593    154.015                  17.624242

  bltOPEN17   1.995262e-23   -1.439204        4.560796          4.801593    107.94                   14.761

  bltOPEN18   3.162278e-23   0.4607963        -1.2092036        4.371592    569.05                   33.848

  bltOPEN19   3.981072e-23   4.820796         4.220796          1.611593    1037.088                 45.634

  bltOPEN20   1.995262e-23   -1.619204        1.730796          3.191593    47.441070                **[9.741084]{.mark}**
  ----------- -------------- ---------------- ----------------- ----------- ------------------------ -----------------------

**Challenge 1.1.3 (Resolvable Binaries)**

For the Resolvable Binaries Challenge, we have identified 18 significant
sources (not the full 20) based on FFT of A and E. Initial template
parameters for theta, psi, and iota are at the mid point (i.e., pi/2),
and phi and iphase start at 'pi'. Details of these runs follow in the
next several tables.

The multi-grid approach on the cluster has been adopted for the
**Challenge 1.1.3**. Several iterations are needed in Run1 \[**Table
6**\] to retrieve "converged" stationary parameters for Challenge1.1.3.
Note, the SNR in many sources have been below 10 and many log-likelihood
values are also negative. In Run2, the non-stationary parameters search
increases log-likelihood and SNR values, which can be seen in **Table
7**. Red values in **Table 7** indicate sources that never converged in
their finest grid according to our success metric of positive
Log-Likelihood and SNR. We include them here, while recognizing that the
results are most likely not accurate; but this is as far as we have been
able to converge before the Round 1 Deadline of 1 December. The other
highlighted values are ones that did converge to positive values during
the "amplitude" search. The "Run1 Converged Values" from **Table 6**
were used in Run 2, and all parameters improved. Run 3 \[**Table 8**\]
shows the final converged values of all parameters, with SNR and Log-L.

**Table 6.**

**Run 1: Coarse to Fine grid search for Stationary Parameters**

(multi-grid approach)

+-------+-----------------+--------+----------+--------+-------------+
| In    | Frequency       | Theta  | Phi      | SNR    | Log         |
| itial |                 |        |          |        | Likelihood  |
| Freq  |                 |        |          |        |             |
| uency |                 |        |          |        |             |
|       |                 |        |          |        |             |
| (     |                 |        |          |        |             |
| Based |                 |        |          |        |             |
| on    |                 |        |          |        |             |
| FFT)  |                 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.0011001908569 | -1.07  | 5.491593 | 4.774  | 11.3621     |
| 01128 |                 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.              | 1.1892 | 1.170796 | 3.0    | -3.1492288  |
| 01388 | 001387666213994 |        |          | 280098 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.              | -1.08  | 2.321593 | 3.2858 | -12.168554  |
| 01599 | 001599975926716 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.              | -1.54  | 4.72159  | 4.8773 | 2.162446    |
| 01649 | 001648554951986 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.              | -1.14  | 5        | 10.934 | 54.110695   |
| 02104 | 002104108083089 |        | .9715929 |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.    | 0.0             | -0.86  | 0.841593 | 3.3425 | -86.4217    |
| 00229 | 023000517272947 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0               | -0.79  | 4.       | 13.6   | 21.448      |
| 03499 | .00349899999999 |        | 71159265 |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.    | 0.              | -0.62  | 4.       | 16     | 74.43053    |
| 00369 | 003689615351357 |        | 55159265 | .09433 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0               | -0.19  | 4        | 2      | 261.874     |
| 04635 | .00463479972839 |        | .6015926 | 3.5298 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.0047342257029 | -0.32  | 4.651590 | 1      | -101.92611  |
| 04734 |                 |        |          | 1.0440 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.0             | -      | 4.561592 | 71.28  | 1660.874    |
| 04929 | 049292702077229 | 0.0598 |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0               | 0.15   | 4.       | 17.18  | 70.32311    |
| 05233 | .00523277793884 |        | 69159264 |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0               | -0.440 | 4.671592 | 1      | -144.1436   |
| 05793 | .00579345140584 |        |          | 0.0746 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.00            | -1.55  | 3.85158  | 5      | -229.2067   |
| 06085 | 608488238016738 |        |          | .00838 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.    | 0.              | -1.64  | -0.5     | 3      | -269.1295   |
| 00709 | 007115692250563 |        | 38407345 | .73486 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.0             | 1.88   | 2.43159  | 4.767  | -255.527    |
| 07772 | 078012936960846 |        |          |        |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.007           | -      | 3.490796 | 4.     | -242.67643  |
| 07828 | 861311843865612 | 1.4108 |          | 874389 |             |
+-------+-----------------+--------+----------+--------+-------------+
| 0.0   | 0.0             | -0.91  | 5.7      | 2      | 3.333425    |
| 09183 | 092005666680908 |        | 31592653 | .61226 |             |
+-------+-----------------+--------+----------+--------+-------------+

**Table 7.**

Run 2: Non-stationary Parameters with Multi-Grid Approach from Coarse to
Fine

  ------------------------ --------- ----------- ------------ ------------ ---------------------- --------- -------------------------
  Frequency                Theta     Phi         Psi          Iota         Phase                  SNR       Log Likelihood

  0.00110019403584837991   -1.06     5.57157     0.1307963    1.540796     5.7419                 4.99      12.35

  0.00138768528748072113   1.2292    1.230795    0.300796     1.530794     -2.878                 3.84      2.53

  0.00159997910563038710   -1.15     2.321593    0.07079632   1.540796     6.15159                3.39      **[-10.815]{.mark}**

  0.001648554951986        -1.53     4.741579    1.590796     1.56079      3.0715919              4.89      2.302

  0.002104108083089        -1.15     5.981593    1.580796     1.6107959    3.221592               11.013    55.076

  0.0023000549062083802    -0.94     0.861592    1.570796     1.520796     3.28999                3.65685   **[-80.404]{.mark}**

  0.00349898410542683579   -0.710    4.701592    4.440795     1.5007962    4.89159                16.912    99.53

  0.00368962806701316447   -0.64     4.501592    1.6707962    4.550796     1.5815919              19.113    136.7669

  0.00463479972838         -0.19     4.6215926   2.1207959    -1.9292036   4.1715                 35.928    635.483

  0.00473423206072877672   -0.25     4.661589    1.040796     4.550796     1.1015                 19.7204   105.844

  0.00492927338663728780   -0.0998   4.5715919   1.610795     3.140795     2.74159                89.99     4043.48

  0.005232777938839        0.14      4.6915926   5.010795     -1.4392      2.7315                 22.7434   215.549

  0.00579344186909983277   -0.4      4.7015926   -1.229203    4.57070795   4.841592               14.4218   -58.924

  0.0060848792012529       -1.54     3.7715889   3.040796     1.5607963    **[6.64159]{.mark}**   5.08785   **[-227.08218]{.mark}**

  0.007115685892734        -1.63     -0.528407   3.070796     1.57079      0.641592               3.96587   -263.059

  0.00780129051717022      1.88      2.4115919   0.0707963    1.570796     6.641592               4.79568   -254.677

  0.00786131502278000077   -1.4108   3.450796    3.070796     1.570796     -0.258407              4.9213    -241.536

  0.00920056348917641133   -0.91     5.771592    3.57079      1.5707963    -0.258407              3.1294    4.885797
  ------------------------ --------- ----------- ------------ ------------ ---------------------- --------- -------------------------

**Table 8**

Run 2: Amplitude Search for Challenge 1.1.3 with Multi-Grid Approach

  --------------------- -------------- ----------------------- ----------- ----------- ----------- ----------- ----------- ----------- ------------
  Source                Amplitude      Frequency               Theta       Phi         Psi         Iota        Phase       SNR         Log
                                                                                                                                       Likelihood

  bltOPEN101            3.981072e-23   0.0110019403584837991   -1.06       5.591579    0.150796    1.540796    5.741925    5.008       12.4183

  bltOPEN102            1.995262e-23   0.0013876852874807211   1.2492      1.250795    0.290796    1.510795    -2.898407   3.8889      7.4794

  bltOPEN103            1.584893e-23   0.0015999791056303871   -1.13       2.321593    0.070796    1.520796    6.131593    3.425       5.841667

  bltOPEN104            1.995262e-23   0.001648554951986       -1.53       4.76158     1.610796    1.550796    3.071592    4.8977      11.96207

  bltOPEN105            3.162278e-23   0.0021041080830890000   -1.14       5.981593    1.590796    1.630796    3.201593    11.0228     60.6639

  bltOPEN106            7.943282e-24   0.0023000549062083802   -0.96       0.861593    1.590796    1.500796    3.30999     3.74505     6.941142

  bltOPEN107            2.511886e-23   0.0034989841054268357   -0.69       4.701593    4.430796    1.480796    4.871590    17.0881     445.92

  bltOPEN108            2.511886e-23   0.0036896280670131644   -0.63       4.501593    1.690796    4.530796    1.571592    19.2677     185.24

  bltOPEN109            3.162278e-23   0.0046347997283890003   -0.19       4.621593    2.130796    -1.9492     4.19159     36.0145     643.082

  bltOPEN110            2.511886e-23   0.0047342320607287767   -0.25       4.66158     1.020796    4.530796    1.081500    19.9398     198.058

  bltOPEN111            3.981072e-23   0.0049292733866372878   -0.0998     4.571592    1.600796    3.140796    2.721593    89.99       4042.404

  bltOPEN112            2.511886e-23   0.005232777938839999    0.14        4.691593    5.030796    -1.419204   2.711592    22.8846     259.0253

  [bltOPEN113]{.mark}   []{.mark}      []{.mark}               []{.mark}   []{.mark}   []{.mark}   []{.mark}   []{.mark}   []{.mark}   []{.mark}

  bltOPEN114            7.943282e-24   0.0060848792012529922   -1.54       3.751589    3.020796    1.540796    6.641592    5.10456     12.990118

  [bltOPEN115]{.mark}   []{.mark}                                                                                                      

  [bltOPEN116]{.mark}   []{.mark}                                                                                                      

  [bltOPEN117]{.mark}   []{.mark}                                                                                                      

  [bltOPEN118]{.mark}   []{.mark}                                                                                                      
  --------------------- -------------- ----------------------- ----------- ----------- ----------- ----------- ----------- ----------- ------------

As usual, the stationary and non-stationary parameters are found first;
then the dimensionless amplitude is extracted across 10^-21^ to 10^-25^.
Recall that in Challenge 1.1.2, only 2 runs needed to be performed in
the Cluster. Challenge 1.1.3 required 4 (coarse  fine) grid-search
processes to converge and extract stationary source parameters. The
non-stationary parameter convergence also required in 4 search processes
(coarse  fine). The Challenge 1.1.3 is a 7-dimension search problem
rather than the 4-dimension search of Challenge 1.1.2 (recall f, theta,
and phi are provided in 1.1.2). For the Resolvable Binaries, the
frequencies of source parameters are very close, and convergence took
multiple hours, even on the fast Cluster. In addition, only 18 sources
were found, based on our FFT preliminary search. No other filter or
transform method has been attempted at this time. Not all parameters
have converged successfully. We will continue to refine our procedures
for Challenges 1.1.2 and 1.1.3, outside of the MLDC Round 1 Challenge.

## General Implications of Grid Search Method for All Challenges

The coarse grid leads to the region where "real" source parameters are
available. Once search space resolves to the finer grid, the greater the
computation cost. It has proven to be a serious limitation for us to
begin with much finer grids initially, and it makes it difficult to
automate sizing of subsequent grid refinements. With reference to
Challenge 1.1.1a and b, the grid refinements pattern does not fall into
a common category due to the complex structure of the signal in
Challenge 'b'. During these blind challenges, we have used manual
grid-refinement for the analysis. The 'get_SNR_logL' function currently
has to be executed at every grid point to compute SNR and log-likelihood
values. The 'get_SNR_logL' function is evaluated at the vertex of the
grids, rather than the centroid of the grid, and this introduces
possible errors if the ideal value is not on a vertex. This is the basis
of the need for such extensive fine-scale search. Actually, certain grid
points could be eliminated following a simpler strategy rather than
computing SNR and logL values at every point. However, such a strategy
needs to involve data-stream classification and search for the main
contribution time-periods for the peak frequency. This strategy has not
yet been implement, but we are endeavoring to articulate and prove it.
The 'get_SNR_logL' function in turn calls low-frequency function \[a
low-pass filter\] and noise function. Every call involves multiple
computations of these various functions. Inside the low-frequency
function, multiple loops are needed to compute the amplitude and Doppler
modulation. In the low-frequency function, the memory is released and
allocated dynamically; but allocating and releasing memory dynamically
increases computation cost. Due to the sensitivity of the problem, the
grid size must be sliced extremely thin to achieve the best solution for
the source parameters. This slicing of the grid increases computation
cost exponentially. During the Challenge 1.1.2 search process \[Table
5\], even though the number of template searches (i.e., grid points) is
equivalent in all 20 cases, certain sources converged faster than
others. We believe the reason behind the slower convergence is tied
directly to the complex structure of signal and/or close proximity of
the sources and wave patterns in frequency-space.

## Benchmark Analysis 

Initial runs of Challenges 1.1.1a and b search process were performed
using a Sun Solaris (Sparc) Server. The code was implemented as a single
thread approach \[see **Table 1**\]. The first 3 runs took between 20
min. to 3 hrs to converge. From Run 4 onwards, convergence took
approximately between 3-6 hours due to the finer grid size. Run 14 took
more than 100 hours, which represents the finest grid with respect to
6-dimension search. The template search ('get' calls) also increases
time-of-execution over the coarse grid to fine grid, as seen in the
following, **Table 9**.

**Table 9**. Times for convergence of each simulation in Challenge
1.1.1a

+---------+------------------------------------+----------------------+
| ### Run | **Template Search for Challenge    | ###                  |
|         | 1.1.1a**                           | Time for convergence |
|         |                                    |                      |
|         | **(number of times 'get_SNR_logL'  |                      |
|         | called)**                          |                      |
+---------+------------------------------------+----------------------+
| 1       | 82656                              | Less than 40 min.    |
+---------+------------------------------------+----------------------+
| 2       | 82656                              | Less than 40 min.    |
+---------+------------------------------------+----------------------+
| 3       | 814464                             | 1h 10 min            |
+---------+------------------------------------+----------------------+
| 4       | 5058585                            | 6h 28min             |
+---------+------------------------------------+----------------------+
| 5       | 665091                             | 1h 16min             |
+---------+------------------------------------+----------------------+
| 6       | 404271                             | 0h 37min             |
+---------+------------------------------------+----------------------+
| 7       | 18491                              | 0h 20min             |
+---------+------------------------------------+----------------------+
| 8       | 1331                               | 0h 5min              |
+---------+------------------------------------+----------------------+
| 9       | 2924207                            | 3h 35min             |
+---------+------------------------------------+----------------------+
| 10      | 970299                             | 2hr 15min            |
+---------+------------------------------------+----------------------+
| 11      | 6539203                            | 6hr 30min            |
+---------+------------------------------------+----------------------+
| 12      | 6539203                            | 8hr 0min             |
+---------+------------------------------------+----------------------+
| 13      | 6539203                            | 10hr 0min            |
+---------+------------------------------------+----------------------+
| 14      | 91733851                           | More than 100 Hrs    |
+---------+------------------------------------+----------------------+
| 15      | 640625                             | Less than 2 hr       |
+---------+------------------------------------+----------------------+

The relatively short time for Run 15 is due to the fact that therein
only the amplitude is searched while other parameters are held stable.
Overall, the time for convergence for each run depends on the number in
template search (i.e., the number of times 'get_SNR_logL' has to be
called). The more often a template search is called, the longer the
convergence time, in direct proportionality.

## Future Directions, Comments, and Conclusions

The MLDC grid search method is an exhaustive search method;
stream-lining the search process in an optimized way, while maintaining
accuracy and high log-likelihood is of the highest priority. Ideally,
the 'get_SNR_logL' function would need to be called only a minimal
number of times to avoid computation cost in a multi-dimensional grid
search. Stopping criteria would need to be established for the search
process; for example, once a ridge-pathway of ideal solutions is found
in the coarse grid, then alter the actual search parameters to stay on
that pathway. This approach could lead to autonomous grid refinement
based on these constraints. Rapid convergence of the search process
using heuristic approaches should be evaluated based on hybrid
techniques. Resolving close, complex signals in a given time-series is a
significant challenge at low frequency. In addition, aliasing creates a
similar power-spectrum at higher frequencies in the FFT; and if one does
not know in advance what frequency band to look across, a major
ambiguity will need to be resolved.

Currently, we run an FFT on the data-stream, and manually/visually
select probable regions of GW source signals. The structure of the
presumed signals in frequency-space therefore determines both the
initial guess center frequency and the realistic range for detailed
search. It would be very interesting to try to automate at least part of
this process. For example, the source EIPsc verification binary does not
show a signal in the FFT of channels A and E, yet the MLDC-galactic.c
codes finds the source parameters. We found that doing an FFT on the
Michelson-like variables X, Y, and Z provided a possible solution: the
peak values of X, Y, and Z when substituted into the A and E formulae
essentially cancelled each other out \[2X \~ -Y-Z and Z-Y \~ 0\]. Thus,
the method of visually looking for sources in A and E is fallible. A
better process characterizing the frequency sources is needed, and
ultimately some automation or software assistance would be very helpful.

Establishing source databases for known \[verification and resolvable\]
binaries such as AM Cvn stars, known cataclysmic variables, certain
Binary WD's, and some compact X-ray binaries, will allow a
'quick-and-dirty' pattern recognition software to identify and extract
these sources in a new LISA time-series. Removing the "knowns" allows
for huge data reduction in the search-discovery phase. But, such
databases need to be constructed in a format *amenable to data-mining*
for pattern recognition. In addition, such early matches could be done
before waiting for one complete interferometer orbit.

In addition to data-mining techniques, two major approaches need to be
developed. These are broadly categorized as ***dimension reduction***
and ***data reduction***.

Once analysis moves from a 7-dimension parameter space to 17-dimension
space, any viable search process will have to be highly optimized, based
probably on hybrid techniques, in order to reach convergence. At the
moment, searching 7 dimensions takes substantial time using the current
formats; 17-dimensional search will swamp these methods. Consider also
that the strategy of searching stationary parameters first and then the
non-stationary ones will no longer work: f, fdot, and fdoubledot will
have to be searched together because if 'f' is not constant, then the
real search will have to be over 'f', its slope, and its curvature, thus
mixing in non-stationary variables. Here, ***dimension reduction*** will
require analysis of possible proxy dimensions (or mathematical
projections) that can represent composite data.

Recursive partitioning of the data into smaller time-bins could be used
to identify the signals (still based on the FFTs), and this would enable
further ***dimension reduction***. In the higher-order dimensional
search where certain parameters are (physically) correlated, PCA or ICA
could be applied to identify such source parameter connections. Instead
of performing a sequential search process, a hybrid optimized search
process could be performed using various intelligent algorithms and
conjugate gradient-descent methods.

The key challenge is detecting the signal from the time-series' power
spectrum. The signals could be classified based on certain energy level
using a neural network approach. Once a signal was identified and
processed using the neural network, the data corresponding to the
signal-region could be further processed 'locally' to determine the
requisite source parameters rather than dealing the entire time-series.
Such ***data reduction*** would enable much faster convergence.

The multi-dimensional grid search method employed here focuses on one
initial template. An improved approach to the search process would be to
search multiple templates (from derived databases) in parallel rather
than sequentially. Computational cost and resolution capabilities have
to be extended for complex signal structure. Symmetric Multi-Processing
(SMP) using cluster-computing technology is an alternative for rapid and
faster convergence. Also, implementing Parallel Virtual Machine (PVM)
techniques to the grid search process would lead to a robust and more
scalable real-time search process.

# Acknowledgements

We gratefully thank Dr. Jeff Crowder, Dr. Michele Vallisneri, and Dr.
Neil Cornish for several very helpful discussions during Round 1 of the
MLDC. We also gratefully acknowledge the support of our Division Systems
Support Staff for implementation and use of space on large servers and
clusters.