HARDWARE-ORIENTED ALGORITHM FOR FAST MULTIPLICATION OF A VECTOR BY A MATRIX KRONECKER PRODUCT

Abstract

The article discusses new algorithm to increase the efficiency of the operation of multiplying a matrix Kronecker product (KP) by a vector. It is based on the use of the KP properties. This operation is widely used in solving problems of processing signals, images, cryptography, etc., where the formation of large matrices with specified properties is performed using small size matrices. In this case, matrices with the following properties are used: orthogonal (unitary), invertible, involutive. Multiplying an n × n square matrix by a vector has a computational complexity of O(n2). Therefore, with an increase in the number of elementary matrix factors, the size of the resulting KP matrix and the complexity of multiplying it by a vector grow exponentially. This circumstance significantly increases the time for solving applied problems. The aim of the proposed work is to construct an algorithm that accelerates the processes of forming the KP and multiplyingthe vector by it. It is proposed to combine the process of multiplication with the process of forming the KP. Thus, the KP matrix is not actually calculated explicitly. Instead, the KP factor matrices are iteratively multiplied by the vector components in O(nlog2n) time with linear memory complexity. The computational scheme with the hypercube topology for the possible hardware implementation of the proposed algorithm is presented. It can be easily pipelined. Section 1 presents the definitions and properties of the KP used in the synthesis of the proposed algorithm. Section 2 presents an example with n = 8 illustrating the proposed algorithm, on the basis of which, in Section 3, a hardware-oriented structure of its implementation for arbitrary n is proposed.