next up previous contents
Next: Function: plot_template() Up: GRASP Routines: Template Bank Previous: Example: read_grid program   Contents

Function: template_grid()

0 void template_grid(struct Scope *Grid)
This function evolved from grid4.f, a FORTRAN routine written by Sathyaprakash. This function lays down a grid of templates that cover a particular mass range (the region inside the distorted triangle shown in Figure [*]).

The arguments are:

Grid: Input/Output. This function uses as input all of the fields of Grid except for Grid.n_tmplt and Grid.templates. On return from template_grid these latter two fields are set. The function uses malloc() to allocate storage space and creates in this space an array containing Grid.n_tmplt objects of type Template. If you wish to free the memory, call free(Grid.templates).

It is easy to cover the parameter space shown in Figure [*] with ellipses. However each ellipse represents a filter, and filtering takes computer time and memory, so the real problem is to cover the parameter space completely, using the smallest possible number of templates. This is a non-trivial packing problem; while our solution is certainly not optimal, it is quite close.

The algorithm used to place the templates works in coordinates $(x_0,x_1)$ which are rotated versions of $(\tau_0,\tau_1)$, aligned along the minor and major (or major and minor) axes of the template ellipses. The input angle Grid.theta,in the range $(-\pi,\pi)$, is the counterclockwise angle through which the $(x_0,x_1)$ axes need to be rotated to bring them into alignment with the principal axis of the template ellipses.

Although each template is an ellipse, the problem of packing templates onto the parameter space can be more easily described in terms of a more familiar packing problem: packing pennies on the plane. One can always transform an ellipse into a circle by merely scaling one coordinate uniformly while leaving the other coordinate unchanged. So we introduce coordinates $x_1$ along the major diameter and $x_o$ along the minor diameter of the ellipse, and then ``shrinking" the $x_1$ coordinate by the ratio of major to minor diameters. In this way the ellipses are transformed into circles.

Figure: Covering a plane with a square lattice of pennies (or templates) leaves 21% of the area exposed
\begin{figure}\begin{center}
\epsfig{file=Figures/figure3.ps,height=4cm,bbllx=72pt,bblly=160pt,
bburx=540pt,bbury=630pt}\end{center}\end{figure}

First, a template is laid down at the point where the equal mass line intersects the maximum mass line. Then additional templates are placed along the equal mass line, at increasing values of $x_0$. These templates are staggered up and down in the $x_1$ direction. After laying down this set of templates, the remaining part of parameter space is covered with additional templates, in columns starting at each of the previously determined template locations. These columns have the same value of $x_0$ as the previously determined templates but increasing values of $x_1$. The columns are continued until the ``leading edge" of the final template lies outside the parameter space.

We can describe the packing (and the ``efficiency") of the packing in terms of the penny-packing problem. Suppose we start by setting pennies of radius $1/2$ on all points in the plane with integer coordinates, as shown in Figure [*]. It is easy to show that the fraction of the plane (i.e., parameter space!) which is not covered by any pennies is $\epsilon = 1-\pi/4 =0.214\cdots$ or about 21%.

Figure: Staggering the pennies (or templates) decreases the uncovered fraction of the plane to 9.3%
\begin{figure}\begin{center}
\epsfig{file=Figures/figure4.ps,height=4cm,bbllx=72pt,bblly=160pt,
bburx=540pt,bbury=630pt}\end{center}\end{figure}

Now suppose that we ``stagger" the pennies as shown in Figure [*]. In this case, the fraction of area not covered is $\epsilon = 1 - {\pi \over 2 \sqrt{3}} =0.093\cdots$ or about 9.3%. If we wish to completely cover the missing bits of the plane, then we can do so by increasing the radius of each penny by $\sqrt{5/4}$ (or, equivalently, by moving the points at which the pennies lie closer together by that same factor). The resulting diagram is shown in Figure [*]. By increasing the number-density of pennies on the plane by 25% we have successfully covered up the remaining 9.3% of the area.

Figure: Decreasing the spacings of the pennies (or templates) by a factor of $(5/4)^{1/2}=1.118\cdots$ then covers the entire plane.
\begin{figure}\begin{center}
\epsfig{file=Figures/figure5.ps,height=4cm,bbllx=72pt,bblly=160pt,
bburx=540pt,bbury=630pt}\end{center}\end{figure}

Now it is not possible to implement this algorithm exactly, because we are not attempting to cover the entire plane, but rather only a finite region of it. You might think that we could just start laying down templates in the same was as for Figure [*] and stick in a few extra ones for any parts of the parameter space which were not covered, but unfortunately this would then lead us to place templates centered at points in $(\tau_0,\tau_1)$ space that do not correspond to $\eta \le
1/4$, and for which the very meaning of a ``chirp" is ill-defined.

The code in template_grid() thus uses a heuristic method to place templates, trying whenever possible to stagger them in the same way as Figure [*] but then shifting the center locations when necessary to ensure that the template corresponds to physical values of the mass parameters $m_1$ and $m_2$. This is often referred to as ``hexagonal packing". In practice, to see if this placement has been successful or not, the function plot_template() can be used to visually examine the template map.


Table: Orientation and dimensions of 0.97 ambiguity templates.
Author Detector $f_0$/Hz $\theta$/rad radius $r_1$ (msec) radius $r_2$ (msec)
Sathyaprakash Caltech 40m (Nov 94) 140 0.307 8.0 0.6
Owen Initial LIGO 200 0.5066 2.109 0.162
Owen Advanced LIGO 70 0.4524 3.970 0.352


Table [*] gives information about the appropriate template sizes, spacings and orientations as found in the recent literature, and using the match_fit example program. The angle $\theta$ is the angle to the axis of the ellipse whose radius is $r_1$, measured counterclockwise from the $\tau_0$ axis. The other radius (semi-axis) of the ellipse has length $r_2$. Equation (3.16-18) of reference [5] do not appear to agree with Table [*], but that is because the $r_i = dx_i$ of [5] are defined by $(dx_i)_{\rm Owen}
= dl_i/\sqrt{E_i}$. The $dl_i$ are the edge lengths of a hypercube in dimension $N$, chosen so that if templates are centered on its vertices, then the templates touch in the center of the cube, so that $(dx_i)_{\rm Owen}
= dl_i/\sqrt{E_i}$. In our $N=2$ dimensional case, this gives $r_i = dx_i=(dx_i)_{\rm Owen}/\sqrt{2}$. Note also that in this table, Owen and Sathyaprakash use different definitions of $f_0$, so that their results may not be directly compared. In Owen's case, $f_0$ refers to the frequency of maximum sensitivity of the detector, whereas in Sathyaprakash's case it refers to the frequency at which the chirp first enters the bandpass of the detector. In the case of the November 1994 data set, we quote two different sizes an orientations for the ellipses, depending upon the choice of $f_0$.
Author: Bruce Allen, ballen@dirac.phys.uwm.edu
Comments: This routine evolved from grid4.f, which was written by Sathyaprakash. The method used to stagger templates is heuristic, and could perhaps be improved. Very small regions of the parameter space along the equal-mass line ($\eta=1/4$) may not be covered by any templates.


next up previous contents
Next: Function: plot_template() Up: GRASP Routines: Template Bank Previous: Example: read_grid program   Contents
Bruce Allen 2000-11-19