Supercomputing Co-Design for Solving Ill-Posed Linear Inverse Problems Using Iterative Algorithms

Alexander S. Antonov; Vladimir V. Voevodin; Dmitry V. Lukyanenko

doi:10.14529/jsfi250402

Authors

Alexander S. Antonov Research Computing Center, Lomonosov Moscow State University, Moscow, Russia https://orcid.org/0000-0003-2820-7196
Vladimir V. Voevodin Research Computing Center, Lomonosov Moscow State University, Moscow, Russia https://orcid.org/0000-0001-6036-5106
Dmitry V. Lukyanenko Department of Mathematics, Faculty of Physics, Lomonosov Moscow State University, Moscow, Russia https://orcid.org/0000-0001-5140-3617

DOI:

https://doi.org/10.14529/jsfi250402

Keywords:

supercomputing co-design, parallelization efficiency, parallelism, autotuning, AlgoWiki, inverse problem, iterative regularization, conjugate gradient method

Abstract

The paper considers an approach to applying the ideas of supercomputing co-design for the effective use of arbitrary multiprocessor computing systems with distributed memory when using iterative regularization algorithms to solve ill-posed linear inverse problems, which are reduced to solving large overdetermined systems of linear algebraic equations with a dense matrix. The proposed methodology allows for a large number of algorithms to select the best virtual topology of processes (in terms of parallelization efficiency) for solving problems of the class under consideration within the allocated resources of the supercomputer system being used.

References

Antonov, A.S.: MPI and OpenMP Parallel Programming Technologies: Textbook. Moscow University Press (2012)

Antonov, A.S., Maier, R.V., Nikitenko, D.A., Voevodin, V.V.: An approach to solving the problem of supercomputer co-design. Lobachevskii J Math. 45(7), 2965–2973 (2024). https://doi.org/10.1134/S1995080224603680

Kalitkin, N.N., Kuzmina, L.V.: Improved form of the conjugate gradient method. Mathematical Models and Computer Simulations 4(1), 68–81 (2012). https://doi.org/10.1134/S2070048212010061

Kalitkin, N.N., Kuzmina, L.V.: Improved forms of iterative methods for systems of linear algebraic equations. Doklady Mathematics 88(1), 489–494 (2013). https://doi.org/10.1134/S1064562413040133

Kindermann, S.: Optimal-order convergence of Nesterov acceleration for linear ill-posed problems*. Inverse Problems 37(6), 065002 (2021). https://doi.org/10.1088/1361-6420/abf5bc

Lukyanenko, D.: Parallel algorithm for solving overdetermined systems of linear equations, taking into account round-off errors. Algorithms 16(5), 242 (2023). https://doi.org/10.3390/a16050242

Neubauer, A.: On Nesterov acceleration for Landweber iteration of linear ill-posed problems. Journal of Inverse and Ill-posed Problems 25(3), 381–390 (2017). https://doi.org/10.1515/jiip-2016-0060

Park, J., Shin, Y., Lee, J., et al.: HYPERF: End-to-End Autotuning Framework for High-Performance Computing. Proceedings of the 34th International Symposium on High-Performance Parallel and Distributed Computing (20), 1–14 (2025). https://doi.org/10.1145/3731545.3731588

Petrovič, F., Střelák, D., Hozzová, J., et al.: A benchmark set of highly-efficient CUDA and OpenCL kernels and its dynamic autotuning with Kernel Tuning Toolkit. Future Generation Computer Systems 108, 161–177 (2020). https://doi.org/10.1016/j.future.2020.02.069

Tikhonov, A.N., Goncharsky, A.V., Stepanov, V.V., Yagola, A.G.: Numerical methods for the solution of ill-posed problems. Dordrecht: Kluwer Academic Publishers (1995)

Voevodin, V., Antonov, A., Dongarra, J.: AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features. Supercomputing Frontiers and Innovations 2(1), 4–18 (2015). https://doi.org/10.14529/jsfi150101

Voevodin, V., Antonov, A., Nikitenko, D., et al.: Supercomputer Lomonosov-2: Large scale, deep monitoring and fine analytics for the user community. Supercomputing Frontiers and Innovations 6(2), 4–11 (2019). https://doi.org/10.14529/jsfi190201

Vuduc, R., Demmel, J.W., Yelick, K.A.: OSKI: A library of automatically tuned sparse matrix kernels. Journal of Physics: Conference Series 16(1), 521 (2015). https://doi.org/10.1088/1742-6596/16/1/071

vanWerkhoven B.: Kernel Tuner: A search-optimizing GPU code auto-tuner. Future Generation Computer Systems 90, 347–358 (2019). https://doi.org/10.1016/j.future.2018.08.004

Wu, X., Balaprakash, P., Kruse, M., et al.: ytopt: Autotuning scientific applications for energy efficiency at large scales. Concurrency and Computation: Practice and Experience 37(1), e8322 (2023). https://doi.org/10.1002/cpe.8322