大型稀疏矩阵求解器GSS简介 上海智琢软件科技有限公司 2013. 7. 20

稀疏矩阵求解的广泛应用 矩阵求解是数值计算的核心[1] 稀疏矩阵求解是数值计算的关键之一 稀疏矩阵求解往往是资源瓶颈 一些有趣的应用 偏微分方程，积分方程，特征值，优化… 万阶以上dense matrix不可行 稀疏矩阵求解往往是资源瓶颈 时间瓶颈，内存，外存等瓶颈 一些有趣的应用 GOOGLE PAGE RANK[8]

稀疏矩阵复杂、多变 基本参数 对称性，稀疏性，非零元分布 敏感性，病态矩阵 条件数 格式多变 测试集 Harwell-Boeing Exchange Format 。。。 测试集 Harwell-Boeing Sparse Matrix Collection UF sparse matrix collection

求解器的飞速发展 BBMAT http://www.cise.ufl.edu/research/sparse/matrices/Simon/bbmat.html 38744阶，分解后元素超过四千万. 1988 巨型机cray-2上 >1000秒 2003 4G umfpack4 32.6秒[4] 2006 3.0G GSS1.2 15秒 2012 3.0G 4核 GSS 2.3 4秒 硬件的发展 CPU，内存等 稀疏技术逐渐成熟 multifrontal ,supernodal… 数学库 BLAS，LAPACK www.netlib.org

LU分解稀疏矩阵的优势 保持稀疏性（优于QR分解等） 百万阶的矩阵的LU可在PC上求解。 较高的稳定性（优于迭代法）[5] 列选主元，代价较小(O( ) ) 多种技巧处理病态矩阵 可充分发挥CPU的效率（优于迭代法） flops >50%*CPU主频 算法很复杂

多波前法(multifrontal)简介 发展 Duff and Raid [2] J.W.H.Liu等分析，改进 [3] T.A.Davis开发UMFPACK [4] 基本算法 利用稀疏矩阵的特性，得到一系列密集子阵（波前）。将LU分解转化为对这些波前的装配，消去，更新等操作。 多波前法的优点 波前是dense matrix ,可直接调用高性能库（BLAS等） 密集子阵可以节省下标存储 提高并行性 目前主要的求解器 UMFPACK,WSMP,GSS,HSL MA41等

LU分解形成frontal 10阶矩阵。 蓝点代表非零元。红点表示分解产生的注入元(fill-in) Frontal划分{a}, {b}{c}{d} {e} {f,g}{h,i,j}

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} 消去树

GSS简介 标准C开发，适用于各种平台 比INTEL PARDISO更快，更稳定 平均数值分解时间不到UMFPACK的1/3 突破32位Windows内存限制 支持最多32个CPUP 提供64位版本

GSS的技术特点 支持 AMD，METIS，COLAMD及用户自定义排序 自动分析分块矩阵结构，提取strong hall matrix 支持列选主元，rook pivoting，static pivoting等多种主元策略 支持常见的稀疏矩阵格式，包括ccs,crs, Harwell Boeing format等 支持INTEL Hyper-Threading；支持共享内存的多CPU并行机 32位Windows下，可处理LU规模超过4G的矩阵 提供多种处理病态矩阵手段

对比测试 INTEL PARDISO 9.0 UMFPACK 4.4。 测试集 symmetric set，2-by-2 set，unsymmetric set [4] P43.0G，512K cache。 1G内存

与INTEL PARDISO的对比

与UMFPACK 4.4的对比

GSS的用户 高校，研究所 中国电力科学研究院 香港大学 中国石油大学 电子科技大学 三峡大学 2011年成为Intel软件卓越精英合作伙伴

参考文献 [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. 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. 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. 82--109. [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]宋新立,陈英时等.电力系统全过程动态仿真中大型稀疏线性方程组的分块求解算法

GSS for million unknowns performance stable generality 地址：上海市黄埔区北京东路666号B区906 (200001) 手机：13501997193 网址：www.grusoft.com 邮箱: gsp@grusoft.com QQ: 304718494