High Performance Sparse Solver for Unsymmetrical Linear Equations With Out-of-Core Strategies and Its Application on Meshless Methods

YUAN Wei-ran; CHEN Pu; LIU Kai-xin

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2006 > 27(10): 1173-1181

YUAN Wei-ran, CHEN Pu, LIU Kai-xin. High Performance Sparse Solver for Unsymmetrical Linear Equations With Out-of-Core Strategies and Its Application on Meshless Methods[J]. Applied Mathematics and Mechanics, 2006, 27(10): 1173-1181.

Citation:

PDF( 362 KB)

High Performance Sparse Solver for Unsymmetrical Linear Equations With Out-of-Core Strategies and Its Application on Meshless Methods

1.
LTCS & Department of Mechanics and Aerospace Engineering, Peking University, Beijing 100871, P. R. China;

Received Date: 2005-07-25
Rev Recd Date: 2006-04-07
Publish Date: 2006-10-15

Abstract

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.
- sparse matrices,
- linear equations,
- meshless methods,
- high performance computation

FullText(HTML)

References(19)

References

[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.