Fast Algorithm for Toeplitz Systems Based on Wavelet Transform and Low Rank Update
Dehua Wang · Journal of Hunan University · 2007
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.