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



Document title: Reordering edges and elements in unstructured meshes to reduce execution time in Finite Element Computations
Journal: Nova scientia
Database: PERIÓDICA
System number: 000430329
ISSN: 2007-0705
Authors: 1
2
2
Institutions: 1Universidad Veracruzana, Facultad de Ingeniería, Boca del Río, Veracruz. México
2Universidad Veracruzana, Instituto de Ingeniería, Boca del Río, Veracruz. México
Year:
Season: Oct
Volumen: 10
Number: 20
Country: México
Language: Inglés
Document type: Artículo
Approach: Aplicado, descriptivo
Spanish abstract En este trabajo mostramos cómo el reordenamiento RCM puede aplicarse a los lados y a los elementos de una malla no estructurada (tetraedros/triángulos) para reducir el ancho de banda de las matrices de esfuerzos para las formulaciones de elementos finitos definidas sobre lados o sobre elementos. Los generadores de malla han sido diseñados principalmente para elementos finitos nodales, sus salidas son una lista de nodos (2d/3d) y un arreglo de la conectividad de los elementos (triángulos/tetraedros). Sin embargo, para las formulaciones de elementos finitos basados en los lados se requiere una enumeración de los lados de la malla. Reportamos observaciones realizadas con los generadores de mallas Triangle y Tetgen y las estructuras esparcidas de las matrices de esfuerzos obtenidas en formulaciones sobre los lados y sobre elementos. El RCM es un algoritmo de re-enumeración tradicionalmente aplicado a los nodos de la malla. Así para aplicar este algoritmo de re-enumeración al caso de elementos finitos sobre lados y elementos, definimos los grafos de los lados y el grafo de los elementos. Obtenemos así una noTable reducción de ancho de banda de las matrices de esfuerzos, lo que se traduce en reducción de tiempo de ejecución en la multiplicación de matrices esparcidas por un vector. Usamos matrices comprimidas por filas e implementamos la multiplicación de matriz esparcida por vector en una rutina en paralelo usando OpenMp
English abstract 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 tetrahedrons. 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
Disciplines: Matemáticas,
Ciencias de la computación
Keyword: Matemáticas aplicadas,
Análisis de sistemas,
Elementos finitos,
Ancho de banda,
Tiempo de ejecución,
Matriz esparcida,
Vectores
Keyword: Applied mathematics,
Systems analysis,
Finite elements,
Band width
Full text: Texto completo (Ver HTML) Texto completo (Ver PDF)