## 2 Key Steps in a FRB Search Pipeline
### Dedispersion
#### 2.2.2 Tree Dedispersion  
Brute force dedispersion can get computationally intensive very quickly for modern day FRB surveys given their large data volumes and high number of trial DMs. The tree dedispersion algorithm [21] uses the divide and conquer algorithm (similar to the Fast Fourier Transform [22]) to reduce the complexity of dedispersion. The complexity in this algorithm reduces from \(\mathcal{O}(N_{\text{t}}N_{\text{D}}N_{\
u})\) to \(\mathcal{O}(N_{\text{t}}N_{\ell m}log(N_{\
u}))\). This significant speed-up is obtained by first regularising the problem (represent the mathematical problem into a superposition of linear terms) and then eliminating all redundant additions. In spite of the large speed-ups in the calculation, there are overheads involved with the many add operations which still make this algorithm suited for many-core and GPU (Graphics processing unit) architectures. In a mathematical sense, the algorithm computes the following:  
\[\mathcal{I}(t)=\sum_{\
u}^{N_{\
u}}B(\
u,t+\delta t(d^{{}^{\prime}},\
u)), \tag{8}\]  
where \(\mathcal{I}(t)\) is the intensity of a given time sample, \(B\) is the intensity for a given time sample and observing frequency \(\
u\), and  
\[\delta t(d^{{}^{\prime}},\
u)=d^{{}^{\prime}}\left(\frac{\
u}{N_{\
u}-1}\right), \tag{9}\]  
for a bandwidth with \(N_{\
u}\) and a DM trial \(d^{{}^{\prime}}\) in the range \(0\leq d^{{}^{\prime}}<N_{\
u}\). This regularisation produces a delay function \(\delta t(d^{{}^{\prime}},\
u)\) that is a linear function of frequency. Hence, the DM can also be mapped to a linear function of frequency. Due to this regularisation, Equation (8) can be computed for different DMs in \(log_{2}N_{\
u}\) steps using the divide and conquer algorithm (as illustrated in Figure 3). While the algorithm reduces the number of computations, there are several constraints introduced by the method. The two key ones are that the DMs for which the data are dedispersed are not the efficiently distributed DM trial values that produce the most sensitive search, and that the algorithm sums over linear tracks. To overcome these, tree dedispersion can first run within subbands (cf. Section 2.2.1) and next we can combine their outcomes with the same algorithm. That way, tree dedispersion approximates the quadratic DM smear over the entire band while still preserving the efficient computation with regularisation.  
Figure 3: The tree dedispersion algorithm that uses the divide and conquer technique to remove redundant operations during dedispersion over many DM trials. The Figure has been adopted from [19].  
An algorithm that also recursively breaks down the problem, like tree dedispersion, is the fast dispersion measure transform (FDMT; [23]). FDMT (Figure 41) combines a low theoretical complexity as seen in tree dedispersion with the ability to sum over the exact quadratic dispersion curve as featured in brute force dedispersion. The latter is important especially when using high fractional bandwidths, high DMs, and/or low observing frequencies. While brute force dedispersion implementations successfully employ data reuse to allow real-time searching [20], and the problem is thus solved in practice, FDMT is intrinsically more efficient.