next up previous contents
Next: Structure: struct tile Up: GRASP Routines: Template Bank Previous: Optimization and computation-speed considerations   Contents


Template Placement

As mentioned in preceding sections, when detecting signals using a discrete bank of templates, some loss in signal strength will always occur due to imperfect matching of the signal with the closest template in the bank. The match function $\mu$ measures this signal loss; the mismatch $1-\mu$ can then be thought of as a proper distance interval on the template parameter space. The goal of template bank construction is to place templates with a sufficient density in parameter space that the fractional signal loss is reduced to less than some specified amount. However, since each template in the bank represents a computational investment, one would like to do this with as few templates as possible.

Conceptually this can be thought of as a tiling problem -- one attempts to cover the parameter space completely with ``tiles'', each representing a template. Each tile is small enough to fit entirely within the equimatch contour at the specified match level, drawn about the tile's centre. For match levels close to 1, the match function $\mu$ drops off quadratically with parameter offsets, and the equimatch contours are ellipses. However, the sizes and orientations of these ellispes will in general vary over the parameter space, as the behaviour of the match function changes. This complicates the problem significantly. For instance, while hexagonal tiling can be shown to be the most efficient tiling scheme when tile sizes are constant, it is not at all clear how to implement such a scheme when the sizes and shapes of the hexagons are allowed to vary.

For this reason, a somewhat less efficient but algorithmically simpler tiling scheme has been adopted. We lay out on the parameter space a rectilinear coordinate system with some arbitrary rotation, take our tiles to be rectangles whose sides are aligned with the coordinate axes. The width and height of each tile may vary so that it exactly inscribes the equimatch ellipse, but its orientation is fixed by the coordinate system. As figure [*](a) shows, aligning the coordinate axes with the principle axes of the ellipse results in the largest tile areas, and hence the fewest number of templates. When the ellipse have changing orientations, one must choose some appropriate averaged angle for the coordinate system. Several guesses are often required before an optimal orientation is found.

Figure: Some aspects of template placement using rectangular tiling: (a) By applying a coordinate rotation, the axes of the equimatch ellipse can be alligned with the axes of the rectanglular tiles, maximizing the tile area. (b) Rectangular tiles can easily be stacked into columns, even when the match contours are varying. (c) At the ends of a column, extra overlapping tiles may be required to cover the edges of the parameter space.
\begin{figure}\begin{center}
\epsfig{file=Figures/fig_tiling.ps}\end{center}\end{figure}

Once a coordinate system is chosen, the parameter space can be divided into columns, into which the rectangular tiles are stacked. The height of each tile is chosen so as to stay within its equimatch ellipse, as shown in figure [*](b), and the column widths may vary between columns so as to maximize the resulting tile areas. At the boundaries of the parameter space, extra tiles may have to be added at the corners of a column to provide complete coverage, as shown in figure [*](c).

The function tiling_2d() (section [*]) is a generic implementation of such a rectangular tiling scheme. It works on nearly any parameter space on which a proper distance metric can be defined. The function get_chirp_templates() (section [*]) implements the tiling_2d() algorithm for the specific case of binary inspiral templates, using the quadratic terms of a fit to the chirp template match function (equation [*]) to define the distance metric on the space.


next up previous contents
Next: Structure: struct tile Up: GRASP Routines: Template Bank Previous: Optimization and computation-speed considerations   Contents
Bruce Allen 2000-11-19