IMPACT OF MATRIX INVERSION ON THE COMPLEXITY OF THE FINITE ELEMENT METHOD
DOI:
https://doi.org/10.15802/stp2016/67358Keywords:
finite element method, FEM, LU, Cholesky, Gaussian elimination, decomposition methods, optimizationsAbstract
Purpose. The development of a wide construction market and a desire to design innovative architectural building constructions has resulted in the need to create complex numerical models of objects having increasingly higher computational complexity. The purpose of this work is to show that choosing a proper method for solving the set of equations can improve the calculation time (reduce the complexity) by a few levels of magnitude. Methodology. The article presents an analysis of the impact of matrix inversion algorithm on the deflection calculation in the beam, using the finite element method (FEM). Based on the literature analysis, common methods of calculating set of equations were determined. From the found solutions the Gaussian elimination, LU and Cholesky decomposition methods have been implemented to determine the effect of the matrix inversion algorithm used for solving the equations set on the number of computational operations performed. In addition, each of the implemented method has been further optimized thereby reducing the number of necessary arithmetic operations. Findings. These optimizations have been performed on the use of certain properties of the matrix, such as symmetry or significant number of zero elements in the matrix. The results of the analysis are presented for the division of the beam to 5, 50, 100 and 200 nodes, for which the deflection has been calculated. Originality. The main achievement of this work is that it shows the impact of the used methodology on the complexity of solving the problem (or equivalently, time needed to obtain results). Practical value. The difference between the best (the less complex) and the worst (the most complex) is in the row of few orders of magnitude. This result shows that choosing wrong methodology may enlarge time needed to perform calculation significantly.
References
Chen R., Wu Y., Yan Z., Zhao Y., Cai X.-C. A parallel domain decomposition method for 3D unsteady incompressible flows at high Reynolds number. Journal of Scientific Computing, 2014, vol. 58, no. 2, pp. 275-289. doi: 10.1007/s10915-013-9732-x.
Balonek K., Gozdur S. Wprowadzenie do metody elementów skończonych. Akademia Górniczo Hutnicza Publ., Kraków, 2009.
Drwal M. Algorytmy algebry numerycznej. Rozwiązywanie układu równań liniowych. Wrocław, Politechnika Wrocławska Publ., 2012.
Dzierżankowski G., Sitek M. Samouczek Metody Elementów Skończonych. Warszawa, Oficyna Wydawnicza Politechniki Warszawskiej Publ., 2012. 106 р.
Geijn R.A. van de. Notes on Cholesky Factorization. Report TX 78712 University of Texas at Austin, Department of Computer Science Publ., Austin, 2011. Р. 1-16.
Cormen T.H., Leiserson C. E., Stein C., Rivest R. L. Introduction to Algorithms. Cambridge, The MIT Press Publ., 1990. 1292 р.
Khawaja H. Application of a 2-D approximation technique for solving stress analyses problem in FEM. Intern. Journal of Multiphysics, 2015, vol. 9, issue 4, pp. 317-324.
Cichoń C., Cecot W., Krok J., Pluciński P. Metody komputerowe w liniowej mechanice konstrukcji. Kraków, Politechnika Krakowska Publ., 2009. 428 р. doi: 10.1260/1750-9548.9.4.317.
Papadimitriu Ch.H. Złożoność obliczeniowa. Warszawa, Wydawnictwa Naukowo-Techniczne Publ., 2002. 540 р.
Rakowski G., Kacprzyk Z. Metoda Elementów Skończonych w mechanic konstrukcji. Warszawa, Oficyna Wydawnicza Politechniki Warszawskiej Publ., 2005. 434 р.
Vandenberghe, L. Applied Numerical Computing (lecture). Available at: http://www.ee.ucla.edu/vandenbe/ee103.html (Accessed 10 April 2016).
Sybis M., Smoczkiewicz-Wojciechowska A., Szymczak-Graczyk A. Analiza złożoności metody różnic skończonych (MRS) oraz metody elementów skończonych (MES) na przykładzie elementu belkowego. Projektowanie, eksploatacja, diagnostyka i naprawy wybranych obiektów budownictwa ogólnego i hydrotechnicznego: мonografia. Instytut Budownictwa i Geoinżynierii Uniwersytet Przyrodniczy Publ., Poznań, 2015. Р. 135-151.
Younis G. Practical method to solve large least squares problems using Cholesky decomposition. Geodesy and Cartography, 2015, vol. 41, issue 3, pp. 113-118. doi: 10.3846/20296991.2015.1086118.
Downloads
Published
How to Cite
Issue
Section
License
Copyright and Licensing
This journal provides open access to all of its content.
As such, copyright for articles published in this journal is retained by the authors, under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0). The CC BY license permits commercial and non-commercial reuse. Such access is associated with increased readership and increased citation of an author's work. For more information on this approach, see the Public Knowledge Project, the Directory of Open Access Journals, or the Budapest Open Access Initiative.
The CC BY 4.0 license allows users to copy, distribute and adapt the work in any way, provided that they properly point to the author. Therefore, the editorial board of the journal does not prevent from placing published materials in third-party repositories. In order to protect manuscripts from misappropriation by unscrupulous authors, reference should be made to the original version of the work.
