塊三對角方程組的可擴展并行算法及其應(yīng)用研究.pdf

1、偏微分方程的數(shù)值求解是科學(xué)與工程計算的重要任務(wù)，塊三對角線性方程組是偏微分方程離散格式的主要形式之一。本文系統(tǒng)地研究了塊三對角線性方程組直接求解方法的可擴展并行算法及其應(yīng)用，主要工作如下： 1．將三對角線性方程組的RCD(Recursive Doubling)方法，推廣到了塊三對角線性方程組，得到BRCD(Block Recursive Doubling)方法。該方法將塊LU分解的時序性較強的計算轉(zhuǎn)化成矩陣的乘積計算，有利于設(shè)計

2、并行算法；同時給出了塊LU分解方法、BRCD方法和SBP(Sequential Block Prefix)方法的反向與雙向計算公式，在計算中使用不同方向的計算公式可以減少計算量；給出了一個數(shù)值穩(wěn)定的塊三對角線性方程組快速BOER(Block Odd-Even Reduction)求解公式，提高了計算精度和速度； 2．對于Larfiba等提出的三對角線性方程組的重疊分割并行方法，一方面將它推廣到了塊三對角線性方程組，該方法對于強塊

3、對角占優(yōu)塊三對角線性方程組的求解有較高的并行效率；另一方面將它與非重疊分割并行方法的縮減方程組結(jié)合，提出了塊三對角線性方程組的有通信重疊分割并行方法，對于弱塊對角占優(yōu)的塊三對角線性方程組，該方法可以用少量通信代替過量的計算，保證了精度和計算效率； 3．對嚴(yán)格塊對角占優(yōu)塊三對角線性方程組的兩類縮減方程組，提出了近似求解方法和相應(yīng)的并行算法，該方法的通信次數(shù)是可調(diào)整的，可以通過它的調(diào)整來控制精度； 4．對嚴(yán)格塊對角占優(yōu)的塊三

4、對角線性方程組提出了多個可擴展的重疊與非重疊分割并行算法(統(tǒng)稱PBDDA算法)，其中基于塊LU分解的算法統(tǒng)稱PBDDA-LU算法、基于BOER的算法統(tǒng)稱PBDDA-OE算法。給出了兩種通信模式，其特點是：僅使用局部通信；通信復(fù)雜度可調(diào)整；每次通信都是具有一定間隔的相鄰處理器之間的單向數(shù)據(jù)傳遞。給出了相對誤差與三個可調(diào)整的指標(biāo)k<,0>(通信復(fù)雜度指標(biāo))、q+?(子問題規(guī)模指標(biāo))和p(處理器數(shù)量即算法并行度指標(biāo))的關(guān)系。PBDDA-LU算

5、法是對PDD方法的推廣，在推廣中使用了反向塊LU分解，改進了回代方法，比直接使用PDD方法求解塊三對角線性方程組減少了將近30％的計算量； 5．提出了一類Topelitz塊三對角線性方程組的PBDDA-OE算法公式；使用這個公式進行高維Poisson方程第一邊值問題的數(shù)值求解；研究了PBDDA-OE算法的性能，提出了保證精度和并行效率的分治策略； 6．利用以上Topelitz塊三對角線性方程組的PBDDA-OE算法公式進