2025, issue 3, p. 68-78
Received 11.08.2025; Revised 27.08.2025; Accepted 02.09.2025
Published 29.09.2025; First Online 30.09.2025
https://doi.org/10.34229/2707-451X.25.3.6
Solving Linear Systems of Equations with Block Skyscraper Structure
Volodymyr Sydoruk 1 
, Oleksii Chystiakov 1 , Peter Benner 2 , Olena Nikolaievska 1 *
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
This paper proposes an efficient parallel algorithm for solving systems of linear algebraic equations (SLAE) using block skyscraper matrices, designed for execution on shared-memory computing systems. The algorithm is focused on achieving high performance and scalability, making it suitable for resource-intensive computational tasks. Special attention is given to optimizing computations and distributing the workload among processor cores to maximize acceleration. The study includes testing the proposed algorithm on nodes of a modern computational cluster by solving practical problems related to modeling the strength of building structures. The performance characteristics of the algorithm, including total execution time and acceleration coefficients depending on the number of processor cores used, have been analyzed. The impact of block sizes used in the calculations on computational performance has also been investigated. The experimental results demonstrate that the algorithm significantly reduces execution time as the number of processors increases and exhibits stable scalability on systems with a large number of cores. This highlights its applicability for solving complex engineering problems and modeling largescale systems. The proposed approach can be utilized in structural mechanics, applied physics, and other fields of engineering analysis requiring the processing of large data volumes. The conclusions of the study are valuable for further development of parallel programming methods and improving the efficiency of computational systems.
Keywords: high-performance computing, system of linear algebraic equations, Cholesky method, sparse matrices, block skyscraper matrices, parallel algorithms, systems with shared memory.
Cite as: Sydoruk V., Chystiakov O., Benner P., Nikolaievska O. Solving Linear Systems of Equations with Block Skyscraper Structure. Cybernetics and Computer Technologies. 2025. 3. P. 68–78. https://doi.org/10.34229/2707-451X.25.3.6
References
1. Pissanetzky S. Sparse Matrix Technology. Academic Press, 2008. https://doi.org/10.1016/C2013-0-11311-6
2. George A., Liu J. Numerical solution of large sparse systems of equations. M.: Mir, 1984. 334 p. (Russian)
3. Dongarra J., Beckman P., Moore T. et al. The International Exascale Software Project roadmap. The International Journal of High Performance Computing Applications. 2011. Vol. 25, Iss. 1. P: 3–60. https://doi.org/10.1177/1094342010391989
4. Khimich A.N., Popov A.V., Polyanko V.V. Algorithms of parallel computations for linear algebra problems with irregularly structured matrices. Cybern Syst Anal. 2011. Vol. 47. P. 973–985. https://doi.org/10.1007/s10559-011-9377-4
5. Baranov A.Yu., Popov A.V., Slobodyan Y.E., Khimich A.N. Mathematical modeling of building constructions using hybrid computing systems. J. Autom. Inform. Sci. 2017. 49 (7). P. 18–32. https://doi.org/10.1615/JAutomatInfScien.v49.i7.20
6. Khimich A.N., Popov A.V., Chistyakov O.V. Hybrid algorithms for solving the algebraic eigenvalue problem with sparse matrices. Cybern Syst Anal. 2017. 53 (6). P. 937–949. https://doi.org/10.1007/s10559-017-9996-5
7. Khimich O.M., Popov O.V., Chistyakov O.V. et al. A Parallel Algorithm for Solving a Partial Eigenvalue Problem for Block-Diagonal Bordered Matrices. Cybern Syst Anal. 2020. 56. P. 913–92. https://doi.org/10.1007/s10559-020-00311-z
8. Khimich O.M., Popov A.V., Chystiakov О.V. About the Peculiarities of Using Sparse Matrices in Problems 0f Mathematical Modeling. Programming problems. 2022. Vol. 3-4. P. 240–248. https://doi.org/10.15407/pp2022.03-04.240
9. Khimich A.N., Molchanov I.N., Popov A.V., Chistyakova T.V., Yakovlev M.F. Parallel Algorithms to Solve Problems in Calculus Mathematics. Kyiv: Nauk.Dumka, 2008. (in Russian)
10. Benner P., Ezzatti P., Quintana-Ortí E.S., Remón A. A Parallel Multi-threaded Solver for Symmetric Positive Definite Bordered-Band Linear Systems. In: Wyrzykowski R., Deelman E., Dongarra J., Karczewski K., Kitowski J., Wiatr K. (eds), Parallel Processing and Applied Mathematics. PPAM 2015. Lecture Notes in Computer Science. 2016. Vol 9573. Springer, Cham. https://doi.org/10.1007/978-3-319-32149-3_10
11. Sydoruk V., Yershov P. Adaptive algorithm for solving systems of equations with block-skyscraper matrices. International Scientific Technical Journal "Problems of Control and Informatics". 2023. 67 (5). P. 17–31. https://doi.org/10.34229/2786-6505-2022-5-2
12. Khimich O.M., Popov O.V., Chistyakov O.V., Kokhanovsky V.O. Adaptive Algorithms for Solving Eigenvalue Problems in the Variable Computer Environment of Supercomputers. Cybern Syst Anal. 2023. Vol. 59. P. 480–492. https://doi.org/10.1007/s10559-023-00583-1
13. Khimich O.M., Popov A.V. Solving Ill-Posed Problems of the Theory of Elasticity Using High-Performance Computing Systems. Cybern Syst Anal. 2023. 59 (5). P. 743–752. https://doi.org/10.1007/s10559-023-00610-1
14. Petryk M.R., Boyko I.V., Khimich O.M., Sydoruk V.A. High-throughput methods for modeling nanoabsorption and diffusion with feedback in heterogeneous cylindrical multicomponent nanoporous media. Cybern Sys tAnal. 2023. 59 (6). P. 163–177. https://doi.org/10.1007/s10559-023-00636-5
15. Khimich O., Popov A., Chistyakov A. Effective Use of Sparse Matrices in Problems of Mathemaical Modeling. CEUR Workshop Proceedings (CEUR-WS.org). 2023. https://ceur-ws.org/Vol-3501/s20.pdf
16. Khimich A., Polyanko V., Chistyakova T. Parallel algorithms for solving linear systems on hybrid computers. Cybernetics and Computer Technologies. 2020. 2. P. 53–66. https://doi.org/10.34229/2707-451X.20.2.6
17. Khimich O.M., Sydoruk V.A., Nesterenko A.N. Hybrid algorithm Newton method for solving systems of nonlinear equations with block Jacobi matrix. Problems in programming. 2020. Vol. 2-3. P. 208–217. https://doi.org/10.15407/pp2020.02-03.208
18. Chistyakov A.V. On improving the efficiency of mathematical modeling of the problem of stability of construction. Artificial Intelligence. 2020. 25 (3). P. 27–36. https://doi.org/10.15407/jai2020.03.027
19. Velikoivanenko E.A., Milenin A.S., Popov A.V., Sydoruk V.A., Khimich A.N. High-performance methods for analyzing the statistical strength of welded pipelines and pressure vessels using the monte carlo method. Journal of Automation and Information Sciences. 2020. 52 (11). P. 12–27. https://doi.org/10.1615/JAutomatInfScien.v52.i11.20
20. Khimich A.N., Nikolaevskaya E.A., Baranov I.A. Weighted least squares perturbation theory. Еdited by Dr. Mykhaylo Andriychuk «Matrix Theory – Classics and Advances», 2023. https://doi.org/10.5772/intechopen.102885
21. SparseBLAS: https://netlib.org/sparse-blas/index.html (accessed: 11.08.2025)
22. IMSL: https://www.imsl.com/ (accessed: 11.08.2025)
23. NAG: https://nag.com/nag-library/ (accessed: 11.08.2025)
24. Hypre: https://hypre.readthedocs.io/en/latest/ (accessed: 11.08.2025)
25. MUMPS: https://mumps-solver.org/index.php (accessed: 11.08.2025)
26. SUPERLU: https://portal.nersc.gov/project/sparse/superlu/ (accessed: 11.08.2025)
27. SPARSKIT:https:/www-users.cse.umn.edu/~saad/software/SPARSKIT/ (accessed: 11.08.2025)
28. Molchanov I.N. Machine methods for solving problems of applied mathematics. Algebra, approximation of functions, ordinary differential equations. Kyiv: Nauk.Dumka, 2007. 550 p. (in Russian)
29. MKL: https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-c/2024-0/cblas-trsm.html#GUID-230D5D74-DB1B-469A-A24E-3F46FC8E41C7 (accessed: 11.08.2025)
30. OpenMP Application Programming Interface Examples Version 5.2 – April 2022: https://www.openmp.org/wp-content/uploads/openmp-examples-5-2.pdf (accessed: 11.08.2025)
31. SKIT-5: http://icybcluster.org.ua/index.php?lang_id=2&menu_id=5 (accessed: 11.08.2025)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)