A parallel algorithm for direct solution of large sparse linear systems, well suitable to domain decomposition methods
DOI:
https://doi.org/10.13052/EJCM.18.589-605Keywords:
two-level parallelism, parallel algorithm, nested dissection, zero-energy modesAbstract
The goal of this paper is to develop a parallel algorithm for the direct solution of large sparse linear systems and integrate it into domain decomposition methods. The computational effort for these linear systems, often encountered in numerical simulation of structural mechanics problems by finite element codes, is very significant in terms of run-time and memory requirements.In this paper, a two-level parallelism is exploited. The exploitation of the lower level of parallelism is based on the development of a parallel direct solver with a nested dissection algorithm and to introduce it into the FETI methods. This direct solver has the advantage of handling zero-energy modes in floating structures automatically and properly. The upper level of parallelism is a coarse-grain parallelism between substructures of FETI. Some numerical tests are carried out to evaluate the performance of the direct solver.
Downloads
References
Bui T. N., Moon B.-R., “ Genetic algorithm and graph partitioning”, IEEE Transactions on
Computers, vol. 45, n° 7, p. 841-855, 1996.
Charrier P., Roman J., “ Algorithmique et calculs de complexité pour un solveur de type dissections
emboîtées”, Numerische Mathematik, vol. 55, p. 463-476, 1989.
Dongarra J. J., Duff I. S., Croz J. D., Hammarling S., “ A set of Level 3 Basic Linear Algebra
Subprograms”, ACM Transactions on Mathematical Software, vol. 16, p. 1-17, 1990.
Farhat C., Pierson K., LesoinneM., “ The second generation FETImethods and their application
to the parallel solution of large-scale linear and geometrically non-linear structural analysis
problems”, Computer Methods in Applied Mechanics and Engineering, vol. 184, n° 2-4,
p. 333-374, 2000.
Farhat C., Roux F.-X., “ Implicit parallel processing in structural mechanics”, Computational
Mechanics Advances, vol. 2, n° 1, p. 1-124, 1994.
George A., “ Nested dissection of a regular finite element mesh”, SIAM Journal on Numerical
Analysis, vol. 10, n° 2, p. 345-363, 1973.
George A., Liu J. W.-H., Computer solution of large sparse positive definite systems, Prentice
Hall, 1981.
Gosselet P., REY C., “ Non-overlapping domain decomposition methods in structural mechanics”,
Archives of Computational Methods in Engineering, vol. 13, n° 4, p. 515-572, 2006.
Karypis G., Kumar V., “ Metis: Unstructured graph partitioning and sparse matrix ordering
system”, http://www-users.cs.umn.edu/ karypis/metis, 1995.
Karypis G., Kumar V., “ A fast and high quality multilevel scheme for partitioning irregular
graph”, SIAM Journal on Scientific Computing, vol. 20, n° 1, p. 359-392, 1999.
Liu J. W.-H., “ The role of elimination trees in sparse factorization”, SIAM Journal of Matrix
Analysis and Applications, vol. 11, n° 1, p. 132-172, 1990.
Raghavan P., “ DSCPACK home page”, http://www.cse.psu.edu/ raghavan/Dscpack, 2001.
TinneyW. F.,Walker J.W., “ Direct solutions of sparse network equations by optimally ordered
triangular factorization”, Proceedings of the IEEE, vol. 55, n° 11, p. 1801-1809, 1967.
