论文部分内容阅读
大规模稠密矩阵的数值线性代数是科学与工程计算的核心问题之一,此类问题广泛来源于机器学习的核密度估计、椭圆型边界值问题的边界元方法、数值天气预报的谱模式等诸多应用领域。通过近似分解或构造逼近基等方法对稠密矩阵中的低秩子块进行压缩,可有效地降低存储开销以及矩阵运算的计算复杂度。分层矩阵(Hierarchicalmatrices)可作为某些稠密矩阵的稀疏近似表示,根据矩阵划分方式和数据结构的差异,其可分为H-矩阵、H2-矩阵、HODLR矩阵、HSS矩阵和FMM矩阵这五个子类。目前,分层矩阵已被用于求解线性方程组、奇异值与特征值等问题。本文主要研究了HSS矩阵的基本理论与快速算法,以此出发改进了球谐展开的快速算法,并通过数值实验说明了算法的高效性与数值稳定性。本文的内容主要分为三部分: 一、以秩揭示QR分解、插值分解以及奇异值分解为主要对象,介绍了低秩矩阵构造近似分解的基本方法。本文还介绍了当前研究热点之一的随机低秩逼近算法。 二、详细地介绍了求解对称三对角矩阵特征分解的分而治之(Divide-and-Conquer)算法,以及用HSS矩阵改进后的HSSDC算法。本文还详细地介绍了构造HSS矩阵的随机算法以及HSS矩阵的快速乘法。 三、研究了MarkTygert提出的球谐展开的快速算法,并用HSSDC算法去加速连带勒让德变换。实验结果表明:对称三对角矩阵的特征分解在连带勒让德变换中的计算量比重很大,引入HSSDC算法能显著地加速连带勒让德变换。当截断波数?=18432且矩阵的规模n=18432时,连带勒让德变换的改进算法能达到4.21倍加速比,且算法的数值稳定性很好。