基于小波变换与低秩校正的Toeplitz系统快速算法

Fast Algorithm for Toeplitz Systems Based on Wavelet Transform and Low Rank Update

讨论了Toeplitz方程组的快速求解方法．首先研究了Toeplitz矩阵在多进制小波变换下的代数结构．利用数值实验得到,对多项式偶函数生成的Toeplitz系统实施双正交9～7小波后矩阵在一定的精度下具有有限的带宽特性．结合低秩校正方法,得到一类Toeplitz系统的快速求解方法,运算量级为O(N),其中N为系统的阶．该方法与通常使用的直接快速算法以及预条件共轭梯度法(PCG)分别需要的复杂度O(N^2)以及O(Nlog_2N)相比,运算量有较大幅度的减少．

The fast algorithm for Toeplitz systems was studied. We first obtained the algebraic structure when M band wavelet transform was performed to Toeplitz matrix. By using numerical experiment under a precision, we showed that the matrix after wavelet transform was performed was featured by bandwidth for the generation function being polynomial. By using wavelet and low rank update approach, a fast algorithm for Toepliz system was proposed. The computational complexity was O （N）, where N was the order. Compared with the complexity O（N2）and O（N log2N）required in commonly used direct fast method and PCG method, the computational cost of the proposed algorithm was greatly reduced.