Reordering edges and elements in unstructured meshes to reduce execution time in Finite Element Computations

Gerardo Mario Ortigoza Capetillo, Alberto Pedro Lorandi Medina, Alfonso Cuauhtemoc García Reynoso


Reverse Cuthill McKee (RCM) reordering can be applied to either edges or elements of unstructured meshes (triangular/tetrahedral) , in accordance to the respective finite element formulation,  to reduce the bandwidth of stiffness matrices . Grid generators are mainly designed for nodal based finite elements. Their output is a list of nodes (2d or 3d) and an array describing element connectivity, be it triangles or tetrahedra. However,  for edge-defined finite element formulations a numbering of the edges is required. Observations are reported for Triangle/Tetgen Delaunay grid generators and for the sparse structure of the assembled matrices in both edge- and element-defined formulations. The RCM is a renumbering algorithm traditionally applied to the nodal graph of the mesh. Thus, in order to apply this renumbering to either the edges or the elements of the respective finite element formulation,  graphs of the mesh were generated. Significant bandwidth reduction was obtained. This translates to reduction in the execution effort of the sparse-matrix-times-vector product. Compressed Sparse Row format was adopted and the matrix-times-vector product was implemented in an OpenMp parallel routine.


RCM reordering; finite element; bandwidth reduction of stiffness matrices; edge and element graphs of the mesh

Full Text:



J. P. Bastos and N. Sadowski. Magnetic Materials and 3D Finite Element Modeling. CRC press, 2014.

D. A. Burgess and M. Giles. Renumbering unstructured grids to improve performance of codes on hierarchical memory machines. Advances in Engineering Software, 28(3):189–201, 1997.

P. Castillo. A review of the local discontinuous Galerkin (ldg) method applied to elliptic problems. Journal Applied Numerical Mathematics, Selected papers from the first Chilean workshop on numerical analysis of partial differential equations, 56(10):1307–1313, 2006.

B. F. Cockburn B., Arnold D.N. and D. Marini. Unified analysis of discontinuous galerkin methods for elliptic problems. SIAM Journal of Numerical Analysis, 39(2):1749–1779, 2002.

E. Cuthill and J.McKee. Reducing the bandwidth of sparse symmetric matrices. ACM Annual Conference Proceedings of the 24th national conference, pages 157–172, 1969.

D. K. K. D. E. Keyes, W. C. Groop and B. F. Smith. Performance modeling and tunning of an unstructured mesh cfd application. Conference on High Performance Networking and Computing, Proceedings of the 2000 ACM/IEEE conference on Supercomputing, (34), 2000.

S. G. J. Saltz and D. J.Mavriplis. The design and implementation of a parallel unstructured euler solver using software primitives. AIAAA Journal, 1992.

M. Jian. The Finite Element Method in Electromagnetics. IEEE, John Wiley and sons inc, 2014.

V. H.-H. Nguye-Thoi, Phung-Van P. and L. Le-Anh. An edge-based smoothed finite element method (es-fem) for dynamic analysis of 2d fluid-solid interaction problems. KSCE Journal of Civil Engineering, 3(19):641–650, 2015.

T. P. Noreika A. Electromagnetic Field Modeling Using Edge Finite Elements. International Biennial Baltic Electronics Conference, 2008.

D. M. V. P. J. m. C. Octavio Castillo, Josep de la Puente. A parallel tool for numerical approximation of 3d electromagnetic surveys in geophysics. Computacion y sistemas, 1(20):29–39, 2016.

R. R. C. M. Ordering.

G. Ortigoza. Triangular grid generators for the eigenvalue calculation with edge elements. Revista Mexicana de Fisica, (2):154–160, 2009.

G. Ortigoza. Tetrahedral grid generators for the eigenvalue calculation with edge elements. Revista Computacion y Sistemas IPN, (14):5–16, 2010.

N. G. P. K. Stockmeyer and W. Poole. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM Journal on Numerical Analysis, 13(2):236–250, 1976.

K. Paluszny A. and M. Hohmeyer. Hybrid finite elementfinite volume discretization of complex geologic structures and a new simulation workflow demonstrated on fractured rocks. Geofluids, (7):186–208, 2007.

P.-O. Persson. High-order navier-stokes simulations using a sparse line-based discontinuous galerkin method. 50th AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition. Nashville, Tennessee., 2012.

J. R. Schewchuk. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. Applied computational geometry, 1148:203–222, 1996.

H. Si. Tetgen, a delaunay-based quality tetrahedral mesh generator. Journal ACMTransactions onMathematical Software, 41(2), 2015.

E. S. Um, J. M. Harris, and D. L. Alumbaugh. An iterative finite element time-domain method for simulating threedimensional electromagnetic diffusion in earth. Geophysical Journal International, 190(2):871–886, 2012.

T. R. Zienkiewicz O. C. and J. Zhu. The Finite Element Method Set. Butterworth-Heinemann Elsevier, 2013.



  • There are currently no refbacks.

Copyright (c) 2018

Nova Scientia, year 10, issue 20, May – October 2018, is a biannual journal printed by the Universidad De La Salle Bajío, with its address: Av. Universidad 602, Col. Lomas del Campestre, C. P. 37150, León, Gto. México. Phone: (52) 477 7108500, e-mail: Chief editor: Ph.D. Ramiro Rico Martínez. ISSN 2007 - 0705. Copyright for exclusive use No. 04-2008-092518225500/102, Diffusion rights via computer net 04 - 2008 – 121011584800-203 both granted by the Instituto Nacional del Derecho de Autor.

Editor responsible for updating this issue: Direction of Research Department of the Universidad De La Salle Bajío, last updated on May 25th, 2018.