2022, issue 2, p. 38-51
Received 02.09.2022; Revised 12.09.2022; Accepted 29.09.2022
Published 30.09.2022; First Online 05.10.2022
https://doi.org/10.34229/2707-451X.22.2.4
Previous | FULL TEXT (in Ukrainian) | Next
Models of Computer Calculations
Valerii Zadiraka *
, Oleksandr Khimich , Inna Shvidchenko *
V.M. Hlushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The complexity of computational algorithms for solving typical problems of computational, applied, and discrete mathematics is analyzed from the perspective of the theory of computation, depending on the computer architecture and the used computing model: single-processor, multiprocessor, and quantum.
The following classes of problems are considered: systems of linear algebraic equations, the Cauchy problem for systems of ordinary differential equations, numerical integration, boundary value problems for ordinary differential equations, factorization of numbers, finding the discrete logarithm of a number in multiplicative integer groups, searching for the necessary record in an unordered database, etc.
The purposes of the paper are:
1. To investigate how the computational complexity depends on the computer architecture and the computational model.
2. To show that the construction of the computational process under the given conditions of calculations is related to the solution of the following problems:
– the existence ε-solution to the problem;
– the existence of T-effective computing algorithms;
– the possibility of building a real computing process under the given computing conditions.
3. To investigate the effect of rounding numbers on computational complexity (especially when solving problems of transcomputational complexity).
4. To give the complexity estimates and total error of the computational algorithm for a number of typical problems of computational, applied, and discrete mathematics.
The results. The complexity estimates of computational algorithms of the listed classes of problems for single-processor, multiprocessor and quantum computing models are given.
The main focus is on high-performance computing: using the principles of parallel data processing and quantum mechanics.
Conclusions. The connection of complexity estimates of computational algorithms with the architecture of computers and models of calculations is demonstrated.
The characteristics of the first quantum computers (2016 – 2022), which have gone beyond laboratory research, are given.
Keywords: computer technologies, rounding error, sequential, parallel and quantum computing models, complexity estimate.
Cite as: Zadiraka V., Khimich O., Shvidchenko I. Models of Computer Calculations. Cybernetics and Computer Technologies. 2022. 2. P. 38–51. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.4
References
1. Bahvalov N.S. On the properties of optimal methods for solving problems of mathematical physics. Zh. vyichisl. matem. i matem. fiz. 1970. 10 (3). P. 555–568. (In Russian)
2. Ivanov V.V. Computer Computing Methods: A Reference Guide. Kiyv: Nauk. dumka, 1986. 584 p. (In Russian)
3. Ivanov V.V., Babich M.D., Berezovskiy A.I., Besarab P.N., Zadiraka V.K., Lyudvichenko V.A. Characteristics of Problems, Algorithms and Computers in Program Complexes of Computational Mathematics. Kiyv, 1984. 53 p. (In Russian)
4. Besarab P.N. Computational complexity of integrating ordinary differential equations. Cybern Syst Anal. 1996. 32 (3). P. 417–423. https://doi.org/10.1007/BF02366506
5. Khimich A.N., Molchanov I.N., Popov A.V., Chistyakova T.V., Yakovlev M.F. Parallel algorithms for solving problems of computational mathematics. Kiyv: Nauk. dumka, 2008. 247 p. (In Russian)
6. NetLib http://www.netlib.org/ (accessed: 23.09.2022)
7. Kartsev M.A. Arithmetic of digital machines. M.: Nauka, 1969. 575 p. (In Russian)
8. Parallel processing systems. M.: Mir, 1985. 416 p. (In Russian)
9. Algorithms, software and architecture of multiprocessor systems. M.: Nauka, 1982. 336 p. (In Russian)
10. Hayrer E., Nersetg S., Vanner T. Solving ordinary differential equations. M.: Mir, 1990. 512 p. (In Russian)
11. Voevodin V.V. Mathematical models and methods in parallel processes. M.: Nauka, 1986. 296 p. (In Russian)
12. Mihalevich V.S., Molchanov I.N., Sergienko I.V. Numerical Methods for the EU Multiprocessor Computing System ES. M.: VVIA im. prof. N.E. Zhukovskogo, 1986. 401 p. (In Russian)
13. Kitaev A., Shen A., Vyalyiy M. Classical and quantum computing. M.: Mir, 1988. 518 p. (In Russian)
14. Zadiraka V.K., Babych M.D., Berezovskyi A.I., Besarab P.M., Hnativ L.O., Liudvychenko V.O. T-efektyvni alhorytmy nablyzhenoho rozviazannia zadach obchysliuvalnoi ta prykladnoi matematyky. Kyiv-Ternopil, “Zbruch”, 2003. 261 p. (In Ukrainian)
15. Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the General Theory of Optimal Algorithms. Springer, 2021. P. 378. https://doi.org/10.1007/978-3-030-90908-6
16. Nil'sen M., Chang I. Quantum computing and quantum information. M.: Mir. 2006. 824 p. (In Russian)
17. Kaptol Ye.Iu., Horbenko I.D Analysis of the possibilities and peculiarities of programming cryptology problems on a quantum computer. Radiotekhnika. 2020. 202. P. 37–48. https://doi.org/10.30837/rt.2020.3.202.03 (In Ukrainian)
18. Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proc. of the 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press. 1994. P. 124–134.
19. Boneh D., Lipton R.J. Quantum cryptanalysis of hidden linear function. Lect. Notes Comput. Sci. 963. 1995. Р. 424–437. https://doi.org/10.1007/3-540-44750-4_34
20. Cleve R. A note of computing Fourier transforms by quantum programs. 1994.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next