A New Approach To Minimizing the Frontwidth in Finite-element Calculations
(1994) Computer Methods in Applied Mechanics and Engineering — Vol. 111, n° 3-4, p. 323-334 (1994)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 836.49 KB
Details
- Authors
- Abstract
- We propose a new approach to determine the element ordering that minimises the frontwidth in finite element computations. The optimisation problem is formulated using graph theoretic concepts. We develop a divide-and-conquer strategy which defines a series of graph partitioning subproblems. The latter are tackled by means of three different heuristics, namely the Kernighan-Lin deterministic technique, and the non-deterministic Simulated Annealing and Stochastic Evolution algorithms. Results obtained for various 2D and 3D finite element meshes, whether structured or non-structured, reveal the superiority of the proposed approach relative to the standard Cuthill-McKee 'greedy' algorithms. Relative improvements in frontwidth are in the range 25-50% in most cases. These figures translate into a significant 2-4 speedup of the finite element solver phase relative to the standard Cuthill-McKee ordering. The best results are obtained with the divide.-and-conquer variant that uses the Stochastic Evolution partitioning heuristic. Numerical experiments indicate that the two non-deterministic variants of our divide-and-conquer approach are robust with respect to mesh refinement and vary little in solution quality from one run to another.
- Affiliations
Citations
De Souza, C., Keunings, R., Wolsey, L., & Zone, O. (1994). A New Approach To Minimizing the Frontwidth in Finite-element Calculations. Computer Methods in Applied Mechanics and Engineering, 111(3-4), 323-334. https://doi.org/10.1016/0045-7825(94)90137-6 (Original work published 1994)