Abstract
This paper presents an experimental performance study of implementations of three different types of algorithms for solving band matrix systems of linear algebraic equations (SLAEs) after parabolic nonlinear partial differential equations – direct, symbolic, and iterative, the former two of which were introduced in Veneva and Ayriyan in Effective methods for solving band SLAEs after parabolic nonlinear PDEs (2018) [3]. An iterative algorithm is presented – the strongly implicit procedure (SIP), also known as the Stone method. This method uses the incomplete LU (ILU(0)) decomposition. An application of the Hotelling-Bodewig iterative algorithm is suggested as a replacement of the standard forward-backward substitutions. The upsides and the downsides of the SIP method are discussed. The complexity of all the investigated methods is presented. Performance analysis of the implementations is done using the high-performance computing (HPC) clusters “HybriLIT” and “Avitohol”. To that purpose, the experimental setup and the results from the conducted computations on the individual computer systems are presented and discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ayriyan, A., Buša, J., Jr., Donets, E.E., Grigorian, H., Pribiš, J.: Algorithm and simulation of heat conduction process for design of a thin multilayer technical device. Appl. Therm. Eng. 94, 151–158 (2016). https://doi.org/10.1016/j.applthermaleng.2015.10.095. (Elsevier)
Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn, pp. 174–176. SIAM, Philadelphia, PA (2002)
Veneva, M., Ayriyan, A.: Effective methods for solving band SLAEs after parabolic nonlinear PDEs. In: AYSS-2017, EPJ Web of Conferences, vol. 177, p. 07004 (2018). https://doi.org/10.1051/epjconf/201817707004, arXiv: 1710.00428v2 [math.NA]
Kincaid, D.R., Cheney, E.W.: Numerical Analysis: Mathematics of Scientific Computing, p. 788. American Mathematical Society, Providence, RI (2002)
Samarskii, A.A., Goolin, A.: Chislennye Metody, pp. 45–47. Nauka, Moscow (1989). (in Russian)
Askar, S.S., Karawia, A.A.: On solving pentadiagonal linear systems via transformations. Math. Probl. Eng. 2015, 9 (2015). https://doi.org/10.1155/2015/232456. (Hindawi Publishing Corporation)
El-Mikkawy, M.: A generalized symbolic Thomas algorithm. Appl. Math. 3(4), 342–345 (2012). https://doi.org/10.4236/am.2012.34052
Stone, H.L.: Iterative solution of implicit approximations of multidimensional partial differential equations. SIAM J. Numer. Anal. 4(3), 530–538 (1968). https://doi.org/10.1137/0705044
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn, pp. 307–310. SIAM, Philadelphia, PA (2003). https://doi.org/10.1137/1.9780898718003
Schulz, G.: Iterative berechnung der reziproken matrix. Zeitschrift fur Angewandte Mathematik und Mechanik 13, 57–59 (1933). (in German)
Soleymani, F.: A rapid numerical algorithm to compute matrix inversion. Int. J. Math. Math. Sci. 2012, 11 (2012). https://doi.org/10.1155/2012/134653
Bauer, C., Frink, A., Kreckel, R.: Introduction to the GiNaC framework for symbolic computation within the C++ programming language. J. Symbolic Comput. 33, 1–12 (2002). https://doi.org/10.1006/jsco.2001.0494
El-Mikkawy, M.: Fast and reliable algorithm for evaluating \(n\)th order pentadiagonal determinants. Appl. Math. Comput. 202(1), 210–215 (2008). (Elsevier)
Acknowledgements
The authors want to express their gratitude to the Summer Student Program at JINR, Dr. Ján Buša Jr. (JINR), Dr. Andrey Lebedev (GSI/JINR), Assoc. Prof. Ivan Georgiev (IICT & IMI, BAS), the “HybriLIT” team at LIT, JINR, and the “Avitohol” team at the Advanced Computing and Data Centre of IICT, BAS. Computer time grants from LIT, JINR and the Advanced Computing and Data Centre at IICT, BAS are kindly acknowledged. A. Ayriyan thanks the JINR grant No. 17-602-01.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
The Hotelling-Bodewig iterative algorithm has the form as follows:
where I is the identity matrix, A is the matrix whose inverse we are looking for. \(A^{-1}_{0}\) is taken to be of a diagonal form.
The obtained computational times for the ILU(0) method, the Hotelling-Bodewig iterative algorithm and the Stone method, using the heterogeneous cluster “HybriLIT” and the supercomputer system “Avitohol”, are summarized in Tables 8, 9, and 10.
The matrix implementations lead to 5, 7, and 34 iterations, respectively for finding \(L^{-1}\) and \(U^{-1}\), applying the Hotelling-Bodewig procedure, and for the Stone method while the needed iterations when the array implementations are executed are 5, 6, and 31, respectively. It is expected that inverting L would require less number of iterations, since it is a unit triangular matrix. The achieved accuracy is of an order of magnitude of \(10^{-13}\), having used an error tolerance \(10^{-12}\). Comparing the results for the computational times, one can see that the array implementation not only decreased the time needed for the inversion of both the matrices L and U but also it decreases the number of iterations needed so as the matrix U to be inverted. As one can see, the time required for the SIP procedure is also improved by the new implementation approach. One reason being is that the number of iterations is decreased. Overall, the array implementations decrease the computational times with one order of magnitude. Finally, this second approach requires less amount of memory (instead of keeping \(N\times N\) matrix, just 5 arrays with length N are stored), which allows experiments with bigger matrices to be conducted. However, this method (even in its array form) is not suitable for too large matrices (with number of rows bigger than \(1\times 10^5\)), since the evaluation of the inverse of a matrix is computationally demanding on both time and memory. A comparison between the times on the two computer systems showed that overall “HybriLIT” is a bit faster than “Avitohol”.
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Veneva, M., Ayriyan, A. (2019). Performance Analysis of Effective Methods for Solving Band Matrix SLAEs After Parabolic Nonlinear PDEs. In: Georgiev, K., Todorov, M., Georgiev, I. (eds) Advanced Computing in Industrial Mathematics. BGSIAM 2017. Studies in Computational Intelligence, vol 793. Springer, Cham. https://doi.org/10.1007/978-3-319-97277-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-97277-0_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97276-3
Online ISBN: 978-3-319-97277-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)