对称Toeplitz矩阵相乘的一种快速算法

A fast algorithm for the multiplication of Symmetric Toeplitz matrices

本文将Toeplitz矩阵分解为循环矩阵和下三角矩阵之和,以及一般卷积向循环卷积的转化,借助快速Fouier算法(FFT),给出了一种对称Toeplitz矩阵相乘的快速算法,其算法复杂性为2n2+O(nlog2n)次实乘次数,2n2-4n+2次实加次数,较之前的算法在时间复杂性上有所改善。

In this paper, I am going to decompose a Toeplitz matrix into the multiplication of a cyclic matrix and a lower triangular matrix.Meanwhile,I will talk about the conversion from a common convolution into a cyclic convolution. Using the fast Fouler algorithm（FFT）,I have a given out a fast algorithm for the multiplication of Symmetric Toeplitz matrices. Its algorithm complexity is 2n^2＋O（nlog2n）multipiies times, 2n2-4n＋2 plus times.Compared with the former algorithm,this method has improved in time complexity.