Premium
An organization of sparse gauss elimination for solving partial differntial equations on distributed memory machines
Author(s) -
Mu Mo,
Rice John R.
Publication year - 1993
Publication title -
numerical methods for partial differential equations
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.901
H-Index - 61
eISSN - 1098-2426
pISSN - 0749-159X
DOI - 10.1002/num.1690090206
Subject(s) - block (permutation group theory) , computer science , exploit , overhead (engineering) , domain decomposition methods , context (archaeology) , multiprocessing , gaussian elimination , domain (mathematical analysis) , distributed memory , computation , partial differential equation , algorithm , data structure , mathematics , parallel computing , shared memory , finite element method , paleontology , mathematical analysis , physics , geometry , computer security , quantum mechanics , biology , gaussian , thermodynamics , programming language , operating system
Abstract A computational arrangement of Gauss elimination is presented for solving sparse, nonsymmetric linear systems arising from partial differential equation problems. It is particularly targeted for use on distributed memory message passing multiprocessor computers and it is presented and analyzed in this context. The objective of the algorithm is to exploit the sparsity (i.e., reducing computation, communication, and memory requirements) and to optimize the data structure manipulation overhead. The algorithm is based on the nested dissection approach, which starts with a large set of very sparse, completely independent subsystems and progresses in stages to a single, nearly dense system at the last stage. The computational efforts of each stage are roughly equal (almost exactly equal for model problems), yet the data structures appropriate for the first and last stages are quite different. Thus we use different types of data structures and algorithm components at different stages of the solution. The new organization is a combination of previous techniques including nested dissection, implicit block factorization, domain decomposition, fan‐in, fan‐out, up‐looking, down‐looking, and dynamic data structures. © 1993 John Wiley & Sons, Inc.