论文部分内容阅读
在最近几年,基于秩结构矩阵的数值稳定的快速算法受到大家的广泛关注。秩结构矩阵包括半可分,拟可分,SSS,HSS,H和H2矩阵等,它们已被用于求解Toeplitz、Cauchy等线性方程组,多项式的根,积分方程,奇异值和特征值等问题。最近的研究表明秩结构矩阵还可用于设计大规模稀疏线性解法器。概括地讲,本文提出了三类快速算法,可分别用于计算(稠密)秩结构矩阵的分解,求解奇异值、特征值问题以及非线性方程求根等。本文将着重介绍与HSS矩阵相关的理论和算法,并用大量的数值算例来说明算法的高效性。本文的基本内容可大致地分为三部分。第一部分(第2–3章)提出了两种快速稳健的HSS矩阵分解算法:正定HSS矩阵的Cholesky分解和通常HSS矩阵的LU分解。与先前的算法相比,本文算法采用了一种新的逼近策略使得每步的分解不需要显式地计算Schur补,从而具有更好的数据局部性和需要更少的计算量。对于HSS LU分解算法,本文还专门提出一种压缩策略来应对某些主对角块病态的情形。为了进一步提高速度,本文采用新近提出的随机SVD算法来计算矩阵的低秩逼近,结果表明随机SVD算法具有计算快速且以极高的概率数值稳定等优点。HSS矩阵的Cholesky分解和LU分解可用作求解积分方程,PDE以及大规模的稀疏线性方程的直接法或者预处理子,并且分别用大量的数值算例说明了算法的高效性。第二部分(第4–6章)提出了一些改进的求解特征值问题的快速算法,例如SVD修正算法,求解奇异值和特征值的分而治之(DC)算法。这些算法的核心思想是利用经典算法中出现的Cauchy类矩阵的低秩结构。如果用HSS矩阵来逼近这些Cauchy类矩阵并且用HSS矩阵乘法来计算特征向量或奇异向量,则可极大地减少计算量。本文还提出一种针对Cauchy类矩阵的HSS构造算法,该算法只需要O(N)的内存(其中N为矩阵的维数),从而可以处理更大规模的矩阵。为了评估本文算法,我们将其与Intel MKL中的相应算法进行比较,结果表明对于某些大规模的矩阵,本文算法可比MKL中的算法快3倍以上且几乎不损失精度。第三部分(第7–9章)提出一种改进的dqds算法和几种求解非线性方程根的高阶牛顿法。特征(奇异)值问题与多项式的求根密切相关,这也是我们研究求根算法的主要原因。本文的dqds算法主要有两类改进:提出一种“全新的”紧缩算法(命名为d-deflation策略)改进了dqds算法对于乱序的矩阵的收敛性;提出一些新的位移策略改进了对于通常双对角矩阵的收敛性。与LAPACK-3.4.0或以前版本中的DLASQ代码相比,在通常情况下,本文改进的dqds算法(V5)可比其快1.2-4.0倍;而对于乱序的双对角矩阵,V5可快3.0-10.0倍。本文提出的d-deflation策略已被LAPACK-3.4.1采用。将V5与“冒进”紧缩策略相结合,本文提出一种混合dqds算法,简记为HDLASQ,其可比LAPACK-3.4.0中的代码快70多倍(对于某些特殊矩阵)。第8章讨论了几种求解非线性方程的高阶牛顿迭代算法,并指出秩结构矩阵算法可与其相结合。与经典的二阶收敛的牛顿法相比,本文算法具有三阶或四阶的收敛速度,并分别给出了收敛阶的证明。第9章对全文的创新点进行了总结,并对未来的工作进行了展望。