Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 94
PROCEEDINGS OF THE SEVENTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by:
Paper 113

Efficient Data Structures and Algorithms to avoid Redundant Calculations in the Finite Element Method

A. Más Tomás1, E. Gil Benso2, V. Galvañ Llopis1 and J.M. Vercher Sanchis1

1Department of Architectural Constructions, 2Department of Mechanics of Continuous Medium,
Universidad Politécnica de Valencia, Spain

Full Bibliographic Reference for this paper
, "Efficient Data Structures and Algorithms to avoid Redundant Calculations in the Finite Element Method", in , (Editors), "Proceedings of the Seventh International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 113, 2010. doi:10.4203/ccp.94.113
Keywords: finite element method, data management, hash function, repetitive calculus.

Summary
In the world of science there are many situations where it is necessary to solve repetitive calculations of a certain entity. We found this problem when writing a computer program for the finite element method (FEM).

The calculations are repeated in the FEM because to calculate the state of stresses and strains we must obtain the global stiffness matrix. And for this we need the elementary matrices of each element. In the case studied in this paper we created many equal finite element matrices for prismatic parts, because we control the mesh. By having so many identical elements it is not necessary to calculate the elementary matrix several times, since we would obtain the same results and would waste time.

Therefore, we create an efficient data structure to avoid redundancy in the FEM calculations. We propose a very fast and robust process based on hash functions and search in binary trees. We might have collisions, but also explain how the proposed data management avoids them.

The process proposes before calculating a finite element matrix a check to ascertain if it has already been done before and if so obtain a pointer to the position indicator to where it is stored, access this memory and retrieve it. If the finite element matrix has not been made earlier, it is calculated and stored within the database of objects. A very efficient way to search is to apply the techniques known as hash functions.

We have chosen as hash function the most simple. We take the sum of all bits of the data field and divide by 256, taking the rest of this division, which gives an integer value from 0 to 255. This procedure transforms the whole data field to an 8 bit integer. This function has been shown to be very efficient. It would be easy to substitute by others more advanced such as those proposed by Hsieh [1].

The goal is to reduce the total computing time on personal computers where modelling of complex systems may mean that the necessary time for calculations is unacceptable.

We have compared the results with a simple model between our program and a widely used commercial software. It gave us the same number of terms in the skyline matrix system of equations, which implies a strong parallel for comparison, and the total time achieved was of the order of one hundredth when compared with the proposed methodology. Our experience tells us that the system is very robust. These subroutines are highly optimized and in machine code. Increased memory usage is very small, only limited to the storage of identical matrices.

But our process has a few limitations. In the case of nonlinearity its use is more limited, and with the automatic meshing, Delaunay type of functions [2], its direct use may be inappropriate .

References
1
P. Hsieh, "Hash functions", 2004-2008. http://www.azillionmonkeys.com/qed/hash.html
2
B. Delaunay, "Sur la sphère vide. A la memoire de Georges Voronoi", Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk, 7, 793-800, 1934. http://es.wikipedia.org/wiki/Triangulaci

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £125 +P&P)