×

A new fast algorithm for products of Toeplitz matrices. (Chinese. English summary) Zbl 1199.65152

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
PDFBibTeX XMLCite