Download presentation
Presentation is loading. Please wait.
1
大型稀疏矩阵求解器GSS简介 上海智琢软件科技有限公司
2
稀疏矩阵求解的广泛应用 矩阵求解是数值计算的核心[1] 稀疏矩阵求解是数值计算的关键之一 稀疏矩阵求解往往是资源瓶颈 一些有趣的应用
偏微分方程，积分方程，特征值，优化… 万阶以上dense matrix不可行 稀疏矩阵求解往往是资源瓶颈 时间瓶颈，内存，外存等瓶颈 一些有趣的应用 GOOGLE PAGE RANK[8]
![稀疏矩阵求解的广泛应用 矩阵求解是数值计算的核心[1] 稀疏矩阵求解是数值计算的关键之一 稀疏矩阵求解往往是资源瓶颈 一些有趣的应用](http://slidesplayer.com/slide/11763197/65/images/2/%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5%E6%B1%82%E8%A7%A3%E7%9A%84%E5%B9%BF%E6%B3%9B%E5%BA%94%E7%94%A8+%E7%9F%A9%E9%98%B5%E6%B1%82%E8%A7%A3%E6%98%AF%E6%95%B0%E5%80%BC%E8%AE%A1%E7%AE%97%E7%9A%84%E6%A0%B8%E5%BF%83%5B1%5D+%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5%E6%B1%82%E8%A7%A3%E6%98%AF%E6%95%B0%E5%80%BC%E8%AE%A1%E7%AE%97%E7%9A%84%E5%85%B3%E9%94%AE%E4%B9%8B%E4%B8%80+%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5%E6%B1%82%E8%A7%A3%E5%BE%80%E5%BE%80%E6%98%AF%E8%B5%84%E6%BA%90%E7%93%B6%E9%A2%88+%E4%B8%80%E4%BA%9B%E6%9C%89%E8%B6%A3%E7%9A%84%E5%BA%94%E7%94%A8.jpg "偏微分方程，积分方程，特征值，优化… 万阶以上dense matrix不可行. 稀疏矩阵求解往往是资源瓶颈. 时间瓶颈，内存，外存等瓶颈. 一些有趣的应用. GOOGLE PAGE RANK[8]")
3
稀疏矩阵复杂、多变 基本参数 对称性，稀疏性，非零元分布 敏感性，病态矩阵 条件数 格式多变 测试集
Harwell-Boeing Exchange Format 。。。 测试集 Harwell-Boeing Sparse Matrix Collection UF sparse matrix collection
4
求解器的飞速发展 BBMAT 38744阶，分解后元素超过四千万. 巨型机cray-2上 >1000秒 G umfpack4 32.6秒[4] G GSS 秒 G 4核 GSS 秒 硬件的发展 CPU，内存等 稀疏技术逐渐成熟 multifrontal ,supernodal… 数学库 BLAS，LAPACK
5
LU分解稀疏矩阵的优势 保持稀疏性（优于QR分解等） 百万阶的矩阵的LU可在PC上求解。 较高的稳定性（优于迭代法）[5]
列选主元，代价较小(O( ) ) 多种技巧处理病态矩阵 可充分发挥CPU的效率（优于迭代法） flops >50%*CPU主频 算法很复杂
![LU分解稀疏矩阵的优势 保持稀疏性（优于QR分解等） 百万阶的矩阵的LU可在PC上求解。 较高的稳定性（优于迭代法）[5]](http://slidesplayer.com/slide/11763197/65/images/5/LU%E5%88%86%E8%A7%A3%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5%E7%9A%84%E4%BC%98%E5%8A%BF+%E4%BF%9D%E6%8C%81%E7%A8%80%E7%96%8F%E6%80%A7%EF%BC%88%E4%BC%98%E4%BA%8EQR%E5%88%86%E8%A7%A3%E7%AD%89%EF%BC%89+%E7%99%BE%E4%B8%87%E9%98%B6%E7%9A%84%E7%9F%A9%E9%98%B5%E7%9A%84LU%E5%8F%AF%E5%9C%A8PC%E4%B8%8A%E6%B1%82%E8%A7%A3%E3%80%82+%E8%BE%83%E9%AB%98%E7%9A%84%E7%A8%B3%E5%AE%9A%E6%80%A7%EF%BC%88%E4%BC%98%E4%BA%8E%E8%BF%AD%E4%BB%A3%E6%B3%95%EF%BC%89%5B5%5D.jpg "列选主元，代价较小(O( ) ) 多种技巧处理病态矩阵. 可充分发挥CPU的效率（优于迭代法） flops >50%*CPU主频. 算法很复杂.")
6
多波前法(multifrontal)简介
发展 Duff and Raid [2] J.W.H.Liu等分析，改进 [3] T.A.Davis开发UMFPACK [4] 基本算法 利用稀疏矩阵的特性，得到一系列密集子阵（波前）。将LU分解转化为对这些波前的装配，消去，更新等操作。 多波前法的优点 波前是dense matrix ,可直接调用高性能库（BLAS等） 密集子阵可以节省下标存储 提高并行性 目前主要的求解器 UMFPACK,WSMP,GSS,HSL MA41等
7
LU分解形成frontal 10阶矩阵。 蓝点代表非零元。红点表示分解产生的注入元(fill-in)
Frontal划分{a}, {b}{c}{d} {e} {f,g}{h,i,j}
8
Frontal的装配，消去，更新过程 {a} {c} {b} {f,g} {e} {d} {h,i,j} 消去树 a c h c · ·
c,g,h g · · h · · b e j e · · j · · {c} {b} d,i,j i · · j · · f,g,h g g · h · · e,i,j i · · j · · {f,g} {e} {d} h,i, j i i · j · j {h,i,j} 消去树
9
GSS简介 标准C开发，适用于各种平台 比INTEL PARDISO更快，更稳定 平均数值分解时间不到UMFPACK的1/3
突破32位Windows内存限制 支持最多32个CPUP 提供64位版本
10
GSS的技术特点 支持 AMD，METIS，COLAMD及用户自定义排序 自动分析分块矩阵结构，提取strong hall matrix
支持列选主元，rook pivoting，static pivoting等多种主元策略 支持常见的稀疏矩阵格式，包括ccs,crs, Harwell Boeing format等 支持INTEL Hyper-Threading；支持共享内存的多CPU并行机 32位Windows下，可处理LU规模超过4G的矩阵 提供多种处理病态矩阵手段
11
对比测试 INTEL PARDISO 9.0 UMFPACK 4.4。 测试集
symmetric set，2-by-2 set，unsymmetric set [4] P43.0G，512K cache。 1G内存
12
与INTEL PARDISO的对比
13
与UMFPACK 4.4的对比
14
GSS的用户 高校，研究所 中国电力科学研究院 香港大学 中国石油大学 电子科技大学 三峡大学 2011年成为Intel软件卓越精英合作伙伴
15
参考文献 [1] Numerical Analysis. Rainer Kress. Springer-Verlag. 1991
[2] I.S.Duff, A.M.Erisman, and J.K.Reid. Direct Methods for Sparse Matrices London:Oxford Univ. Press,1986. [3] J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp [4] T.A.Davis. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Trans. Math. Software, vol 30, no. 2, pp , 2004. [5] N.J.Higham. Accuracy and Stability of Numerical Algorithms. SIAM,2002 [6] G..H.Golob, C.F.Van loan. Matrix Computations. The Johns Hopkins University Press. 1996 [7] J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp [8] Fast PageRank Computation via a Sparse Linear System (Extended Abstract) Gianna M. Del Corso,Antonio Gullí, Francesco Romani. [9] Y.Saad, Iterative Methods for Sparse Linear Systems, PWS, Boston,1996 [10] Y.S. Chen* ,Simon Li. Application of Multifrontal Method for Doubly-Bordered Sparse Matrix in Laser Diode Simulator. NUSOD,2004 [11] 陈英时 吴文勇等. 采用多波前法求解大型结构方程组.建筑结构,2007年09期 [12]宋新立,陈英时等.电力系统全过程动态仿真中大型稀疏线性方程组的分块求解算法
![参考文献 [1] Numerical Analysis. Rainer Kress. Springer-Verlag. 1991](http://slidesplayer.com/slide/11763197/65/images/15/%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE+%5B1%5D+Numerical+Analysis.+Rainer+Kress.+Springer-Verlag.+1991.jpg "[2] I.S.Duff, A.M.Erisman, and J.K.Reid. Direct Methods for Sparse Matrices. London:Oxford Univ. Press,1986. [3] J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp [4] T.A.Davis. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Trans. Math. Software, vol 30, no. 2, pp , [5] N.J.Higham. Accuracy and Stability of Numerical Algorithms. SIAM,2002. [6] G..H.Golob, C.F.Van loan. Matrix Computations. The Johns Hopkins University Press [7] J.W.H.Liu. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), pp [8] Fast PageRank Computation via a Sparse Linear System (Extended Abstract) Gianna M. Del Corso,Antonio Gullí, Francesco Romani. [9] Y.Saad, Iterative Methods for Sparse Linear Systems, PWS, Boston,1996. [10] Y.S. Chen* ,Simon Li. Application of Multifrontal Method for Doubly-Bordered Sparse Matrix in Laser Diode Simulator. NUSOD,2004. [11] 陈英时 吴文勇等. 采用多波前法求解大型结构方程组.建筑结构,2007年09期. [12]宋新立,陈英时等.电力系统全过程动态仿真中大型稀疏线性方程组的分块求解算法.")
16
GSS for million unknowns
performance stable generality 地址：上海市黄埔区北京东路666号B区906 (200001) 手机： 网址： 邮箱: QQ:
Similar presentations
![第九章 常微分方程数值解法 §1 、引言. 微分方程的数值解：设方程问题的解 y(x) 的存在区间是 [a,b] ，令 a= x 0 < x 1](/40/11046233/big_thumb.jpg "第九章 常微分方程数值解法 §1 、引言. 微分方程的数值解：设方程问题的解 y(x) 的存在区间是 [a,b] ，令 a= x 0 < x 1 >")
