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

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

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

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

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

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