IMPACT OF MATRIX INVERSION ON THE COMPLEXITY OF THE FINITE ELEMENT METHOD

M. Sybis, A. Smoczkiewicz-Wojciechowska, A. Szymczak-Graczyk

Abstract


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.


Keywords


finite element method; FEM; LU; Cholesky; Gaussian elimination; decomposition methods; optimizations

Full Text:

PDF

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.


GOST Style Citations


  1. A parallel domain decomposition method for 3D unsteady incompressible flows at high Reynolds number / R. Chen, Y. Wu, Z. Yan [et al.] // J. of Scientific Computing. – 2013. – Vol. 58. – Iss. 2. – P. 275–289. doi: 10.1007/s10915-013-9732-x.
  2. Balonek, K. Wprowadzenie do metody elementów skończonych / K. Balonek, S. Gozdur ; Akademia Górniczo Hutnicza. – Kraków, 2009.
  3. Drwal, M. Algorytmy algebry numerycznej. Rozwiązywanie układu równań liniowych / M. Drwal. – Wrocław : Politechnika Wrocławska, 2012.
  4. Dzierżankowski, G. Samouczek Metody Elemen-tów Skończonych / G. Dzierżankowski, M. Sitek. – Warszawa : Oficyna Wydawnicza Politechniki Warszawskiej, 2012. – 106 р.
  5. Geijn, R. A. van de. Notes on Cholesky Factorization / R. A. van de Geijn // Report TX 78712 University of Texas at Austin, Department of Computer Science. – Austin, 2011. – Р. 1–16.
  6. Introduction to Algorithms / T. H. Cormen, C. E. Leiserson, C. Stein, R. L. Rivest. – Cambridge : The MIT Press, 1990. – 1292 р.
  7. Khawaja, H. Application of a 2-D approximation technique for solving stress analyses problem in FEM / H. Khawaja // Intern. J. of Multiphysics. – 2015.– Vol. 9. – Iss. 4. – Р. 317–324. doi: 10.1260/1750-9548.9.4.317.
  8. Metody komputerowe w liniowej mechanice konstrukcji / C. Cichoń, W. Cecot, J. Krok, P. Pluciński. – Kraków : Politechnika Krakowska, 2009. – 428 р.
  9. Papadimitriu, Ch. H. Złożoność obliczeniowa / Ch. H. Papadimitriu. – Warszawa : Wydaw-nictwa Naukowo-Techniczne, 2002. – 540 р.
  10. Rakowski, G. Metoda Elementów Skończonych w mechanic konstrukcji / G. Rakowski, Z. Kacprzyk. – Warszawa : Oficyna Wydawnicza Politechniki Warszawskiej, 2005. – 434 р.
  11. Vandenberghe, L. Applied Numerical Computing (lecture) [Electronic resource] / L. Vandenberghe. – Available at: http://www.ee.ucla.edu/vandenbe/-ee103.html. – Title from the screen. – Accessed 10.04.2016.
  12. Sybis, M. Analiza złożoności metody różnic skończonych (MRS) oraz metody elementów skończonych (MES) na przykładzie elementu belkowego / М. Sybis, A. Smoczkiewicz-Woj-ciechowska, A. Szymczak-Graczyk // Projek-towanie, eksploatacja, diagnostyka i naprawy wybranych obiektów budownictwa ogólnego i hydrotechnicznego : мonografia / Instytut Budownictwa i Geoinżynierii Uniwersytet Przyrodniczy. – Poznań, 2015. – Р. 135–151.
  13. Younis, G. Practical method to solve large least squares problems using Cholesky decomposition / G. Younis // Geodesy and Cartography. – 2015. – Vol. 41. – Iss. 3. – Р. 113–118. doi: 10.3846/-20296991.2015.1086118.


DOI: https://doi.org/10.15802/stp2016/67358

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)