---
title: "Fast Algorithms for Convolutional Neural Networks — Lavin 2015"
description: "Vision convnets are costly to run. 14 references, cited by 85 papers here. Among them: 69."
authors: ["Andrew Lavin", "Scott Gray"]
year: 2015
venue: "CVPR 2016"
source: "https://arxiv.org/abs/1509.09308"
arxiv: "1509.09308"
licence: "arXiv — non-exclusive distribution license (arXiv OAI)"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/lavin-2015-fast-algorithms-convolutional-neural-networks/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/lavin-2015-fast-algorithms-convolutional-neural-networks/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2015](https://md.research.elamur.ai/free/en/papers/2015/page/2/) / Fast Algorithms for Convolutional Neural Networks

# Fast Algorithms for Convolutional Neural Networks

**Authors:** Andrew Lavin and [Scott Gray](https://md.research.elamur.ai/free/en/authors/scott-gray/) · **Year:** 2015 · **Venue:** CVPR 2016 · **Licence:** [arXiv — non-exclusive distribution license (arXiv OAI)](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1509.09308) · [PDF](https://arxiv.org/pdf/1509.09308) · [arXiv 1509.09308](https://arxiv.org/abs/1509.09308) · [OpenAlex](https://openalex.org/W2949245006)

**Citations:** 69 citations (OpenAlex, 2026-10-14) · [85](https://md.research.elamur.ai/free/en/papers/lavin-2015-fast-algorithms-convolutional-neural-networks/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Vision convnets are costly to run. Low-latency inference, mobile deployment and distributed training with small per-node batches all need convolution that stays fast with tiny 3×3 filters and small batches. FFT-based convolution suits large filters and big batches, so it fits this regime poorly. Lavin and Gray adapt Winograd's minimal filtering algorithms to convnet layers. Images are split into overlapping tiles, and both tiles and filters are mapped into a transform domain. They are multiplied element-wise there and then mapped back. Summing over input channels before the inverse transform turns most of the arithmetic into dense matrix multiplications, which stay efficient even at batch size 1. The authors derive F(2×2,3×3) and F(4×4,3×3) for the forward pass, plus F(3×3,2×2) for weight gradients, and analyse numeric error. They benchmark a Titan X GPU kernel for F(2×2,3×3) on VGG Network E against cuDNN v3. It wins at every batch size from 1 to 64 and needs little extra memory, showing that algebraic restructuring can substantially accelerate modern convnets.

## Key points
- **Multiplication savings:**
  - F(2×2,3×3) uses 16 multiplications per output tile instead of 36, a 2.25× arithmetic reduction.
  - F(4×4,3×3) uses 36 instead of 144, a 4× reduction.
  - The cost is that transform overhead and numeric error grow with tile size.
- **Hardware and metric:** The test GPU was a Titan X with 6.96 TFLOPS device peak. Speed is reported as "Effective TFLOPS," meaning direct-convolution FLOPs divided by runtime, so it can exceed peak.
- **Speed with fp32:**
  - F(2×2,3×3) beats cuDNN by 2.26× at N=1 and 1.48× at N=64.
  - The biggest gains, up to 7.28×, occur at intermediate N, where cuDNN chose a slow FFT path.
  - Throughput at N=16 is 9.49 TFLOPS.
- **Speed with fp16:** F(2×2,3×3) reaches 10.28 TFLOPS at N=64 and 9.57 TFLOPS at N=8.
- **Memory and accuracy:**
  - cuDNN's FFT path used up to 2.6 GB of workspace. The fused Winograd kernel needs none, and the external-filter-transform (FX) variant needs at most 16 MB.
  - In fp32, F(2×2,3×3) is slightly more accurate than direct convolution.
  - F(4×4,3×3) has larger error but remains more accurate than direct convolution on fp16 data.

## Interesting ideas
- **Reduce before the inverse transform.** Doing the channel reduction inside the transform domain spreads the inverse-transform cost over all channels. It also turns the core work into batched matrix multiplies. Reorganizing a computation so its heavy part becomes GEMM is a widely reusable trick for getting efficient hardware utilization.
- **Measure speed in algorithm-independent units.** Normalizing every method by the FLOPs of the naive algorithm makes fast algorithms directly comparable with baselines. It also exposes when an algorithmic saving beats raw hardware peak, which is useful for any benchmark of approximate or fast methods.
- **Test accuracy against a high-precision reference.** Error was measured on random uniform inputs, with direct convolution in double precision as ground truth. This gives a cheap, model-independent way to check that a numerically riskier method stays within the tolerance a low-precision model already accepts.
- **Split one huge convolution into many small ones.** The weight gradient would require an impractically large filtering problem. The authors break it into a sum of small tiled convolutions such as F(3×3,2×2), which shows how a size mismatch can be fixed by tiling rather than by a new algorithm.
- **Choose the kernel variant per layer.** Precomputing the filter transform (FX) or fusing it into the main kernel works better depending on filter and channel counts. Selecting the variant per layer, with workspace size treated as a first-class constraint, is a sensible design habit for performance libraries.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [👁️ Computer Vision and Pattern Recognition](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-vision-and-pattern-recognition/) · 3,486 works · [🔌 Hardware and Architecture](https://md.research.elamur.ai/free/en/shelves/computer-science/hardware-and-architecture/) · 167 works · [🔊 Signal Processing](https://md.research.elamur.ai/free/en/shelves/computer-science/signal-processing/) · 493 works

## Cite

Cite as: Andrew Lavin and Scott Gray. 2015. Fast Algorithms for Convolutional Neural Networks. CVPR 2016.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{lavin2015fast,
  title = {{Fast Algorithms for Convolutional Neural Networks}},
  author = {Andrew Lavin and Scott Gray},
  booktitle = {CVPR 2016},
  year = {2015},
  eprint = {1509.09308},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.09308}
}
```

- [← previous Accurate Evaluation of Segment-level Machine Translation Metrics](https://md.research.elamur.ai/free/en/papers/graham-2015-accurate-evaluation-segment-level-machine/)
- [next → On the semantics and pragmatics of epistemic vocabulary](https://md.research.elamur.ai/free/en/papers/moss-2015-semantics-pragmatics-epistemic-vocabulary/)
- [↑ back to papers of 2015](https://md.research.elamur.ai/free/en/papers/2015/page/2/)

## References

14 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. cuDNN. [https://developer.nvidia.com/cudnn](https://developer.nvidia.com/cudnn). Accessed: 2015-11-01. 1, 7 [↗](https://developer.nvidia.com/cudnn)
2. Richard E Blahut. Fast algorithms for signal processing. Cambridge University Press, 2010. 3, 4 [find](https://scholar.google.com/scholar?q=Richard+E+Blahut%2E+Fast+algorithms+for+signal+processing%2E+Cambridge+University+Press%2C+2010%2E+3%2C+4)
3. Jason Cong and Bingjun Xiao. Minimizing computation in convolutional neural networks. In Artificial Neural Networks and Machine Learning–ICANN 2014, pages 281–290. Springer, 2014. 1, 5 [find](https://scholar.google.com/scholar?q=Jason+Cong+and+Bingjun+Xiao%2E+Minimizing+computation+in+convolutional+neural+networks%2E+In+Artificial+Neural+Networks+and+Machine+Learning%E2%80%93ICANN+2014%2C+pages+281%E2%80%93290%2E+Springer%2C+2014%2E+1%2C+5)
4. Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. Low precision arithmetic for deep learning. CoRR, abs/1412.7024, 2014. 4, 7 — [arXiv:1412.7024](https://arxiv.org/abs/1412.7024) [find](https://scholar.google.com/scholar?q=Matthieu+Courbariaux%2C+Yoshua+Bengio%2C+and+Jean%2DPierre+David%2E+Low+precision+arithmetic+for+deep+learning%2E+CoRR%2C+abs%2F1412%2E7024%2C+2014%2E+4%2C+7+%E2%80%94+%5BarXiv%3A1412%2E7024%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1412%2E7024%29)
5. Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. arXiv preprint arXiv:1502.02551, 2015. 4, 7 [find](https://scholar.google.com/scholar?q=Suyog+Gupta%2C+Ankur+Agrawal%2C+Kailash+Gopalakrishnan%2C+and+Pritish+Narayanan%2E+Deep+learning+with+limited+numerical+precision%2E+arXiv+preprint+arXiv%3A1502%2E02551%2C+2015%2E+4%2C+7)
6. Suyog Gupta, Wei Zhang, and Josh Milthrope. Model accuracy and runtime tradeoff in distributed deep learning. arXiv preprint arXiv:1509.04210, 2015. 1 — [arXiv:1509.04210](https://arxiv.org/abs/1509.04210) [find](https://scholar.google.com/scholar?q=Suyog+Gupta%2C+Wei+Zhang%2C+and+Josh+Milthrope%2E+Model+accuracy+and+runtime+tradeoff+in+distributed+deep+learning%2E+arXiv+preprint+arXiv%3A1509%2E04210%2C+2015%2E+1+%E2%80%94+%5BarXiv%3A1509%2E04210%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1509%2E0)
7. Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015. 1 [find](https://scholar.google.com/scholar?q=Sergey+Ioffe+and+Christian+Szegedy%2E+Batch+normalization%3A+Accelerating+deep+network+training+by+reducing+internal+covariate+shift%2E+arXiv+preprint+arXiv%3A1502%2E03167%2C+2015%2E+1)
8. Alex Krizhevsky. [One weird trick for parallelizing convolutional neural networks](https://md.research.elamur.ai/free/en/papers/krizhevsky-2014-one-weird-trick-parallelizing-convolutional/). arXiv preprint arXiv:1404.5997, 2014. 1
9. V. Madisetti. The Digital Signal Processing Handbook. Number v. 2 in Electrical engineering handbook series. CRC, 2010. 4, 5 [find](https://scholar.google.com/scholar?q=V%2E+Madisetti%2E+The+Digital+Signal+Processing+Handbook%2E+Number+v%2E+2+in+Electrical+engineering+handbook+series%2E+CRC%2C+2010%2E+4%2C+5)
10. Michaël Mathieu, Mikael Henaff, and Yann LeCun. Fast training of convolutional networks through ffts. CoRR, abs/1312.5851, 2013. 1, 4 — [arXiv:1312.5851](https://arxiv.org/abs/1312.5851) [find](https://scholar.google.com/scholar?q=Michae%CC%88l+Mathieu%2C+Mikael+Henaff%2C+and+Yann+LeCun%2E+Fast+training+of+convolutional+networks+through+ffts%2E+CoRR%2C+abs%2F1312%2E5851%2C+2013%2E+1%2C+4+%E2%80%94+%5BarXiv%3A1312%2E5851%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1312%2E5851%29)
11. Karen Simonyan and Andrew Zisserman. [Very deep convolutional networks for large-scale image recognition](https://md.research.elamur.ai/free/en/papers/simonyan-2014-very-deep-convolutional-networks-large/). arXiv preprint arXiv:1409.1556, 2014. 1, 7
12. Nicolas Vasilache, Jeff Johnson, Michaël Mathieu, Soumith Chintala, Serkan Piantino, and Yann LeCun. Fast convolutional nets with fbfft: A GPU performance evaluation. CoRR, abs/1412.7580, 2014. 1, 4, 7 [find](https://scholar.google.com/scholar?q=Nicolas+Vasilache%2C+Jeff+Johnson%2C+Michae%CC%88l+Mathieu%2C+Soumith+Chintala%2C+Serkan+Piantino%2C+and+Yann+LeCun%2E+Fast+convolutional+nets+with+fbfft%3A+A+GPU+performance+evaluation%2E+CoRR%2C+abs%2F1412%2E7580%2C+2014%2E+1%2C+4%2C)
13. Shmuel Winograd. Arithmetic complexity of computations, volume 33. Siam, 1980. 1, 2, 3, 4 [find](https://scholar.google.com/scholar?q=Shmuel+Winograd%2E+Arithmetic+complexity+of+computations%2C+volume+33%2E+Siam%2C+1980%2E+1%2C+2%2C+3%2C+4)
14. Shmuel Winograd. On multiplication of polynomials modulo a polynomial. SIAM Journal on Computing, 9(2):225–229, 1980. 2 [find](https://scholar.google.com/scholar?q=Shmuel+Winograd%2E+On+multiplication+of+polynomials+modulo+a+polynomial%2E+SIAM+Journal+on+Computing%2C+9%282%29%3A225%E2%80%93229%2C+1980%2E+2)

*Updated 2 November 2026*