  Astronomical radio bursts disperse while traveling through the interstellar
medium. To optimally detect a short-duration signal within a frequency band, we
have to precisely compensate for the pulse dispersion, which is a
computationally demanding task. We present the Fast Dispersion Measure
Transform (FDMT) algorithm for optimal detection of such signals. Our algorithm
has a low theoretical complexity of 2N_f N_t+ N_t N_d log_2(N_f) where N_f, N_t
and N_d are the numbers of frequency bins, time bins, and dispersion measure
bins, respectively. Unlike previously suggested fast algorithms our algorithm
conserves the sensitivity of brute force dedispersion. Our tests indicate that
this algorithm, running on a standard desktop computer, and implemented in a
high-level programming language, is already faster than the state of the art
dedispersion codes running on graphical processing units (GPUs). We also
present a variant of the algorithm that can be efficiently implemented on GPUs.
The latter algorithm's computation and data transport requirements are similar
to those of two-dimensional FFT, indicating that incoherent dedispersion can
now be considered a non-issue while planning future surveys. We further present
a fast algorithm for sensitive dedispersion of pulses shorter than normally
allowed by incoherent dedispersion. In typical cases this algorithm is orders
of magnitude faster than coherent dedispersion by convolution. We analyze the
computational complexity of pulsed signal searches by radio interferometers. We
conclude that, using our suggested algorithms, maximally sensitive blind
searches for such pulses is feasible using existing facilities. We provide an
implementation of these algorithms in Python and MATLAB.
