Fast Algorithms Of HSS Matrix And Their Application In Spherical Harmonic Expansions

Numerical linear algebra of large-scale dense matrix is one of the core problems in science and engineering computation.The problems are derived from many real appli-cations,such as kernel density estimation of machine learning,discretization of integral operator in elliptic boundary value problem,spectral mode of numerical weather forecast.By constructing approximate matrix decomposition or approximate basis of the low-rank sub-blocks in the dense matrix,we can effectively reduces the storage and computational complexity of matrix operations.Hierarchical matrices are a subclass of sparse matrices which can be used to approximate some dense matrices.According to the admissibility criterion of matrix partition and the discrete data structure,hierarchical matrices can be di-vided into five subclasses:H-matrix,H~2-matrix,HODLR-matrix,HSS matrix and FMM matrix.At present,hierarchical matrices have been used for solving linear equations,singular value and eigenvalue problems.In this paper,we mainly study the basic theory and fast algorithms of hierarchically semiseparable matrix,we also design an accelerated algorithm for spherical harominc expansions.Numerical experiments show that our al-gorithms have high efficiency and good stability.The main contents of this paper can be divided into three parts:1.Three kinds of matrix factorization are studied,they are rank-revealing QR decom-position,interpolative decomposition and singular value decomposition.The probabilistic algorithms for construting approximate matrix decompositions are also included.2.We make a detailed study of the divide-and-conquer algorithm for constructing the eigen-decomposition of symmetric tridiagonal matrix.How to make use of the HSS matrix to accelerate the divide-and-conquer algorithm is also described.Moreover,the random-ized algorithm of constructing HSS matrix and the fast multiplication of HSS matrix are also introduced in detail.3.The fast algorithm of spherical harmonic expansions proposed by Mark Tygert is introduced in detail,and we use the improved tridiagonal divide-and-conquer algorithm based on HSS matrix to accelerate the associated Legendre transform.The experimen-tal results show that:The weight of the eigen-decomposition of symmetric tridiagonal matrices in the associated Legendre transform is very large,so the associated Legendre transform can be accelerated significantly by HSSDC.When the truncation volumn is?=18432 and the size of the matrix is n=18432,the improved algorithm for associated legendre transform can achieve 4.21 times speedup and has good numerical stability.