Cc. Desouza et al., A NEW APPROACH TO MINIMIZING THE FRONTWIDTH IN FINITE-ELEMENT CALCULATIONS, Computer methods in applied mechanics and engineering, 111(3-4), 1994, pp. 323-334
We propose a new approach to determine the element ordering that minim
ises the frontwidth in finite element computations. The optimisation p
roblem is formulated using graph theoretic concepts. We develop a divi
de-and-conquer strategy which defines a series of graph partitioning s
ubproblems. The latter are tackled by means of three different heurist
ics, namely the Kernighan-Lin deterministic technique, and the non-det
erministic Simulated Annealing and Stochastic Evolution algorithms. Re
sults obtained for various 2D and 3D finite element meshes, whether st
ructured or non-structured, reveal the superiority of the proposed app
roach relative to the standard Cuthill-McKee 'greedy' algorithms. Rela
tive 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 tha
t uses the Stochastic Evolution partitioning heuristic. Numerical expe
riments indicate that the two non-deterministic variants of our divide
-and-conquer approach are robust with respect to mesh refinement and v
ary little in solution quality from one run to another.