High-Performance Algorithm Of Real Block Toeplitz Matrix

Block Toeplitz matrices often appear in the computer timing analysis, autoregres-sive time series model filtering. While dealing with the calculation of a block Toeplitz matrix (such as vector product, solving linear equations, eigenvalue calculation, etc.), if the order of the matrix is small, the usual classical algorithms (such as LU decomposition algorithms, QR algorithms, etc) are feasible. But in many practical applications, the order of the matrix or the size of a linear system of equations solved by iterations until getting a satisfactory result is usually large. Then the usual classical algorithms are so expensive that they have no practical meanings.In this thesis we will design some numerical stable and/or fast algorithms for the real block Toeplitz matrices by exploiting their particular structure and the nature. This thesis is divided into five chapters which are listed as follows:The first chapter is an introduction, in which we describes the research backgro-und, the motivation of choice of the theme, as well as research content.The second chapter is prerequisites, including of some basic definitions, theore-ms, and notation often used in sequel.In the third chapter we discuss how to embed or split a real block Toplitz matrix for the computation of a matrix-vector product by exploiting the particular structure, and then using the block fast Fourier transform, some fast, high-performance algorit-hms are obtained.Some algorithms for the real block Toplitz-Toplitz block matrix vector product based on the discussion of the previous chapters are presented in the forth chapter, s-ome comparison for the performance of two different methods are also given.In the fifth chapter we describe a fast algorithm of real block Toplitz-Toplitz bl-ock matrix based on a discrete bi-orthogonal wavelet transformation. In the real sequ-nce data processing, not only the discrete wavelet transformation is equivalent to the discrete Fourier transform, but also its inverse transformation has the same form, and only real operations are required, the storage and complexity of our algorithm is more economical than one used DFT. Compared with the general triangle transformation, t-e compactly supported orthogonal wavelet transformation can preserve the structure of the matrix under consideration, while this structure is useful for solving a linear system of equations by any iterative procedure, especially for large BTTB linear system.