{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T05:32:38Z","timestamp":1780378358881,"version":"3.54.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:00:00Z","timestamp":1604707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001602","name":"Science Foundation Ireland","doi-asserted-by":"crossref","award":["12\/IA\/1381 and 13\/RC\/2094"],"award-info":[{"award-number":["12\/IA\/1381 and 13\/RC\/2094"]}],"id":[{"id":"10.13039\/501100001602","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Lero\u2014the Irish Software Research Centre"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>Popular deep neural networks (DNNs) spend the majority of their execution time computing convolutions. The Winograd family of algorithms can greatly reduce the number of arithmetic operations required and is used in many DNN software frameworks. However, the performance gain is at the expense of a reduction in floating point (FP) numerical accuracy. In this article, we analyse the worst-case FP error and derive an estimation of the norm and conditioning of the algorithm. We show that the bound grows exponentially with the size of the convolution. Further, the error bound of the modified algorithm is slightly lower but still exponential. We propose several methods for reducing FP error. We propose a canonical evaluation ordering based on Huffman coding that reduces summation error. We study the selection of sampling \u201cpoints\u201d experimentally and find empirically good points for the most important sizes. We identify the main factors associated with good points. In addition, we explore other methods to reduce FP error, including mixed-precision convolution, and pairwise summation across DNN channels. Using our methods, we can significantly reduce FP error for a given block size, which allows larger block sizes to be used and reduced computation.<\/jats:p>","DOI":"10.1145\/3412380","type":"journal-article","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T17:07:56Z","timestamp":1604768876000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Error Analysis and Improving the Accuracy of Winograd Convolution for Deep Neural Networks"],"prefix":"10.1145","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7303-2511","authenticated-orcid":false,"given":"Barbara","family":"Barabasz","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Anderson","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kirk M.","family":"Soodhalter","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032168"},{"key":"e_1_2_1_2_1","volume-title":"Discrete Mathematics (2nd. ed.)","author":"Biggs Norman L.","unstructured":"Norman L. Biggs . 2002. Discrete Mathematics (2nd. ed.) . Oxford University Press , New York, NY . Norman L. Biggs. 2002. Discrete Mathematics (2nd. ed.). Oxford University Press, New York, NY."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01395989"},{"key":"e_1_2_1_4_1","volume-title":"Fast Algorithms for Signal Processing","author":"Blahut Richard E.","unstructured":"Richard E. Blahut . 2010. Fast Algorithms for Signal Processing . Cambridge University Press , New York, NY . Richard E. Blahut. 2010. Fast Algorithms for Signal Processing. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Arithmetic of Finite Fields","author":"Bodrato Marco","unstructured":"Marco Bodrato . 2007. Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0 . In Arithmetic of Finite Fields . Lecture Notes in Computer Science , Vol. 4547 . Springer , 116--133. Marco Bodrato. 2007. Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0. In Arithmetic of Finite Fields. Lecture Notes in Computer Science, Vol. 4547. Springer, 116--133."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0061-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502407627"},{"key":"e_1_2_1_9_1","volume-title":"Norm estimates for inverses of Vandermonde matrices. Numerische Mathematik. 23 (Aug","author":"Gautschi Walter","year":"1974","unstructured":"Walter Gautschi . 1974. Norm estimates for inverses of Vandermonde matrices. Numerische Mathematik. 23 (Aug . 1974 ), 337--347. DOI:https:\/\/doi.org\/10.1007\/BF01438260 Walter Gautschi. 1974. Norm estimates for inverses of Vandermonde matrices. Numerische Mathematik. 23 (Aug. 1974), 337--347. DOI:https:\/\/doi.org\/10.1007\/BF01438260"},{"key":"e_1_2_1_10_1","first-page":"193","article-title":"How (un)stable are Vandermonde systems","volume":"124","author":"Gautschi Walter","year":"1990","unstructured":"Walter Gautschi . 1990 . How (un)stable are Vandermonde systems ? Asymptotic and Computational Analysis 124 (1990), 193 -- 210 . Walter Gautschi. 1990. How (un)stable are Vandermonde systems? Asymptotic and Computational Analysis 124 (1990), 193--210.","journal-title":"Asymptotic and Computational Analysis"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/103162.103163"},{"key":"e_1_2_1_12_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"2013","unstructured":"Gene H. Golub and Charles F . Van Loan . 2013 . Matrix Computations (4th ed.). Johns Hopkins University Press , Baltimore, MD. Gene H. Golub and Charles F. Van Loan. 2013. Matrix Computations (4th ed.). Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_2_1_14_1","volume-title":"Accuracy and Stability of Numerical Algorithms (2nd. ed.)","author":"Higham Nicholas J.","unstructured":"Nicholas J. Higham . 2002. Accuracy and Stability of Numerical Algorithms (2nd. ed.) . SIAM Publications, Philadelphia , PA. Nicholas J. Higham. 2002. Accuracy and Stability of Numerical Algorithms (2nd. ed.). SIAM Publications, Philadelphia, PA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_16_1","volume-title":"Retrieved","author":"Kahan William","year":"1996","unstructured":"William Kahan . 1996 . The Improbability of Probabilistic Error Analyses for Numerical Computations . Retrieved September 30, 2020 from https:\/\/people.eecs.berkeley.edu\/\u223cwkahan\/improber.pdf. William Kahan. 1996. The Improbability of Probabilistic Error Analyses for Numerical Computations. Retrieved September 30, 2020 from https:\/\/people.eecs.berkeley.edu\/\u223cwkahan\/improber.pdf."},{"key":"e_1_2_1_17_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming . Addison-Wesley . Donald E. Knuth. 1998. The Art of Computer Programming. Addison-Wesley."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.435"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1030170"},{"key":"e_1_2_1_20_1","volume-title":"VLSI Digital Signal Processing Systems: Design and Implementation","author":"Parhi Keshab K.","unstructured":"Keshab K. Parhi . 2007. VLSI Digital Signal Processing Systems: Design and Implementation . John Wiley 8 Sons, New York, NY. Keshab K. Parhi. 2007. VLSI Digital Signal Processing Systems: Design and Implementation. John Wiley 8 Sons, New York, NY."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645671"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068816X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298594"},{"key":"e_1_2_1_24_1","volume-title":"Algorithms for Discrete Fourier Transform and Convolution (2nd. ed.)","author":"Tolimieri Richard","unstructured":"Richard Tolimieri , Myoung An , and Chao Lu. 1997. Algorithms for Discrete Fourier Transform and Convolution (2nd. ed.) . Springer-Verlag , New York, NY . Richard Tolimieri, Myoung An, and Chao Lu. 1997. Algorithms for Discrete Fourier Transform and Convolution (2nd. ed.). Springer-Verlag, New York, NY."},{"key":"e_1_2_1_25_1","volume-title":"The complexity of a scheme of functional elements realizing multiplication of integers. Soviet Mathematics\u2014Doklady 3","author":"Toom Andrei L.","year":"1963","unstructured":"Andrei L. Toom . 1963. The complexity of a scheme of functional elements realizing multiplication of integers. Soviet Mathematics\u2014Doklady 3 ( 1963 ), 714--716. Andrei L. Toom. 1963. The complexity of a scheme of functional elements realizing multiplication of integers. Soviet Mathematics\u2014Doklady 3 (1963), 714--716."},{"key":"e_1_2_1_26_1","volume-title":"Trefethen and David Bau","author":"Lloyd","year":"1997","unstructured":"Lloyd N. Trefethen and David Bau . 1997 . Numerical Linear Algebra. SIAM , Philadelphia, PA. Lloyd N. Trefethen and David Bau. 1997. Numerical Linear Algebra. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 5th International Conference on Learning Representations. 4.","author":"Vincent Kevin","year":"2017","unstructured":"Kevin Vincent , Kevin Stephano , Michael Frumkin , Boris Ginsburg , and Julien Demouth . 2017 . On improving the numerical stability of Winograd convolutions . In Proceedings of the 5th International Conference on Learning Representations. 4. Kevin Vincent, Kevin Stephano, Michael Frumkin, Boris Ginsburg, and Julien Demouth. 2017. On improving the numerical stability of Winograd convolutions. In Proceedings of the 5th International Conference on Learning Representations. 4."},{"key":"e_1_2_1_28_1","volume-title":"Rounding Errors in Algebraic Processes","author":"Wilkinson James H.","unstructured":"James H. Wilkinson . 1994. Rounding Errors in Algebraic Processes . Dover Publications , New York, NY . James H. Wilkinson. 1994. Rounding Errors in Algebraic Processes. Dover Publications, New York, NY."},{"key":"e_1_2_1_29_1","volume-title":"Arithmetic Complexity Computations","author":"Winograd Shmuel","unstructured":"Shmuel Winograd . 1980a. Arithmetic Complexity Computations . SIAM Publications, Bristol , England . Shmuel Winograd. 1980a. Arithmetic Complexity Computations. SIAM Publications, Bristol, England."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1980.1171044"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412380","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3412380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:01Z","timestamp":1750195501000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3412380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,7]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3412380"],"URL":"https:\/\/doi.org\/10.1145\/3412380","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,7]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}