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

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

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

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 pre- cision,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(N~2)and O(N log_2N)required in commonly used direct fast method and PCG method, the computational cost of the proposed algorithm was greatly reduced.