A study of the factorization fill‐in for a parallel implementation of the finite element method
Authors:
- 30 November 1994
- journal article
- research article
- Published by Wiley in International Journal for Numerical Methods in Engineering
- Vol. 37 (22) , 3809-3823
Abstract
In this paper we investigate the additional storage overhead needed for a parallel implementation of finite element applications. In particular, we compare the storage requirements for the factorization of the sparse matrices that would occur on a parallel processor vs. a uniprocessor. This variation in storage results from the factorization fill‐in. We address the question of whether the storage overhead is so large for parallel implementations that it imposes severe limitations on the problem size in contrast to the problems executed sequentially on a uniprocessor. The storage requirements for the parallel implementation are based upon a new ordering scheme, the combination mesh‐based scheme. This scheme uses a domain decomposition method which attempts to balance the processors' loads and decreases the interprocessor communication. The storage requirements for the sequential implementation is based upon the minimum degree algorithm. The difference between the two storage requirements corresponds to the storage overhead attributed to the parallel scheme.Experiments were conducted on regular and irregular, 2‐D and 3‐D problems. The meshes were decomposed into 2–256 subdomains which can be executed on 2–256 processors, respectively. The total storage requirements or fill‐in for most of the 2‐D problems were less than a factor of two increase over the sequential execution. In contrast, large 3‐D problems had zero increase in storage or fill‐in over the sequential execution; the fill‐in was less for the parallel execution than the sequential execution. Thus, we conclude that the storage overhead attributed to the use of parallel processors will not impose severe constraints on the problem size. Further, for large 3‐D applications, the combination mesh‐based algorithm does better than minimum degree for reducing the fill‐in.Keywords
This publication has 17 references indexed in Scilit:
- An efficient method for representing and transmitting message patterns on multiprocessor interconnection networksJournal of Parallel and Distributed Computing, 1991
- The Evolution of the Minimum Degree Ordering AlgorithmSIAM Review, 1989
- Solving structural mechanics problems on the caltech hypercube machineComputer Methods in Applied Mechanics and Engineering, 1987
- Modification of the minimum-degree algorithm by multiple eliminationACM Transactions on Mathematical Software, 1985
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- A Fast Solver Free of Fill-In for Finite Element ProblemsSIAM Journal on Numerical Analysis, 1982
- Yale sparse matrix package I: The symmetric codesInternational Journal for Numerical Methods in Engineering, 1982
- Computing the Minimum Fill-In is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1981
- Complexity Bounds for Regular Finite Difference and Finite Element GridsSIAM Journal on Numerical Analysis, 1973
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973