大型稀疏矩陣求解器GSS簡介PPT課件

1、2013. 7. 20大型稀疏矩陣求解器大型稀疏矩陣求解器GSS簡介簡介上海智琢軟件科技有限公司稀疏矩陣求解的廣泛應(yīng)用 矩陣求解是數(shù)值計算的核心1 稀疏矩陣求解是數(shù)值計算的關(guān)鍵之一偏微分方程，積分方程，特征值，優(yōu)化萬階以上dense matrix不可行 稀疏矩陣求解往往是資源瓶頸時間瓶頸，內(nèi)存，外存等瓶頸 一些有趣的應(yīng)用GOOGLE PAGE RANK8稀疏矩陣復(fù)雜、多變 基本參數(shù)對稱性，稀疏性，非零元分布 敏感性，病態(tài)矩陣條件數(shù) 格式多變Harwell-Boeing Exchange Format 。 測試集Harwell-Boeing Sparse Matrix CollectionUF

2、sparse matrix collection1)(AAA求解器的飛速發(fā)展 BBMAT/research/sparse/matrices/Simon/bbmat.html38744階，分解后元素超過四千萬.1988 巨型機cray-2上1000秒2003 4G umfpack432.6秒42006 3.0G GSS1.215秒20123.0G 4核GSS 2.34秒 硬件的發(fā)展CPU，內(nèi)存等 稀疏技術(shù)逐漸成熟multifrontal ,supernodal 數(shù)學庫BLAS，LAPACKLU分解稀疏矩陣的優(yōu)勢 保持稀疏性（優(yōu)于QR分解等

3、）百萬階的矩陣的LU可在PC上求解。 較高的穩(wěn)定性（優(yōu)于迭代法）5列選主元，代價較小(O( ) )多種技巧處理病態(tài)矩陣 可充分發(fā)揮CPU的效率（優(yōu)于迭代法）flops 50%*CPU主頻 算法很復(fù)雜2n多波前法(multifrontal)簡介 發(fā)展Duff and Raid 2 J.W.H.Liu等分析，改進 3 T.A.Davis開發(fā)UMFPACK 4 基本算法利用稀疏矩陣的特性，得到一系列密集子陣（波前）。將LU分解轉(zhuǎn)化為對這些波前的裝配，消去，更新等操作。 多波前法的優(yōu)點波前是dense matrix ,可直接調(diào)用高性能庫（BLAS等）密集子陣可以節(jié)省下標存儲提高并行性 目前主要的求解器

4、UMFPACK,WSMP,GSS,HSL MA41等LU分解形成frontal10階矩陣。藍點代表非零元。紅點表示分解產(chǎn)生的注入元(fill-in)Frontal劃分a, bcd e f,gh,i,jFrontal的裝配，消去，更新過程a c hc h cf,gbeh,i,jac,g,hg h b e je j f,g,hg g h e,i,ji j h,i, ji i j jdd,i,ji j 消去樹GSS簡介 標準C開發(fā)，適用于各種平臺 比INTEL PARDISO更快，更穩(wěn)定 平均數(shù)值分解時間不到UMFPACK的1/3 突破32位Windows內(nèi)存限制 支持最多32個CPUP 提供64位

5、版本GSS的技術(shù)特點技術(shù)特點 支持 AMD，METIS，COLAMD及用戶自定義排序 自動分析分塊矩陣結(jié)構(gòu)，提取strong hall matrix 支持列選主元，rook pivoting，static pivoting等多種主元策略 支持常見的稀疏矩陣格式，包括ccs,crs, Harwell Boeing format等 支持INTEL Hyper-Threading；支持共享內(nèi)存的多CPU并行機 32位Windows下，可處理LU規(guī)模超過4G的矩陣 提供多種處理病態(tài)矩陣手段對比測試 INTEL PARDISO 9.0 UMFPACK 4.4。 測試集symmetric set，2-by

6、-2 set，unsymmetric set 4 P43.0G，512K cache。 1G內(nèi)存 與INTEL PARDISO的對比與UMFPACK 4.4的對比GSS的用戶高校，研究所中國電力科學研究院香港大學中國石油大學電子科技大學三峽大學2011年成為Intel軟件卓越精英合作伙伴參考文獻1 Numerical Analysis. Rainer Kress. Springer-Verlag. 19912 I.S.Duff, A.M.Erisman, and J.K.Reid. Direct Methods for Sparse Matrices. London:Oxford Univ.

7、Press,1986.3 J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp. 82-109.4 T.A.Davis. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Trans. Math. Software, vol 30, no. 2, pp. 165-195, 2004. 5 N.J.Higham. Ac

8、curacy and Stability of Numerical Algorithms. SIAM,20026 G.H.Golob, C.F.Van loan. Matrix Computations. The Johns Hopkins University Press. 19967 J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp. 82-109.8 Fast PageRank Computation via a Spar

9、se Linear System (Extended Abstract) Gianna M. Del Corso,Antonio Gull, Francesco Romani.9 Y.Saad, Iterative Methods for Sparse Linear Systems, PWS, Boston,199610 Y.S. Chen* ,Simon Li. Application of Multifrontal Method for Doubly-Bordered Sparse Matrix in Laser Diode Simulator. NUSOD,200411 陳英時 吳文勇等. 采用多波前法求解大型結(jié)構(gòu)方程組.建筑結(jié)構(gòu),2007年09期12宋新立,陳英時等.電力系