Toeplitz矩阵以及矩阵乘法FFT加速

1.Toeplitz矩阵

托普利兹矩阵，简称为T型矩阵，它是由Bryc、Dembo、Jiang于2006年提出的。托普利兹矩阵的主对角线上的元素相等，平行于主对角线的线上的元素也相等；矩阵中的各元素关于次对角线对称，即T型矩阵为次对称矩阵。这里我们使用matlab中自带的函数生成一个toeplitz矩阵的例子：

x=[1 2 3 4];
y=[1 5 6 7 8 9];
z=toeplitz(x,y);


我们可以得到一个这样的矩阵结果：

我们可以看到，其中x中的元素变成了第一列，y中的元素变成了第一行，注意x与y的第一个元素必须相同，我们可以看出toeplitz矩阵并不一定是方阵，而是可以任意长宽。当然也有做对称方阵的简单做法：

xx=[1 2 3 4 5];
zz=toeplitz(xx);


这样得到的方阵就是一个对角对称的toeplitz矩阵：

2.Toeplitz矩阵的乘法加速

在矩阵乘法中我们经常遇到这样的乘法Ax=b.其中A矩阵为toeplitz矩阵并且数量很大时我们完全可以通过toeplitze矩阵的特性来达到减少计算量的效果。具体如何做到我们如下操作：

n=5;
E=zeros(n,1); E2=zeros(2*n-1,1);J2=zeros(2*n-1,1);
G_p=zeros(2*n-1,1);
G1=rand(n,1); G2=rand(n,1); G1(1,1)=G2(1,1); %这两个一维向量用来生成toeplitz矩阵
toep=toeplitz(G1,G2);
G=[G1;G2(n:-1:2,1)]; %将两个向量合并起来
J=rand(n,1);
E=toep*J; %方法一
J2(1:n,1)=J;
E2=ifft(fft(G).*fft(J2)); %方法二


由此我们可以得到两种方式计算得到的结果，其中方法一是直接用矩阵相乘得到的，而方法二则是利用fft得到结果，可以看到在使用方法二的时候我们将J这个向量进行了拓展，长度从n增加到了2n-1这就是为了保证fft之后的结果长度相等，因此我们最后得到的E2其实也是一个长度为2n-1的数据，因此我们只取其中的前n个数据与E进行比较：

可以发现，前n项的大小是一致的，因此我们就可以用fft的方法来代替直接矩阵相乘，这样做的好处可以从计算效率以及内存两方面考虑。

计算量方面，矩阵相乘的计算量是(n^{3),而利用fft计算的话计算量是（n}2logn）;

内存方面，矩阵相乘需要存储整个方阵，也就是（n^2）个数据，使用fft加速则只需要存储（n）个数据即可。