A New Approach to Minimising the Frontwidth in Finite Element Calculations

Cc. de Souza, R. Keunings, Laurence Wolsey () and O. Zone
Additional contact information
Cc. de Souza: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
R. Keunings: Division of Applied Machanics, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Laurence Wolsey: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
O. Zone: Division of Applied Machanics, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1992055, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Date: 1992-12-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1992.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1992055

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().