Fast And Parallel Algorithm For The Discrete Sine Transform And Toeplitz Systems

The discrete sinusoidal transform and Toeplitz systems have been applied comprehensively in science and engineering. For example, the discrete Fourier transform and sine transform have become important tools in signal processing, and many problems' solving, such as the filter coefficients in the design of recursive digital filters, the RCS of dipole-array antennas, the unknown parameters of stationary auto-regressives models in time series analysis, and minimum realization problems in control theory, Toeplitz systems is necessary.Therefore, in this paper we study fast algorithm for discrete sine transform^ the scaled discrete sine transforms fast and parallel solution for Toeplitz systems, and finally, the image superrresolution technique is achieved by using wavelets , preconditioned conjugate gradient method. The content are organized as follows.1. The related algebra properties that integers maps integers via lifting scheme is discussed, and a floating fast algorithm for the discrete sine transform is proposed, on this basis, scaled integer discrete sine transform is achieved. As its application, a scaled discrete cosine transform is also proposed, the computational complexity for new algorithm is optimal, and serious drawbacks that the transform lengths is limited existing in known optimal algorithm is completely overcome.2. The property that wavelet transform act to Toeplitz matrix is discussed. Under a certain of conditions, we show Toeplitz matrix become a near-band Toeplitz matrix, therefore, a fast solution that the computational complexity is O(n) is achieved, the considerable decrease in complexity is obtained compared to the known preconditioned conjugate gradient method with O(nlogn) cost.3. A new parallel algorithm for Toeplitz system is presented, its computational complexity is O(n) by using n processors, since computational complexity for Levinsion recursive algorithm is O(nlogn), so the new algorithm is highly efficient. In particular, for near-tridiagonal Toeplitz system, a parallel algorithm with perfect parallelism is achieved.4 . Using the combination of wavelet, Tikhonov regularization and preconditioned conjugate gradient method ,a highly precision, fast image superresolution method is achieved, the main technique index is superior to that Of the known superresolution method.