Implementation of (λ, µ)-Convolution Product by Means of Tensordot Operation from Libraries for Tensor Algebra
Abstract
Multidimensional matrix algebra is a successful data model for problems from a variety of subject areas. Many authors have described hardware and software complexes that implement the algebra of multidimensional matrices in its entirety or parallel algorithms of (λ, µ)-convolution product to solve a specific problem. Their implementation requires considerable labor, and the use of knowledge and installation of certain frameworks and compilers. Nevertheless, in the process of research, it is often useful to “test” the assumption on special cases, which may quickly give a counterexample. The article is devoted to the creation of such a tool for applied research. Python-programs are easy to write, thanks to the syntax, and have an extensive selection of various libraries. Among them, a special place is occupied by libraries for fast calculations: NumPy, CuPy, PyTorch, TensorFlow. They can provide sufficient computing speed on both CPU and GPU, and have significant functionality for working with multidimensional objects, although they do not implement a (λ, µ)-convolution product. The article shows that the operation (0, µ)-convolution product from the algebra of multidimensional matrices exactly coincides with the tensordot(A, B, µ) operation from python-libraries for tensor algebra. The article contains the results of an experiment comparing the calculation speed of this operation in different libraries. The author introduces a parallel algorithm for multiplying multidimensional matrices, reducing the (λ, µ)-convolution product to a sequence of (0, µ)-convolution products that can be performed in parallel. This actually reduces a complex task to a parallel call of the tensordot function. The article contains a detailed description of the program implementing the algorithm and the results of its testing in different runtime environments.
References
2. Diev O.E., Munerman V.I. [Parallel processing of distributed databases in Postgresql DBMS]. Computer Mathematics Systems and Their Applications. 2017;(18):68-70. Available at: https://elibrary.ru/item.asp?id=30469404 (accessed 28.09.2022). (In Russ.)
3. Munerman V.I., Munerman D.V. The compliance of operations of multi- dimensional matrix algebra with operations of the relational data model. Computer Mathematics Systems and Their Applications. 2019;(20):209-214. Available at: https://elibrary.ru/item.asp?edn=dsutbo (accessed 28.09.2022). (In Russ., abstract in Eng.)
4. Kirillov E.V., Melnik K.V., Munerman V.I. Parallel association rules mining based on NUMA-architecture. Computer Mathematics Systems and Their Applications. 2019;(20):170-176. Available at: https://elibrary.ru/item.asp?id=39103178 (accessed 28.09.2022). (In Russ., abstract in Eng.)
5. Goncharov E.I., Munerman V.I., Samoylova T.A. The method of selecting parameters of multidimensional matrix for hill encryption algorithm. Computer Mathematics Systems and Their Applications. 2019;(20):111-116. Available at: https://elibrary.ru/item.asp?id=39103166 (accessed 28.09.2022). (In Russ., abstract in Eng.)
6. Korchits K.S., Mukha V.S. Vectorial 1-Connected Markov Chains. Doklady BGUIR. 2003;1(3):102-105. Available at: https://libeldoc.bsuir.by/handle/123456789/30997 (accessed 28.09.2022). (In Russ., abstract in Eng.)
7. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Highly available systems. 2018;14(5):50-56. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-08
8. Goncharov E.I. Multi-Dimensional Definition of Convolution. Modern Information Technologies and IT-Education. 2021;17(3):541-549. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.17.202103.541-549
9. Goncharov E., Munerman V., Yakovlev G. Software and Hardware Complex for Calculating Convolutions by Methods Multidimensional Matrix Algebra. In: 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg, Moscow, Russia: IEEE Computer Society; 2021. p. 2176-2180. doi: https://doi.org/10.1109/ElConRus51938.2021.9396584
10. Goncharov E., Iljin P., Munerman V. Multidimensional Matrix Algebra Versus Tensor Algebra or μ > 0. In: 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). St. Petersburg and Moscow, Russia: IEEE Computer Society; 2020. p. 1949-1954. doi: https://doi.org/10.1109/EIConRus49466.2020.9039478
11. Goncharov E.I. Realization the ( λ, µ )-convolution product of matrixes by means of the ( 0, µ )-convolution product. Computer Mathematics Systems and Their Applications. 2022;(23):96-100. Available at: https://elibrary.ru/item.asp?id=48621275 (accessed 28.09.2022). (In Russ., abstract in Eng.)
12. Linge S., Langtangen H.P. Programming for Computations ‒ Python. Texts in Computational Science and Engineering. Vol. 15. Cham: Springer; 2020. 332 p. doi: https://doi.org/10.1007/978-3-030-16877-3
13. Sanner M.F. Python: A Programming Language for Software Integration and Development. Journal of Molecular Graphics and Modelling. 1999;17(1):57-61. doi: https://doi.org/10.1016/S1093-3263(99)99999-0
14. Dabhi S., Parmar M. Eigenvector Component Calculation Speedup Over NumPy for High-Performance Computing. In: Mahapatra R.P., Panigrahi B.K., Kaushik B.K., Roy S. (eds.) Proceedings of 6th International Conference on Recent Trends in Computing. Lecture Notes in Networks and Systems. Vol. 177. Singapore: Springer; 2021. p. 241-249. doi: https://doi.org/10.1007/978-981-33-4501-0_23
15. Ghosh S., Alsobrooks C., Rüfenacht M., Skjellum A., Bangalore P.V., Lumsdaine A. Towards Modern C++ Language Support for MPI. In: 2021 Workshop on Exascale MPI (ExaMPI). St. Louis, MO, USA: IEEE Computer Society; 2021. p. 27-35. doi: https://doi.org/10.1109/ExaMPI54564.2021.00009
16. Pellegrini S., Prodan R., Fahringer T. A Lightweight C++ Interface to MPI. In: 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Munich, Germany: IEEE Computer Society; 2012. p. 3-10. doi: https://doi.org/10.1109/PDP.2012.42
17. Ballman A., Svoboda D. Avoiding Insecure C++ —How to Avoid Common C++ Security Vulnerabilities. In: 2016 IEEE Cybersecurity Development (SecDev). Boston, MA, USA: IEEE Computer Society; 2016. p. 65-65. doi: https://doi.org/10.1109/SecDev.2016.022
18. Bisong E. NumPy. In: Building Machine Learning and Deep Learning Models on Google Cloud Platform. Berkeley, CA: Apress; 2019. p. 91-113. doi: https://doi.org/10.1007/978-1-4842-4470-8_10
19. Sokolov N.P. Functions of multidimensional matrices and their applications for the solutions of linear systems of partial differential equations. Ukrainian Mathematical Journal. 1970;22(6):657-674. doi: https://doi.org/10.1007/BF01086271
20. Nikolaev K.S. Application of modern parallel technologies to the solution of the problem of multiplaying multidimensional matrices by the method of recursive descent. Computer Mathematics Systems and Their Applications. 2020;(21):183-188. Available at: https://elibrary.ru/item.asp?id=44237974 (accessed 28.09.2022). (In Russ., abstract in Eng.)
21. Goncharov E.I., Iljin P.L. Comparison of realisations of parallel multidimensional matrix multiplication algorithms. Computer Mathematics Systems and Their Applications. 2020;(21):102-109. Available at: https://elibrary.ru/item.asp?id=44237961 (accessed 28.09.2022). (In Russ., abstract in Eng.)
22. Zakharov V.N., Munerman V. I. [Parallel Algorithm for Multidimensional Matrix Multiplication]. Modern Information Technologies and IT-Education. 2015;11(2):384-390. Available at: https://elibrary.ru/item.asp?id=26167519 (accessed 28.09.2022). (In Russ.)
23. Nelson M.J., Hoover A.K. Notes on Using Google Colaboratory in AI Education. In: Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE '20). New York, NY, USA: Association for Computing Machinery; 2020. p. 533-534. doi: https://doi.org/10.1145/3341525.3393997
24. Grout I. Realization of NumPy Tensordot using the Field Programmable Gate Array for Embedded Machine Learning Applications. In: 2020 8th International Electrical Engineering Congress (iEECON). Chiang Mai, Thailand: IEEE Computer Society; 2020. p. 1-4. doi: https://doi.org/10.1109/iEECON48109.2020.229523
25. Shirako J., Hayashi A., Paul S.R., Tumanov A., Sarkar V. Automatic Parallelization of Python Programs for Distributed Heterogeneous Computing. In: Cano J., Trinder P. (eds.) Euro-Par 2022: Parallel Processing. Euro-Par 2022. Lecture Notes in Computer Science. Vol. 13440. Cham: Springer; 2022. p. 350-366. doi: https://doi.org/10.1007/978-3-031-12597-3_22
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
