High Performance Sparse Solver for Unsymmetrical Linear Equations With Out-of-Core Strategies and Its Application on Meshless Methods
-
摘要: 针对局部Petrov-Galerkin无网格法(MLPG)等无网格方法的计算所产生的大型非对称稀疏线性方程组,介绍了一种新的直接解法.与一般非对称求解过程不同,该解法从现有的对称正定解法中演变出来,其分解过程在矩阵的上、下三角阵中对称进行.新的矩阵分解算法可以通过修改对称矩阵分解算法的代码来实现,这提供了从对称解法到非对称解法的快捷转换.还针对MLGP法以及有限元法所产生的方程组开发了多块外存算法(multi-blocked out-of-core strategy)来扩大求解规模.测试结果证明该方法大幅度提高了大型非对称稀疏线性方程组的求解速度.Abstract: A new direct method for solving unsymmetrical sparse linear systems(USLS) arising from meshless methods was introduced. Computation of certain meshless methods such as meshless local Petrov-Galerkin (MLPG) method need to solve large USLS. The proposed solution method for unsymmetrical case performs factorization processes symmetrically on the upper and lower portion of matrix, which differs from previous work based on general unsymmetrical process, and attains higher performance. It is shown that the solution algorithm for USLS can be simply derived from the existing approaches for the symmetrical case. The new matrix factorization algorithm in the method can be implemented easily by modifying a standard JKI symmetrical matrix factorization code. Multi-blocked out-of-core strategies were also developed to expand the solution scale. The approach convincingly increases the speed of the solution process, as is demonstrated with the numerical tests.
-
Key words:
- sparse matrices /
- linear equations /
- meshless methods /
- high performance computation
-
[1] CHEN Pu,Runesha H,Nguyen D T,et al. Sparse algorithms for indefinite systems of linear equations[J].Comput Mech J,2000,25(1):33—42. doi: 10.1007/s004660050013 [2] Damhaug A C,Reid J,Bergseth A.The impact of an efficient linear solver on finite element analysis[J].Comput Struct,1999,72(4/5):594—604. [3] Weinberg D J.A performance assessment of NE/Nastran's new sparse direct and iterative solvers[J].Adv Engng Software,2000,31(8/9):547—554. doi: 10.1016/S0965-9978(00)00016-8 [4] Wilson E L,Bathe K J,Doherty W P.Direct solution of large system of linear equations[J].Comput Struct,1974,4(2):363—372. doi: 10.1016/0045-7949(74)90063-7 [5] Atluri S N,Zhu T.A new meshless local Petrov-Galerkin (MLPG) approach in computational mechanics[J].Comput Mech,1998,22(2):117—127. doi: 10.1007/s004660050346 [6] Atluri S N,Zhu T.The meshless local Petrov-Galerkin (MLPG) approach for solving problems in elasto-statics[J].Comput Mech,2000,25(2/3):169—179. doi: 10.1007/s004660050467 [7] Ng E G,Peyton B W.Block sparse Cholesky algorithm on advanced uniprocessor computers[J].SIAM J Sci Comput,1993,14(5):1034—1055. doi: 10.1137/0914063 [8] Pissanetzky S.Sparse Matrix Technology[M].London,Orlando:Academic Press,1984. [9] Demmel W J,Eisenstat C S,Gilbert J R,et al.A supernodal approach to sparse partial pivoting[J].SIAM J Matrix Anal Appl,1999,20(3):720—755. doi: 10.1137/S0895479895291765 [10] Li S X.An overview of superLU:algorithms,implementation, and user interface[J].ACM Trans Math Software,2005,31(3):302—325. doi: 10.1145/1089014.1089017 [11] Runesha H B,Nguyen D T.Vector-sparse solver for unsymmetrical matrices[J].Adv Engng Software,2000,31(8/9):563—569. doi: 10.1016/S0965-9978(00)00024-7 [12] Sherman A H.On the efficient solution of sparse systems of linear and nonlinear equations[D].Rept No.46.Ph D Dissertation.New York:Dept of Computer Science, Yale University, 1975. [13] CHEN Pu,ZHENG Dong,SUN Shu-li,et al. High performance sparse static solver in finite element analyses with loop-unrolling[J].Adv Engng Software,2003,34(4):203—215. doi: 10.1016/S0965-9978(02)00128-X [14] Fellipa C A. Solution of linear equations with skyline-stored symmetric matrix[J].Comput Struct,1975,5(1):13—29. doi: 10.1016/0045-7949(75)90016-4 [15] Wilson E L,Dovey H H.Solution or reduction of equilibrium equations for large complex structural system[J].Adv Engng Software,1978,1(1):19—26. doi: 10.1016/0141-1195(78)90018-9 [16] Amestoy R P,Enseeiht-Irit,Davis A T,et al.Algorithm 837 : AMD, an approximate minimum degree ordering algorithm[J].ACM Trans Math Software,2004,30(3):381—388. doi: 10.1145/1024074.1024081 [17] Karypis G, Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM J Sci Comput,1998,20(1):359—392. doi: 10.1137/S1064827595287997 [18] Zheng D,Chang T Y P.Parallel Cholesky method on MIMD with shared memory[J].Comput Struct,1995,56(1):25—38. doi: 10.1016/0045-7949(94)00534-A [19] Dowd K,Severance C R.High Performance Computing[M].2nd ed.Cambridge: Sebastopol, CA O’Reilly & Associates,1998.
点击查看大图
计量
- 文章访问数: 2470
- HTML全文浏览量: 47
- PDF下载量: 772
- 被引次数: 0