Fast Algorithm And Its Applications Of Several Structured Matrices

Many important problems in engineering and applied sciences ultimately can be reduced to matrix computation problems. Moreover, various applications often introduce a special structure into the corresponding matrices. Among classical examples are Toeplitz matrices [a_i-j], Hankel matrices [a_i+j], Vandermonde matrices [a_i^j-1], Cauchy matrices [1/((a_i)-(b_j))] and others. When we deal with the related matrix problems (such as solving linear systems, computing eigenvalue and so on) with special structure, as we know, the standard linear algebra methods(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 sense. Therefore, to achieving a fast and stable algorithm for these matrices with special or 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 trans form(FFT). There are many classical fast algorithms which are been deduced by FFT. Its improtance is widely acknowledged and nicely described in numerous papers and monographs, e.g., as follows:" The fast Fourier transfom (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 some properties and design several fastalgorithms, for Toeplitz matrices , Hankel matrices , Pascal matrices and confluent Cauchy-Vandermonde matrices. Moreover, some practical applications of these fast algorithms are given. As theoretical and numerical experiments results show, these fast algorithms is very useful.In chapter 1, we give a brief introduction to the importance and 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 and chapter 3, we derive two fast algorithms for computing discrete sine transformation of Toeplitz matrices and cosine transformation of Hankel matrices, using structure exploitation and FFT. The computational complexity of ous fast algorithms is O(nlogn). Moreover, our algorithms is not only fast but also storage efficient, as it facilitates the computation of selected elements of the transformed matrix without storing any matrix. In chaper, we also present an application of algorithm in eigenvalues computation for symmetric Toeplitz matrices, using Jacobi rotation method. Numerical experiments show that the scan numbers for the transformed are about 1/3 of the scan numbers for the original matrix.In chapter 4, we study the properties of Pascal matrices, and present a fast algorithm for solving linear systems of the Pascal type. The computational complexity of our fast algorithm is O(nlogn), which is more fast than the algorithm in [22]. An application in solving non-homogeneous difference equation with constant coefficients is also discussed.In chapter 5, we analyze the factorization of the inverse of a special type of confluent Cauchy-Vandermonde matrix as a product of block bidiagonal matrices by using block Neville elimination. Factorizations of confluent Cauchy-Vandermonde matrices are also considered, which generalize the results of [52].In chapter 6, we discuss a problem, which has been posed by K. R. Driessel in [19] , that isProblem A: Characterize all n-tuples of real numbers which can serve as n-tuples of eigenvalues of some n x n real Hankel matrix.In this chapter, we give several necessary conditions for Problem A, which extend the partial results of [26].