Editing Convolution (section)

=== Fast convolution algorithms ===

In many situations, discrete convolutions can be converted to circular convolutions so that fast transforms with a convolution property can be used to implement the computation. For example, convolution of digit sequences is the kernel operation in [[multiplication]] of multi-digit numbers, which can therefore be efficiently implemented with transform techniques ({{harvnb|Knuth|1997|loc=§4.3.3.C}}; {{harvnb|von zur Gathen|Gerhard|2003|loc=§8.2}}).

{{EquationNote|Eq.1}} requires {{mvar|N}} arithmetic operations per output value and {{math|''N''<sup>2</sup>}} operations for {{mvar|N}} outputs. That can be significantly reduced with any of several fast algorithms. [[Digital signal processing]] and other applications typically use fast convolution algorithms to reduce the cost of the convolution to O({{mvar|N}} log {{mvar|N}}) complexity.

The most common fast convolution algorithms use [[fast Fourier transform]] (FFT) algorithms via the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]. Specifically, the [[circular convolution]] of two finite-length sequences is found by taking an FFT of each sequence, multiplying pointwise, and then performing an inverse FFT. Convolutions of the type defined above are then efficiently implemented using that technique in conjunction with zero-extension and/or discarding portions of the output. Other fast convolution algorithms, such as the [[Schönhage–Strassen algorithm]] or the Mersenne transform,<ref name=Rader1972>{{cite journal|last=Rader|first=C.M.|title=Discrete Convolutions via Mersenne Transforms|journal=IEEE Transactions on Computers|date=December 1972|volume=21|issue=12|pages=1269–1273|doi=10.1109/T-C.1972.223497|s2cid=1939809}}</ref> use fast Fourier transforms in other [[ring (mathematics)|ring]]s. The Winograd method is used as an alternative to the FFT.<ref>{{Cite book |last=Winograd |first=Shmuel |url=https://epubs.siam.org/doi/book/10.1137/1.9781611970364 |title=Arithmetic Complexity of Computations |date=January 1980 |publisher=Society for Industrial and Applied Mathematics |isbn=978-0-89871-163-9 |language=en |doi=10.1137/1.9781611970364}}</ref> It significantly speeds up 1D,<ref>{{Cite journal |last1=Lyakhov |first1=P. A. |last2=Nagornov |first2=N. N. |last3=Semyonova |first3=N. F. |last4=Abdulsalyamova |first4=A. S. |date=June 2023 |title=Reducing the Computational Complexity of Image Processing Using Wavelet Transform Based on the Winograd Method |url=https://link.springer.com/10.1134/S1054661823020074 |journal=Pattern Recognition and Image Analysis |language=en |volume=33 |issue=2 |pages=184–191 |doi=10.1134/S1054661823020074 |s2cid=259310351 |issn=1054-6618}}</ref> 2D,<ref>{{Cite journal |last1=Wu |first1=Di |last2=Fan |first2=Xitian |last3=Cao |first3=Wei |last4=Wang |first4=Lingli |date=May 2021 |title=SWM: A High-Performance Sparse-Winograd Matrix Multiplication CNN Accelerator |url=https://ieeexplore.ieee.org/document/9373543 |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |volume=29 |issue=5 |pages=936–949 |doi=10.1109/TVLSI.2021.3060041 |s2cid=233433757 |issn=1063-8210}}</ref> and 3D<ref>{{Cite journal |last1=Mittal |first1=Sparsh |last2=Vibhu |date=May 2021 |title=A survey of accelerator architectures for 3D convolution neural networks |url=https://linkinghub.elsevier.com/retrieve/pii/S1383762121000400 |journal=Journal of Systems Architecture |language=en |volume=115 |pages=102041 |doi=10.1016/j.sysarc.2021.102041|s2cid=233917781 }}</ref> convolution.

If one sequence is much longer than the other, zero-extension of the shorter sequence and fast circular convolution is not the most computationally efficient method available.<ref name=Madisetti1999>{{cite book|editor-last=Madisetti |editor-first=Vijay K. |chapter=Fast Convolution and Filtering |first1=Ivan W. |last1=Selesnick |first2=C. Sidney |last2=Burrus |title=Digital Signal Processing Handbook |year=1999 |publisher=CRC Press |isbn=978-1-4200-4563-5 |page=Section 8}}</ref> Instead, decomposing the longer sequence into blocks and convolving each block allows for faster algorithms such as the [[overlap–save method]] and [[overlap–add method]].<ref name=Juang2004>{{cite web|last=Juang|first=B.H.|title=Lecture 21: Block Convolution|url=https://users.ece.gatech.edu/~juang/4270/BHJ4270-21.pdf |archive-url=https://web.archive.org/web/20040729204137/https://users.ece.gatech.edu/~juang/4270/BHJ4270-21.pdf |archive-date=2004-07-29 |url-status=live|publisher=EECS at the Georgia Institute of Technology|access-date=17 May 2013}}</ref> A hybrid convolution method that combines block and [[finite impulse response|FIR]] algorithms allows for a zero input-output latency that is useful for real-time convolution computations.<ref name=Gardner1994>{{cite journal|last=Gardner|first=William G.|title=Efficient Convolution without Input/Output Delay|journal=Audio Engineering Society Convention 97|date=November 1994|series=Paper 3897|url=https://cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/Ga95.PDF |archive-url=https://web.archive.org/web/20150408211312/https://cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/Ga95.PDF |archive-date=2015-04-08 |url-status=live|access-date=17 May 2013}}</ref>