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

Volume 27 Issue 10

Turn off MathJax

Article Contents

Abstract

References

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.

Relative Articles

[1]	ZHENG Senwei, KOU Jiaqing, ZHANG Weiwei. A Mixed-Precision GMRES Acceleration Algorithm for Large Sparse Matrices in Fluid Dynamics Simulation[J]. Applied Mathematics and Mechanics, 2025, 46(1): 40-54. doi: 10.21656/1000-0887.450167
[2]	CHEN Wei, TANG Zhihong, PENG Linxin. Linear Bending Analysis of Functionally Graded Sandwich Shells With the Meshless Method Based on the Layer-Wise Theory[J]. Applied Mathematics and Mechanics, 2024, 45(5): 539-553. doi: 10.21656/1000-0887.440262
[3]	CHEN Hongling, LI Xiaolin. Analysis of the Finite Point Method for Fractional Cable Equations[J]. Applied Mathematics and Mechanics, 2022, 43(6): 700-706. doi: 10.21656/1000-0887.420183
[4]	ZHANG Yingchun, LI Yin, XIAO Manyu, XIE Gongnan. Some Preconditioning Iterative Algorithms for Non-Hermitian Linear Equations[J]. Applied Mathematics and Mechanics, 2019, 40(3): 237-249. doi: 10.21656/1000-0887.390222
[5]	CHEN Shenshen, ZENG Jiawei. A Reproducing Kernel Interpolation Method for Axisymmetric Elastodynamic Problems[J]. Applied Mathematics and Mechanics, 2019, 40(8): 938-944. doi: 10.21656/1000-0887.390242
[6]	FU Minghui, LI Yongxi. A Preconditioned Precise Integration Method for Solving Ill-Conditioned Linear Equations[J]. Applied Mathematics and Mechanics, 2018, 39(4): 462-469. doi: 10.21656/1000-0887.380206
[7]	SUN Yue, FENG Xiang-chu, XIAO Jun, WANG Ying. MLS-Based Postprocessing Procedure for Discontinuous Deformation Analysis[J]. Applied Mathematics and Mechanics, 2017, 38(7): 743-754. doi: 10.21656/1000-0887.370259
[8]	CHEN Shen-shen, ZHONG Bin. A Meshless Natural Element Method for 2D Viscoelastic Problems[J]. Applied Mathematics and Mechanics, 2017, 38(5): 605-612. doi: 10.21656/1000-0887.370300
[9]	SUN Xin-zhi, LI Xiao-lin. Error Estimates for the Complex Variable Moving Least Square Approximation in Sobolev Spaces[J]. Applied Mathematics and Mechanics, 2016, 37(4): 416-425. doi: 10.3879/j.issn.1000-0887.2016.04.009
[10]	YANG Jian-jun, ZHENG Jian-long. A Meshless Intervention-Point Method With h-p-d Adaptability[J]. Applied Mathematics and Mechanics, 2016, 37(10): 1013-1025. doi: 10.21656/1000-0887.370159
[11]	WANG Yu-xin, LI Xiao-jie, WANG Xiao-hong, YAN Hong-hao, SUN Ming. 3D Simulation of Explosive Detonation With the Material Point Method[J]. Applied Mathematics and Mechanics, 2015, 36(2): 198-206. doi: 10.3879/j.issn.1000-0887.2015.02.009
[12]	WANG Bing-bing, GAO Xin, DUAN Qing-lin. Quadratically Consistent Meshfree Methods for Heat Conduction in Steady State[J]. Applied Mathematics and Mechanics, 2013, 34(7): 750-755. doi: 10.3879/j.issn.1000-0887.2013.07.010
[13]	ZHU Xue-feng, HU Ping, MA Zheng-dong, LIU Wei. Nonconforming Isogeometric Analysis With FETI Method[J]. Applied Mathematics and Mechanics, 2013, 34(8): 771-781. doi: 10.3879/j.issn.1000-0887.2013.08.001
[14]	CHENG Guang-hui, HUANG Ting-zhu, CHENG Xiao-yu. Preconditioned Gauss-Seidel Type Iterative Methods for Solving Linear Systems[J]. Applied Mathematics and Mechanics, 2006, 27(9): 1117-1121.
[15]	MIAO Yu, WANG Yuan-han. Meshless Analysis for Three-Dimensional Elasticity With Singular Hybrid Boundary Node Method[J]. Applied Mathematics and Mechanics, 2006, 27(5): 597-604.
[16]	GU Tong-xiang, CHI Xue-bin, LIU Xing-ping. AINV and BILUM Preconditioning Techniques[J]. Applied Mathematics and Mechanics, 2004, 25(9): 927-934.
[17]	XIE La-bing, JIANG Fu-ru. Computer Computation of the Method of Multiple Scales——Dirichlet Problem for a Class of System of Nonlinear Differential Equations[J]. Applied Mathematics and Mechanics, 2003, 24(11): 1118-1125.
[18]	Gu Tongxiang. Asynchronous Relaxed Iterative Methods for Solving Linear Systems of Equations[J]. Applied Mathematics and Mechanics, 1997, 18(8): 747-751.
[19]	Salman H. Abbas, . The Theoretical Cost of Sequential and Parallel Algorithms for Solving Linear System of Equations[J]. Applied Mathematics and Mechanics, 1996, 17(12): 1077-1083.
[20]	Hu Xi-heng. The Linearization of Certain Class of Nonlinear Simultaneous Equation Set Containing Amplitude and Phase Frequency Characteristics and Application[J]. Applied Mathematics and Mechanics, 1982, 3(4): 519-527.