text: 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 present in many DNN software frameworks. However, the performance gain is at the expense of a reduction in floating point (FP) numerical accuracy. In this paper, we analyse the worst case FP error and prove the estimation of norm and conditioning of the algorithm. We show that the bound grows exponentially with the size of the convolution, but the error bound of the algorithm is smaller than the original one. 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 "points" 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 and reduced computation.
  @cite_9: Fast algorithms for matrix multiplication, namely those that perform asymptotically fewer scalar operations than the classical algorithm, have been considered primarily of theoretical interest. Apart from Strassen's original algorithm, few fast algorithms have been efficiently implemented or used in practical applications. However, there exist many practical alternatives to Strassen's algorithm with varying performance and numerical properties. Fast algorithms are known to be numerically stable, but because their error bounds are slightly weaker than the classical algorithm, they are not used even in cases where they provide a performance benefit. We argue in this paper that the numerical sacrifice of fast algorithms, particularly for the typical use cases of practical algorithms, is not prohibitive, and we explore ways to improve the accuracy both theoretically and empirically. The numerical accuracy of fast matrix multiplication depends on properties of the algorithm and of the input matrices, and we co...
  @cite_15: We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of Bini and Lotti [Numer. Math. 36:63–72, 1980]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in Cohn and Umans [Foundations of Computer Science, 44th Annual IEEE Symposium, pp. 438–449, 2003] and [Foundations of Computer Science, 46th Annual IEEE Symposium, pp. 379–388, 2005] are all included in the class of algorithms to which our analysis applies, and are therefore numerically stable. We perform detailed error analysis for three specific fast group-theoretic algorithms.
  @cite_1: Non commutative fast algorithms to compute 2×2 matrix product are classified with regard to stability. An analysis of the rounding error propagation is presented for then×n matrix multiplication algorithms obtained by recursive partitioning.
summary: To the best of our knowledge, this paper is the first that presents a theoretical analysis of the numerical error of Toom-Cook convolution. We demonstrate that the algorithm is unstable because the properties of algorithm parameters matrices we use ( @math , @math , @math ). We formulate the boundaries of the floating point errors for @math and @math dimensional kernels and inputs so we can resonable choose what we should focus on to improve the accuracy. We formulated the error boundaries for Toom-Cook convolution using similar techniqes to those used for another bilinear problem: the fast matrix multiplication, error estimation by Bini and Lotti @cite_1 , @cite_15 and @cite_9 . We show that algorithm is unstable and how the error depends on each component.