Cited By
View all- van Gemund A(2005)Compile-time performance prediction of parallel systemsQuantitative Evaluation of Computing and Communication Systems10.1007/BFb0024323(299-313)Online publication date: 9-Jun-2005
Parallel direct solution of large sparse systems in finite element computations
Authors: 
H. X. Lin, H. J. SipsAuthors Info & Claims
Pages 261 - 270
Abstract
An integrated approach for the parallel solution of large sparse systems arisen in finite element computations is presented. The approach includes a three-phase preprocessor and a macro dataflow execution scheme. The three phases of the preprocessor are: (1) Extracting parallelism by means of an automatic domain decomposer; (2) Building the distributed data structure and (partial) scheduling for parallel computation during symbolic factorization; (3) Assigning processes (tasks) onto processors. The proposed approach has been implemented in the finite element analysis software package DIANA. Experimental results show that this integrated approach is an efficient method for both shared-and distributed-memory parallel systems.
References
[1]
R. de Borst, G.M.A. Kusters, P. Nauta and F.C. de Witte, "DIANA - a comprehensive, but flexible finite element system", In Finite Element Systems: A Handbook, Ed. C.A. Brebbia, Springer, Berlin, 1985.
[2]
O. Storaasli, J. Ransom and R. Fulton, "Structural dynamic analysis on a parallel computer: the finite element machine", 25th AIAA/ASME/ASCE/AHS Structures, Structural Dynamics and Materials Conference, Palm Springs, CA. May 14-16, 1984.
[3]
I.S. Duff, "Parallel implementation of multifrontal schemes", Parallel Computing 3, 1986, pp. 193-204.
[4]
C. Farhat and E. Wilson, "A new finite element concurrent computer program architecture", Int'l J. for Num. Meth. in Eng., Vol. 24, 1987, pp. 1771-1792.
[5]
A. George, M.T. Heath, J.W. Liu, and E. Ng, "Sparse Cholesky factorization on a local-memory multiprocessor", SIAM J. Star. Comput. 9, 1988, 327-340.
[6]
J.R. Gilbert and R. Schreiber, "Highly parallel sparse cholesky factorization", SIAM J. Sci. Stat. Comput., Vol. 13, No. 5, 1992, pp. 1151-1172.
[7]
P. Amestoy, M. Dayde and I. Duff, "Use of Level 3 BLAS kernels in the solution of full and sparse linear equations, Report TR 89/9, CERFACS, 1989.
[8]
W. Blume and R. Eigenman, "Performance analysis of parallelizing compilers on the Perfect Benchmarks programs", IEEE Trans. Parallel and Distributed Systems, Vol. 3, no. 6, Nov. 1992.
[9]
M. Berry, et al, "The perfect club benchmarks: Effective performacne evaluation of supercomputers". Int.J.Supercomput. Appl.,vol.3,no.3,pp.5-40, Fall 1989.
[10]
High Performance Fortran Forum, High Performance Fortran Language Specification, Version 1.0, Rice University, Houston, Texas, January 1993.
[11]
H.X. Lin, A Methodology for Parallel Direct Solution of Finite Element Systems, PhD Thesis, Delft University of Technology (to appear).
[12]
A. George, J.W. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, 1981
[13]
M.R. Garey, D.S. Johnson, and L. Stockmeyer, "Some Simplified NP-complete graph problems", Theoret. Comput. Sci., Vol. 1, 1976, pp. 237-267.
[14]
A. George and J.W.H. Liu, "The evolution of the minimum degree ordering algorithm", SIAM Review, Vol. 31, No. 1., 1989, pp. 1-19.
[15]
J.W.H. Liu, "The role of elimination trees in sparse factorization", SIAM J. Matrix Anal. AppI., Vol. 11, no. 1, pp. 134-172, Jan. 1990.
[16]
C.C. Ashcraft, "The domain/segment partition for the factorizafion of sparse symmetric positive definite matrices", Eng. Comp. & Anal. Tech. Report ECA- TR-148, Boeing Comp. Serv., November 1990.
[17]
C. Farhat, "A simple and efficient automatic FEM domain decomposer, Computer & Structures, Vol. 28, No. 5, 1988, pp. 579-602.
[18]
B.W. Kemighan and S. Lin, "An efficient heuristic procedure for partitioning graphs", The Bell system Tech. J. 49, 1970, pp. 291-307.
[19]
N.P. Chrisochoides, E.N. Houstis and C.E. Houstis, "Geometry based mapping strategies for PDE computations", In Proceedings of ACM Supercomputing Conference '91, 1991, pp. 115-127.
[20]
A. Pothen, H.D. Simon and K-P. Liou, "Partitioning sparse matrices with eigenvectors of graphs", SIAM J. Matrix Anal. Appl. Vol. 11, No. 3, 1990, pp. 430- 452.
[21]
D.E. Johnson, C.R. Aragon, L.A. McGoech and C. Schevon, "Optimization by simulated annealing: an experimental evaluation; Part I, Graph partitioning", Operatins Research, Vol. 37, No. 6, 1989, pp. 865- 892.
[22]
J.W. Liu, "A graph matching algorithm by node separators", ACM Trans.Mathematical Software 15, No.3, 1989, 198-219.
[23]
J. Dongarra and I. Duff "A set of Level 3 Basic Linear Algebra Subprograms", ACM Trans. Mathematical Software, No.1, 1990, 1-17.
[24]
A.H. Karp, "Programming for Parallelism," IEEE Computer, May 1987.
[25]
H.X. Lin and H.J. Sips, "A distributed direct-solver for the DIANA finite element system", ESPRIT Genesis-P deliverable, 1991.
Index Terms
- Parallel direct solution of large sparse systems in finite element computations
Recommendations
MPI-based parallel finite element approaches for implicit nonlinear dynamic analysis employing sparse PCG solvers
This paper presents three formulations combining domain decomposition based finite element method with linear preconditioned conjugate gradient (LPCG) technique for solving large-scale problems in structural mechanics on parallel processing machines. In ...
OpenMP based parallel normalized direct methods for sparse finite element linear systems
A new parallel normalized exact inverse algorithm is presented for solving sparse symmetric finite element linear systems on symmetric multiprocessor systems (SMP), based upon an antidiagonal motion approach ("wave"-like pattern) for overcoming the data ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1993 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 1993
Check for updates
Qualifiers
- Article
Conference
ICS93
Sponsor:
Acceptance Rates
Overall Acceptance Rate 629 of 2,180 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 491Total Downloads
- Downloads (Last 12 months)36
- Downloads (Last 6 weeks)5
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View all- van Gemund A(2005)Compile-time performance prediction of parallel systemsQuantitative Evaluation of Computing and Communication Systems10.1007/BFb0024323(299-313)Online publication date: 9-Jun-2005
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in