Derivation and analysis of fast bilinear algorithms for convolution
From MaRDI portal
Abstract: 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.
Recommendations
- Error Analysis and Improving the Accuracy of Winograd Convolution for Deep Neural Networks
- Automatic derivation and implementation of fast convolution algorithms
- scientific article; zbMATH DE number 3994906
- A decomposable Winograd method for N-D convolution acceleration in video analysis
- Fast computation of convolution operations via low-rank approximation
Cites work
- A fast algorithm for solving a Toeplitz system of equations
- A fast, high-order algorithm for the solution of surface scattering problems: Basic implementation, tests, and applications
- Accuracy and Stability of Numerical Algorithms
- Asymptotically fast solution of Toeplitz and related systems of linear equations
- Automatic derivation and implementation of fast convolution algorithms
- Comparison of the discrete singular convolution algorithm and the Fourier pseudospectral method for solving partial differential equations
- Efficient models for correlated data via convolutions of intrinsic processes
- Even faster integer multiplication
- Every matrix is a product of Toeplitz matrices
- Fast algorithms for signal processing.
- Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension
- Fast Fourier transform and convolution algorithms
- Fast multiplication of large numbers
- Fast polynomial multiplication and convolutions related to the discrete cosine transform
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Gaussian elimination is not optimal
- Hardware Efficient Fast Parallel FIR Filter Structures Based on Iterated Short Convolution
- How bad are Vandermonde matrices?
- How Can We Speed Up Matrix Multiplication?
- How to generate unknown orthogonal polynomials out of known orthogonal polynomials
- scientific article; zbMATH DE number 1682655 (Why is no real title available?)
- scientific article; zbMATH DE number 4160951 (Why is no real title available?)
- scientific article; zbMATH DE number 4054986 (Why is no real title available?)
- scientific article; zbMATH DE number 3688713 (Why is no real title available?)
- scientific article; zbMATH DE number 44502 (Why is no real title available?)
- scientific article; zbMATH DE number 193953 (Why is no real title available?)
- scientific article; zbMATH DE number 1042857 (Why is no real title available?)
- scientific article; zbMATH DE number 6973983 (Why is no real title available?)
- scientific article; zbMATH DE number 3322464 (Why is no real title available?)
- Iterative Toom-Cook methods for very unbalanced long integer multiplication
- Linear integral equations
- Multigrid accelerated tensor approximation of function related multidimensional arrays
- Neural architecture search: a survey
- New algorithms for digital convolution
- On tensor approximation of Green iterations for Kohn-Sham equations
- On the communication complexity of generalized 2-D convolution on array processors
- On the Minimum Computation Time of Functions
- On the rate of growth of condition numbers for convolution matrices
- Overlapped block digital filtering
- QR factorization of Toeplitz matrices
- Spectral Properties of Banded Toeplitz Matrices
- Tensor Decomposition for Signal Processing and Machine Learning
- Tensor Decompositions and Applications
- The Discrete Cosine Transform
- Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0
Cited in
(4)- Convolution accelerator designs using fast algorithms
- A decomposable Winograd method for N-D convolution acceleration in video analysis
- Fast Convolution Method and Its Application in Mask Optimization for Intensity Calculation Using Basis Expansion
- Communication lower bounds for nested bilinear algorithms via rank expansion of Kronecker products
Describes a project that uses
Uses Software
This page was built for publication: Derivation and analysis of fast bilinear algorithms for convolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140608)
