Lattice template placement for coherent all-sky searches for gravitational-wave pulsars

All-sky, broadband, coherent searches for gravitational-wave pulsars are restricted by limited computational resources. Minimizing the number of templates required to cover the search parameter space, of sky position and frequency evolution, is one important way to reduce the computational cost of a search. We demonstrate a practical algorithm which, for the first time, achieves template placement with a minimal number of templates for an all-sky search, using the reduced supersky parameter-space metric of Wette and Prix [Phys. Rev. D 88, 123005 (2013)]. The metric prescribes a constant template density in the signal parameters, which permits that templates be placed at the vertices of a lattice. We demonstrate how to ensure complete coverage of the parameter space, including in particular at its boundaries. The number of templates generated by the algorithm is compared to theoretical estimates and to previous predictions by Brady et al. [Phys. Rev. D 57, 2101 (1998)]. The algorithm may be applied to any search parameter space with a constant template density, which includes semicoherent searches and searches targeting known low-mass x-ray binaries.

Figure 1

Histograms of normalized mismatch $\mu /{\mu }_{\max }$ expected from lattice placement using (a) ${\mathbb{Z}}^n$ lattices and (b) $A_n^{*}$ lattices, with $n=2–5$. Each histogram was generated using $10^9$ simulated points.

Figure 2

Relative errors between ${\mu }_{\mathrm{rss}}$ and ${\mu }_0$ (a and b) and between ${\mu }_{\mathrm{rss}}$ and ${\mu }_{\mathrm{ss}}$ (c and d). Only the first spindown is used. Plotted are the median (solid line), the 25th to 75th percentile range (error bars), and the 2.5th (short-dashed line) and 97.5th (long-dashed line) percentiles of relative errors: as a function of $T$, averaged over $\mathrm{\Delta }{t}_{\text{start}}$ and $f_{\max }$ (a and c); and as a function of $\mathrm{\Delta }{t}_{\text{start}}$, averaged over $T$ and $f_{\max }$ (b and d). An $A_n^{*}$ lattice is used to generate random parameter offsets with ${\mu }_{\mathrm{rss}}\le 0.3$.

Figure 3

Relative errors between ${\mu }_{\mathrm{rss}}$ and ${\mu }_0$ (a and b) and between ${\mu }_{\mathrm{rss}}$ and ${\mu }_{\mathrm{ss}}$ (c and d). Both first and second spindowns are used. Plotted are the median (solid line), the 25th to 75th percentile range (error bars), and the 2.5th (short-dashed line) and 97.5th (long-dashed line) percentiles of relative errors: as a function of $T$, averaged over $\mathrm{\Delta }{t}_{\text{start}}$ and $f_{\max }$ (a and c); and as a function of $\mathrm{\Delta }{t}_{\text{start}}$, averaged over $T$ and $f_{\max }$ (b and d). An $A_n^{*}$ lattice is used to generate random parameter offsets with ${\mu }_{\mathrm{rss}}\le 0.3$.

Figure 4

Histograms of mismatches in ${\mu }_{\mathrm{rss}}$, ${\mu }_{\mathrm{ss}}$, and ${\mu }_0$, averaged over all simulated values of $T$, $\mathrm{\Delta }{t}_{\text{start}}$, and $f_{\max }$. Only the first spindown is used in (a); both first and second spindowns are used in (b). An $A_n^{*}$ lattice is used to generate random parameter offsets with ${\mu }_{\mathrm{rss}}\le 0.3$.

Figure 5

Illustration of a two-dimensional parameter space $\mathcal{P}$ (gray shaded area) whose boundaries (solid lines) are represented, per Eq. (9), by $1\le {\lambda }_0^{\mathrm{t}}\le 2$ and $2/{\lambda }_0^{\mathrm{t}}\le {\lambda }_1^{\mathrm{t}}\le 5/{\lambda }_0^{\mathrm{t}}$. Each boundary is labeled by its defining inequality.

Figure 6

Illustration of the boundary of a two-dimensional parameter space $\mathcal{P}$. Templates (crosses, dashed ellipses) are laid within the bound ${\lambda }_1^{\mathrm{t}}\le {\lambda }_1^{\max }$ (solid line); the gray shaded area indicates where $\mathcal{P}$ is covered by these templates. The white areas within the ${\lambda }_1^{\mathrm{t}}\le {\lambda }_1^{\max }$ bound are covered by laying templates outside the parameter space (circles, solid ellipses), up to ${\lambda }_1^{\mathrm{t}}\le {\lambda }_1^{\max }+0.5{\beta }_1$ (dashed line), where ${\beta }_1$ is the height of the metric ellipse bounding box (solid box).

Figure 7

Example of a lattice template bank in reduced supersky coordinates $(n_a,n_b)$, with $T=1$ day, $\mathrm{\Delta }{t}_{\text{start}}=0$, and ${\nu }_{\max }=100\mathrm{Hz}$. Templates and their metric ellipses are plotted as points and dashed lines, respectively. Templates, plotted as crosses, which lie outside the parameter-space boundaries (circles) are moved radially onto the nearest boundary (thick lines) when converted to physical coordinates $(\alpha ,\delta )$. An $A_n^{*}$ lattice is used to generate the template bank with ${\mu }_{\mathrm{rss}}\le 0.3$.

Figure 8

The projection of the example lattice template bank from Fig. 7 onto the sky sphere $|\overrightarrow{n}|=1$. Templates are plotted as points; lines are drawn from each template to its (up to) six nearest neighbors in the $A_n^{*}$ lattice.

Figure 9

Illustration of the $j({\overrightarrow{\lambda }}^{\mathrm{t}})$ lookup trie described in Sec. 4c. The trie is traversed top to bottom. Ovals denote the input and output nodes of the trie. Diamonds denote nodes where a branch is taken. Rectangles denote nodes where a stored value is retrieved. Cloud shapes denote nodes omitted for brevity.

Figure 10

Histograms of mismatches in ${\mu }_{\mathrm{rss}}$ and ${\mu }_{\mathrm{ss}}$, generated by the lattice template placement algorithm detailed in Sec. 4, and averaged over all values of $T$ and $\mathrm{\Delta }{t}_{\text{start}}$. The plots correspond to the parameter spaces (a) ${\mathrm{A}}_1$, (b) ${\mathrm{A}}_2$, (c) ${\mathrm{B}}_1$, and (d) ${\mathrm{B}}_2$ from Table 1. An $A_n^{*}$ lattice is used to place templates with ${\mu }_{\mathrm{rss}}\le 0.3$ (left column) and ${\mu }_{\mathrm{rss}}\le 0.6$ (right column).

Figure 11

Illustration of the staircase boundary template issue, using the example parameter space of Fig. 5. The parameter space to be covered is light gray. The short-dashed outline shows the area covered by the template bank, if the bounds ${\lambda }_1^{\min }({\lambda }_0^{\mathrm{t}})$ and ${\lambda }_1^{\max }({\lambda }_0^{\mathrm{t}})$ are computed exactly at the boundary templates (crosses). Regions of the parameter space not covered by this template bank are dark gray. The long-dashed outline shows the area covered if instead the bounds are extremized over the bounding box of each boundary template.

Figure 12

Number of templates required to search a coherent segment of time span $T$, centered on the reference time $t_0$ of Sec. 3b, over the following parameter spaces, using an $A_n^{*}$ lattice template bank with ${\mu }_{\max }=0.3$: (a) the whole sky, a fixed band in $f$ of [100,100.01] Hz, and a fixed band in $\dot{f}$ of $[-10^{-8},0]\mathrm{Hz}{\mathrm{s}}^{-1}$; (b) as above, with an additional fixed band in $\ddot{f}$ of $[0,10^{-18}]\mathrm{Hz}{\mathrm{s}}^{-2}$. Crosses denote the number $\mathcal{N}$ counted by the algorithm of Sec. 4; lines denote the number ${\mathcal{N}}_{\text{est}}$ estimated by the procedures described in Sec. 5. Black/gray denotes the template counts including/excluding the extra boundary templates discussed in Sec. 4e.

Figure 13

Number of templates required to search a coherent segment of time span T over the whole sky, a fixed band in $f$ of [0,200] Hz, and frequency-dependent bands in $\dot{f}$ of $\pm f/(10^3\mathrm{yr})$. The estimate of Brady et al. [15] (dashed line) is compared with an estimate following the procedure of Sec. 5 using the approximate ${\mathbf{g}}_{\mathrm{rss}}$ (solid line).

Figure 14

Local power-law exponent $p$ of the number of templates plotted in Figs. 12, with the first spindown (solid line), and 12 (dashed line), with both first and second spindowns. The thick horizontal lines denote the expected $p$, assuming that ${\mathcal{N}}_{\text{sky}}\propto T^2$ and ${\mathcal{N}}_{\text{freq}}\propto T^3$ (solid) or $T^6$ (dashed).