Реализация (λ, µ)-свернутого произведения многомерных матриц средствами операции tensordot из библиотек для тензорной алгебры
Аннотация
Алгебра многомерных матриц является удачной моделью данных для задач из самых разных предметных областей. Многие авторы описывали аппаратно-программные комплексы, реализующих алгебру многомерных матриц целиком или параллельные алгоритмы (λ, µ)-свернутого произведения для решения определенной задачи. Их реализации требует значительных трудозатрат, а использование – знание и установку определенный фреймворков и компиляторов. Тем не менее в процессе исследования часто бывает полезно "проверить" предположение на частных случаях, что, возможно, быстро даст контрпример. Статья посещена созданию такого инструмента для прикладных исследований. Python-программы легки в написании, благодаря синтаксису, и имеют обширный выбор разнообразных библиотек. Среди них особое место занимают библиотеки для быстрых вычислений: NumPy, CuPy, PyTorch, TensorFlow. Они могут обеспечить достаточную скорость вычислений как на CPU, так и на GPU, и обладают значительным функционалом для работы с многомерными объектами, хотя и не реализуют (λ, µ)-свернутого произведения. В статье показывается, что операция (0, µ)-свернутого произведения из алгебры многомерных матриц в точности совпадает с операцией tensordot(A, B, µ) из python-библиотек для тензорной алгебры. Статья содержит результаты эксперимента по сравнению скорости вычислений этой операции в разных библиотеках. Автор вводит параллельный алгоритм умножения многомерных матриц, сводящий (λ, µ)-свернутое произведение к последовательности (0, µ)-свернутых произведений, которые могут быть выполнены параллельно. Это фактически сводит сложную задачу к параллельному вызову функции tensordot. Статья содержит подробное описание программы, реализующей алгоритм и результаты ее тестирования в разных средах выполнения.
Литература
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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
