基于結(jié)構(gòu)矩陣的快速算法及其應用.pdf

1、在最近幾年，基于秩結(jié)構(gòu)矩陣的數(shù)值穩(wěn)定的快速算法受到大家的廣泛關(guān)注。秩結(jié)構(gòu)矩陣包括半可分，擬可分，SSS，HSS，H和H2矩陣等，它們已被用于求解Toeplitz、Cauchy等線性方程組，多項式的根，積分方程，奇異值和特征值等問題。最近的研究表明秩結(jié)構(gòu)矩陣還可用于設計大規(guī)模稀疏線性解法器。概括地講，本文提出了三類快速算法，可分別用于計算（稠密）秩結(jié)構(gòu)矩陣的分解，求解奇異值、特征值問題以及非線性方程求根等。本文將著重介紹與HSS矩陣相關(guān)的

2、理論和算法，并用大量的數(shù)值算例來說明算法的高效性。本文的基本內(nèi)容可大致地分為三部分。
　　第一部分(第2–3章)提出了兩種快速穩(wěn)健的HSS矩陣分解算法：正定HSS矩陣的Cholesky分解和通常HSS矩陣的LU分解。與先前的算法相比，本文算法采用了一種新的逼近策略使得每步的分解不需要顯式地計算Schur補，從而具有更好的數(shù)據(jù)局部性和需要更少的計算量。對于HSS LU分解算法，本文還專門提出一種壓縮策略來應對某些主對角塊病態(tài)的情形。

3、為了進一步提高速度，本文采用新近提出的隨機SVD算法來計算矩陣的低秩逼近，結(jié)果表明隨機SVD算法具有計算快速且以極高的概率數(shù)值穩(wěn)定等優(yōu)點。HSS矩陣的Cholesky分解和LU分解可用作求解積分方程，PDE以及大規(guī)模的稀疏線性方程的直接法或者預處理子，并且分別用大量的數(shù)值算例說明了算法的高效性。
　　第二部分(第4–6章)提出了一些改進的求解特征值問題的快速算法，例如SVD修正算法，求解奇異值和特征值的分而治之(DC)算法。這些算

4、法的核心思想是利用經(jīng)典算法中出現(xiàn)的Cauchy類矩陣的低秩結(jié)構(gòu)。如果用HSS矩陣來逼近這些Cauchy類矩陣并且用HSS矩陣乘法來計算特征向量或奇異向量，則可極大地減少計算量。本文還提出一種針對Cauchy類矩陣的HSS構(gòu)造算法，該算法只需要O(N)的內(nèi)存(其中N為矩陣的維數(shù))，從而可以處理更大規(guī)模的矩陣。為了評估本文算法，我們將其與Intel MKL中的相應算法進行比較，結(jié)果表明對于某些大規(guī)模的矩陣，本文算法可比MKL中的算法快3倍以

5、上且?guī)缀醪粨p失精度。
　　第三部分(第7–9章)提出一種改進的dqds算法和幾種求解非線性方程根的高階牛頓法。特征(奇異)值問題與多項式的求根密切相關(guān)，這也是我們研究求根算法的主要原因。本文的dqds算法主要有兩類改進：提出一種“全新的”緊縮算法(命名為d-deflation策略)改進了dqds算法對于亂序的矩陣的收斂性；提出一些新的位移策略改進了對于通常雙對角矩陣的收斂性。與LAPACK-3.4.0或以前版本中的DLASQ代碼相

6、比，在通常情況下，本文改進的dqds算法(V5)可比其快1.2-4.0倍；而對于亂序的雙對角矩陣，V5可快3.0-10.0倍。本文提出的d-deflation策略已被LAPACK-3.4.1采用。將V5與“冒進”緊縮策略相結(jié)合，本文提出一種混合dqds算法，簡記為HDLASQ，其可比LAPACK-3.4.0中的代碼快70多倍（對于某些特殊矩陣）。第8章討論了幾種求解非線性方程的高階牛頓迭代算法，并指出秩結(jié)構(gòu)矩陣算法可與其相結(jié)合。與經(jīng)典的