Реализация (λ, µ)-свернутого произведения многомерных матриц средствами операции tensordot из библиотек для тензорной алгебры
Authors: Гончаров Е.И. 
Published: December 2024

Алгебра многомерных матриц является удачной моделью данных для задач из самых разных предметных областей. Многие авторы описывали аппаратно-программные комплексы, реализующих алгебру многомерных матриц целиком или параллельные алгоритмы (λ, µ)-свернутого произведения для решения определенной задачи. Их реализации требует значительных трудозатрат, а использование – знание и установку определенный фреймворков и компиляторов. Тем не менее в процессе исследования часто бывает полезно “проверить” предположение на частных случаях, что, возможно, быстро даст контрпример. Статья посещена созданию такого инструмента для прикладных исследований. Python-программы легки в написании, благодаря синтаксису, и имеют обширный выбор разнообразных библиотек. Среди них особое место занимают библиотеки для быстрых вычислений: NumPy, CuPy, PyTorch, TensorFlow. Они могут обеспечить достаточную скорость вычислений как на CPU, так и на GPU, и обладают значительным функционалом для работы с многомерными объектами, хотя и не реализуют (λ, µ)-свернутого произведения. В статье показывается, что операция (0, µ)-свернутого произведения из алгебры многомерных матриц в точности совпадает с операцией tensordot(A, B, µ) из python-библиотек для тензорной алгебры. Статья содержит результаты эксперимента по сравнению скорости вычислений этой операции в разных библиотеках. Автор вводит параллельный алгоритм умножения многомерных матриц, сводящий (λ, µ)-свернутое произведение к последовательности (0, µ)-свернутых произведений, которые могут быть выполнены параллельно. Это фактически сводит сложную задачу к параллельному вызову функции tensordot. Статья содержит подробное описание программы, реализующей алгоритм и результаты ее тестирования в разных средах выполнения.

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.