  The prevalence of convolution in applications within signal processing, deep
neural networks, and numerical solvers has motivated the development of
numerous fast convolution algorithms. In many of these problems, convolution is
performed on terabytes or petabytes of data, so even constant factors of
improvement can significantly reduce the computation time. We leverage the
formalism of bilinear algorithms to describe and analyze all of the most
popular approaches. This unified lens permits us to study the relationship
between different variants of convolution as well as to derive error bounds and
analyze the cost of the various algorithms. We provide new derivations, which
predominantly leverage matrix and tensor algebra, to describe the Winograd
family of convolution algorithms as well as reductions between 1D and
multidimensional convolution. We provide cost and error bounds as well as
experimental numerical studies. Our experiments for two of these algorithms,
the overlap-add approach and Winograd convolution algorithm with polynomials of
degree greater than one, show that fast convolution algorithms can rival the
accuracy of the fast Fourier transform (FFT) without using complex arithmetic.
These algorithms can be used for convolution problems with multidimensional
inputs or for filters larger than size of four, extending the state-of-the-art
in Winograd-based convolution algorithms.
