Yu, Pinneng; Wang, Yu A new fast algorithm for products of Toeplitz matrices. (Chinese. English summary) Zbl 1199.65152 J. Numer. Methods Comput. Appl. 29, No. 3, 207-216 (2008). Summary: A new fast algorithm for the product of two Toeplitz matrices is presented, based on a new decomposition of a Toeplitz matrix into a cyclic matrix and a low-triangle Toeplitz matrix. Convolution is converted to cyclic convolution, and also the fast Fourier transform is employed to calculate cyclic convolution. Its arithmetic complexity is \(2n^2+\frac{63}{n}n\log_2n-15n-34\) real multiplication and \(4n^2+\frac{63}{n}n\log_2n-18n+23\) real addition. However, its multiplicative complexity reduces a little, additive complexity reduces by nearly \(\frac13\) compared to the optimized algorithm. The algorithm proposed in this paper owns the lowest complexity. MSC: 65F30 Other matrix algorithms (MSC2010) 65T50 Numerical methods for discrete and fast Fourier transforms 15B05 Toeplitz, Cauchy, and related matrices 65Y20 Complexity and performance of numerical algorithms Keywords:Toeplitz matrix; fast Fourier transform; cyclic convolution; products of Toeplitz matrices; fast algorithm; cyclic matrix; arithmetic complexity; multiplicative complexity; additive complexity PDFBibTeX XMLCite \textit{P. Yu} and \textit{Y. Wang}, J. Numer. Methods Comput. Appl. 29, No. 3, 207--216 (2008; Zbl 1199.65152)