void qn_template_grid(float dl, struct qnScope *grid)This function is responsible for allocating the memory for a grid of templates on the parameter space and for choosing the location of the templates. The arguments are:

`dl`: Input. The length of the `sides' of the square templates. This quantity should be set to (see the discussion below).`grid`: Input/Output. The grid of templates of type`struct qnScope`. On input, the fields that relate to parameter ranges should be set. On output, the field`n_tmplt`is set to the number of templates generated, and these templates are put into the array field`templates[0..n_tmplt-1]`(which is allocated by the function).

The function `qn_template_grid()` attempts to create a set of
templates, , which ``cover'' parameter space finely enough that
the distance between an arbitrary point on the parameter space and one of
the templates is small. A precise statement of this goal, and how it is
achieved, can be found in the paper by Owen [5]. We hilight
the relevant parts of reference [5] here.

The templates are damped sinusoids with a set of frequency and quality parameters . They are normalized so that where is the inner product defined by Cutler and Flanagan [21]. Since we are most interested in the high quality region of parameter space, it is a good approximation that the value of the one-sided noise power spectrum is approximately constant, , over the frequency band of the template. This approximation simplifies the form of the inner product as the noise power spectrum appears in the inner product as a weighting function.

In order to estimate how close together the templates must be, we define
the distance function
corresponding to the mismatch
between the two templates and . This interval can be expressed
in terms of a metric as
where
are coordinates on the two dimensional parameter
space. Such an expression is only valid for sufficiently close points on
parameter space. In the limit of a continuum of templates over parameter
space, the metric can be evaluated
by
where
is a partial derivative with respect to the
coordinate . We find that the mismatch between templates that
differ in frequency by and in quality by is given by

In the approximate metric of equation (), we have kept only the dominant term in the limit of high quality. The minimum number of templates, , required to span the parameter space such that there is no point on parameter space that is a distance larger than from the nearest template can be found by integrating the volume element over the parameter space. Using the approximate metric and the parameter ranges and , we find that the number of templates required is

(8.18.187) |

The issue of template placement is more difficult than computing the number of templates required. Fortunately, for the problem of quasinormal ringdown template placement, the metric is reasonably simple. By using the coordinate rather than , we see that the metric components depend on alone. We can exploit this property for the task of template placement as follows: First, choose a ``surface'' of constant , and on this surface place templates at intervals in of for the entire range of . Here, . Then choose the next surface of constant with and repeat the placement of templates on this surface. This can be iterated until the entire range of has been covered; the collection of templates should now cover the entire parameter region with no point in the region being farther than from the nearest template.

- Author: Jolien Creighton, jolien@tapir.caltech.edu