PARPACK并行特征值問(wèn)題求解器簡(jiǎn)介

1、PARPACK：并行特征值問(wèn)題求解器簡(jiǎn)介趙永華 遲學(xué)斌 程強(qiáng) 中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心超級(jí)計(jì)算中心，100080摘要 PARPACK是求解大規(guī)模特征問(wèn)題的軟件包，特別適合于稀疏矩陣特征問(wèn)題。本文扼要介紹了PARPACK的基本概況、主要特性、基本組成。探討了基于PARPACK的特征問(wèn)題求解方法和途徑。最后對(duì)PARPACK的優(yōu)缺點(diǎn)給出了簡(jiǎn)要的總結(jié)。關(guān)鍵字 PARPACK Arnoldi 稀疏矩陣 特征問(wèn)題 1. 概況PARPACK是ARPACK軟件包的并行版本。ARPARK是一個(gè)用來(lái)求解大規(guī)模特征問(wèn)題的軟件包，它本身是一個(gè)Fortran77子程序集合。由于采用基于消息傳遞的并行編程模型，使得P

2、ARPACK軟件包具有較好的可以移植性。通過(guò)PARPACK/ARPACK軟件包，用戶(hù)可解決來(lái)自重大應(yīng)用領(lǐng)域內(nèi)的大規(guī)模對(duì)稱(chēng)、非對(duì)稱(chēng)(包括Hermiton、non-Hermiton)和廣義特征值問(wèn)題。該軟件使用n·O(k)+O(k2)的存儲(chǔ)開(kāi)銷(xiāo)計(jì)算滿(mǎn)足用戶(hù)特定要求的k個(gè)特征值，這包括k個(gè)具有最大實(shí)部、最大虛部或最大模的特征值。PARPACK/ARPACK軟件包是基于隱式重開(kāi)始Arnoldi/Lanczos方法（IRAM：Implicitly Restarted Arnoldi/Lanczos mothed）的實(shí)現(xiàn)。Arnoldi/Lanczos是一個(gè)用來(lái)求解大規(guī)模n×n矩陣幾個(gè)

3、端特征值的重要方法，特別適合于大規(guī)模稀疏或結(jié)構(gòu)矩陣的特征問(wèn)題的求解（這里的結(jié)構(gòu)是指一個(gè)矩陣-向量積wAv的浮點(diǎn)運(yùn)算需求是O（n）而不是O（n2）。 IRLM/IRAM采用了將隱式位移QR策略同一個(gè)k步Arnoldi/Lanczos分解相結(jié)合的策略，從而得到了一個(gè)隱式位移QR迭代的截短形式。通過(guò)隱式重開(kāi)始技術(shù)，克服了標(biāo)準(zhǔn)Arnoldi和Lanczos方法中存在的數(shù)值困難和存儲(chǔ)問(wèn)題。因?yàn)榈偷拇鎯?chǔ)和計(jì)算需求，這個(gè)技術(shù)適合大規(guī)模特征問(wèn)題。2. PARPACK/ARPACK主要特性2.1. 存儲(chǔ)開(kāi)銷(xiāo)低對(duì)大規(guī)模問(wèn)題，存儲(chǔ)需求將成為用戶(hù)使用軟件時(shí)的一個(gè)重要考慮。該軟件包通過(guò)使用隱式重開(kāi)始Lanczos/Ar

4、noldi（Implicit Restarting Lanczos/Arnoldi）方法克服了原始Lanczos/Arnoldi方法太高的存儲(chǔ)需求，求解k個(gè)特征值的存儲(chǔ)開(kāi)銷(xiāo)為2nk+O(k2) 且不要求輔助存儲(chǔ)空間。2.2. 逆向通信接口(Reverse Communication Interface)逆向通信接口為用戶(hù)使用ARPACK/PARPACK 軟件包提供了極大靈活性，這也是該軟件的重要特性。該軟件為不同應(yīng)用類(lèi)型提供了相應(yīng)的逆通信接口子程序。逆通信接口采用循環(huán)結(jié)構(gòu)，它使得矩陣的存儲(chǔ)格式和矩陣-向量乘積的選擇更為靈活，同時(shí)也有利于PARPACK代碼的并行化實(shí)現(xiàn)。2.3. 簡(jiǎn)單易用的驅(qū)動(dòng)程

5、序PARPACK為求解不同類(lèi)型矩陣的特征問(wèn)題提供了相應(yīng)的驅(qū)動(dòng)程序，這些驅(qū)動(dòng)程序可以被用戶(hù)用做模板，通過(guò)適當(dāng)?shù)男薷淖鳛榍蠼饩唧w特征問(wèn)題的程序。2.4. 數(shù)值穩(wěn)定、求解效率和精度高所計(jì)算特征值和特征向量的數(shù)值精度可由用戶(hù)自由指定，且求解精度同隱式位移QR迭代一致，提供了各種譜變換用來(lái)加速收斂速度和求解廣義特征問(wèn)題；充分考慮奇異和病態(tài)問(wèn)題。. PARPACK的組成PARPACK有兩類(lèi)可以被用戶(hù)使用的接口子程序，它們是實(shí)現(xiàn)IRAM的逆通訊接口子程序p*aupd和后處理子程序P*eupd。3.1. 通訊接口子程序?qū)τ诮o定的一般特征問(wèn)題，形式為：Ax=Mx （1）當(dāng)M=I時(shí)，稱(chēng)為標(biāo)準(zhǔn)特征問(wèn)題；MI，稱(chēng)為為

6、廣義特征問(wèn)題。通訊接口子程序p*aupd用來(lái)求解（1）式經(jīng)轉(zhuǎn)換后得到的形如：OP x=x的特征問(wèn)題。P*aupd是問(wèn)題類(lèi)型（symmetric，non-symmetric），數(shù)據(jù)類(lèi)型（real，complex）和精度（single，double）的組合。第一個(gè)*可取s，d，c或z，表示精度和數(shù)據(jù)類(lèi)型；第二個(gè)*可取s或n，表示對(duì)稱(chēng)或非對(duì)稱(chēng)。3.2. 標(biāo)準(zhǔn)特征問(wèn)題求解對(duì)于標(biāo)準(zhǔn)特征問(wèn)題Ax=x，PARPACK提供了兩種求解方式：(1) 標(biāo)準(zhǔn)求解方式 OP=A。(2) 位移逆求解方式 OP=(A-I)-1 3.3. 準(zhǔn)特征問(wèn)題求解 對(duì)于非標(biāo)準(zhǔn)（廣義）特征問(wèn)題Ax=Mx，須首先將此轉(zhuǎn)換為標(biāo)準(zhǔn)特征問(wèn)題，P

7、ARPACK提供了四種轉(zhuǎn)換方式：(1) 標(biāo)準(zhǔn)逆方式 OP=M-1A(2) 位移逆方式 OP=(A-M) -1M(3) Buckling方式 OP=( A-M) 1A (4) Cayley轉(zhuǎn)換方式 OP=( A-M) 1( A+M)其中后兩種方式僅使用于對(duì)稱(chēng)矩陣情況3.2 后處理子程序p*eupd用來(lái)求得由p*aupd得到的特征值的一組正交集。如果使用了（位移）逆求解方式，p*eupd還用來(lái)轉(zhuǎn)換求得Ax=Mx的特征值。每個(gè)通訊接口子程序都有對(duì)應(yīng)的后處理子程序。4. PARPACK編程PARPACK為求解不同模式的矩陣特征問(wèn)題提供了相應(yīng)的驅(qū)動(dòng)程序，這些驅(qū)動(dòng)程序可被用作模板。用戶(hù)通過(guò)適當(dāng)?shù)男薷倪@些模

8、板，可以得到求解具體特征問(wèn)題的程序。這些驅(qū)動(dòng)程序包括：pdsdrv1.f pdndrv1.f pssdrv1.f psndrv1.f psndrv3.f pdndrv3.f。5小結(jié)PARPACK是基于隱式重開(kāi)始Arnoidi方法的特征問(wèn)題求解軟件包。同其它求解特征問(wèn)題的軟件相比，PARAPCK更適合稀疏矩陣和端特征值的求解。由于采用了逆向通信接口，這為用戶(hù)使用ARPACK/PARPACK 軟件包提供了極大靈活性，但同時(shí)對(duì)用戶(hù)編寫(xiě)數(shù)值計(jì)算程序提出了高的要求。PARPACK提供的各種轉(zhuǎn)換方式可以幫助用戶(hù)解決各種類(lèi)型特征問(wèn)題的求解，能滿(mǎn)足絕大用戶(hù)解決來(lái)自重大應(yīng)用領(lǐng)域內(nèi)的大規(guī)模端特征問(wèn)題。致謝 PAR

9、PACK系統(tǒng)測(cè)試和開(kāi)發(fā)工作得到了十五信息化建設(shè)項(xiàng)目“超級(jí)計(jì)算環(huán)境建設(shè)與應(yīng)用”和國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng)目(G1999032805)的資助。參考文獻(xiàn)1. R.B. Lehoucq, J.A. Scott, An Evaluation of Software for Computing Eigenvalues of Sparse Nonsymmetric Matrices, Rice University, January 22, 19962. K.J. Mashhoff, D.C. Scorensen, A Portable Implementation of ARPACK for Distributed Memory Parallel Architectures, Rice University, March 12, 19963. K.J. Mashhoff,  D. C. Scorensen,  P_ARPACK: An Efficient Portable Large Scale Eigenvalues Package for Distributed Memory Parallel Archit