Spectral Problems Of Several Structured Matrices

Many important problems in engineering and applied sciences can be finally reduced to matrix computation problems. Moreover, various applications often introduce some special structures into the corresponding matrices. Among classical examples are Toeplitz matrices [a_i-j], Hankel matrices [a_i+j], Toeplitz-plus-Hankel matrices, Cauchy matrices (?) and others. When we deal with the related matrix problem (such as computing eigenvalue , solving linear systems and so on) with special structure, as we know, the standard linear algebra(such as Gaussian elimination algorithm, QR algorithm, etc)are, of course, readily available for small-size problems.However, in many practical applications, the order of matrices are very large (n - 10⁶ -10⁹) or the linear equations may have to be solved over and over again (such as iterative methods), with different problem or model parameters, until a satisfactory solution to the original physical problem is obtained.In such cases, the number of flops required to solve the related matrix problems can become prohibitively large so that these classical methods have no senses.Therefore, to achiving a fast and stable algorithm for these matrices with special of characteristic structure is an important issue in many applied areas.Thus, it is not surprising that in recent years the design of fast algorithms for structured matrices has become an increasingly important activity in a diverse variety of branches of the exact sciences. As to fast algorithms, perhaps the most widely and importantly known example of fast algorithms is the fast Fourier transform(FFT) .There are many classical fast algorithms which are been deduced by FFT. Its importance is widely acknowledged and nicely described in numerous papers and monographs, e.g., as follows: "The fast Fourier transform(FFT)is one of the truly great computational developments of this century. It has changed the face of science and engineering so that it is not an exaggeration to say that life as we know it would be very different without FFT " (Charles Van Loan, a famous mathematician).In this paper, we mainly discuss SVD of Hankel-circulant and Hankel-skew- circulant matrices and design a fast algorithm for symmetric Toeplitz-plus-Hankel matrices. As theoretical and numerical experiments results show, the fast algorithm is very useful.In chapter 1, we give a brief introduction to the importance, the current research situation and classical research methods on structured matrices. Moreover, some definition and properties of the structured matrices which are discussed in our paper have been given.In chapter 2, we present a fast symmetric Toeplitz-plus-Hankel matrix-vector product algorithm and apply the Lanczos-type tridiagonalization and QR-type diagonalization method to find all the eigenvalues of an n×n symmetric Toeplitz-plus-Hankel matrix in O(n² log n) operation.In chapter 3, we study the relation between real Hankel-circulant,Hankel-skew-circulant matrix and Hankel matrix. Moreover, we present several singular value decompositions of real Hankel-circulant and Hankel-skew-circulant matrices. The singular value decompositions of this chapter are given in explicit form which can be easily evaluated in computer programs and provide a useful basis for theoretical investigations.