Fast Matrix Computations Based On Rank Structured Matrix

Rank Structured matrices gains more and more interest and importance in the numerical analysis and linear algebra literature. Singular value decomposition is one of the basic problems in numerical linear algebra, which is also a fundamental problem in big data. In this thesis, We propose a new algorithm based on the SVD and rank structured matrices.The thesis consists of three parts:In the first part, we study rank structured matrices and low rank approximation from a theoretical point of view. We introduce some efficient singular value decomposition(SVD)algorithms, which can be briefly summed up to two kind. We analyze the advantage of QR iterative algorithm, divide-and-conquer, Jacobi algorithm in both time and precision. Combined with Linear algebra package(LAPACK), we implement the programmes to compare the speed of the different algorithms.In the second part, we modify a classical downdating SVD algorithm and reduce its complexity significantly. We use a structured low-rank approximation algorithm to compute an hierarchically semiseparable(HSS) matrix approximation to the eigenvector matrix of a diagonal matrix plus rank-one modification. The complexity of our downdating algorithm is analyzed. We further show that the structured low-rank approximation algorithm is backward stable. Numerous experiments have been done to show the efficiency of our algorithm. When the dimension approaches 8000, our algorithm can be 5.4x faster than Intel MKL. Furthermore, the memory needed in our algorithm is much less than Intel MKL.In the third part, we propose a parallel matrix multiplication algorithm for some Cauchylike matrices. We adopt the strategy which is better for paralellism. For some matrices with large dimensions, our algorithm can be much faster than that using plain matrixmatrix multiplications by using Intel MKL in parallel cases.