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.
References
Mathematics, 2000, No. 123, pp. 85-100.
2. Jemderson H.V., Pukelsheim F., and Searle S.R. On the history of the Kronecker product, Linear
and Multilinear Algebra, 1983, Vol. 14, No. 2, pp. 113-120.
3. Graham A. Kronecker Products and Matrix Calculus with Applications (Dover Books on
Mathematics), Dover Publications, 2018.
4. Buchholz P., Ciardo G., Donatelli S., Kemper P. Complexity of memory-efficient Kronecker
operations with applications to the solution of Markov models, INFORMS J. Comput., 2000,
pp. 203-222.
5. Tadonki C., Philippe B. Parallel multiplication of a vector by a Kronecker product of matrices,
Journal of Parallel and Distributed Computing and Practices, 2000, No. 3 (3), pp. 1-11.
6. Tadonki C. Large-scale Kronecker product on supercomputers, 2011 Second Workshop on
Architecture and Multi-Core Applications (WAMCA 2011). 26-27 Oct. 2011. Victoria, Brazil.
IEEE, pp. 1-4.
7. Doukhnitch E., Strelnikov O., Andreev A., Application of Kronecker Matrix Product for the
Synthesis of Hardware-oriented DSP Algorithms, in Proc. of Intern. Conf. on Signal Proc.
“DSPA-99”, Moscow, Sept. 1999, pp. 78-83.
8. Doukhnitch E., Salamah M., Andreev A. Effective Processor for Matrix Decomposition, Arabian
Journal for Science and Engineering, March 2014, Vol. 39, Issue 3, pp. 1797-1804.
9. Dayar T., Orhan M.C. On vector-Kronecker product multiplication with rectangular factors,
SIAM J. Sci. Comput., 2015, Vol. 37 (5), p. S526-S543.
10. Koukouvinos C., Lappas E., Simos D.E. Encryption schemes using orthogonal arrays, Journal
of Discrete Mathematical Sciences and Cryptography, 2009, No. 12 (5), pp. 615-628.
11. Chefranov A., Dukhnich E. One-time Kronecker product-based Hill cipher modification, International
Journal of Information Assurance and Security, 2017, No. 12 (3), pp. 94-103.
12. Lancaster Р. and Tismenetsky М., The Theory of Matrices. 2nd ed. Orlando, Florida:
AcademicPress, 1985.
13. Chefranov A., Dukhnich E., Shapel A. One-Time Involutory Matrix-Based Hill Cipher Modification,
International Journal of Information Assurance and Security (JIAS), 2020, Vol. 15,
No. 4, pp. 165-174.
14. Dzhambruno M. Trekhmernaya (3D) grafika i animatsiya [3D Graphics &Animation]. Moscow:
Vil'yams, 2002, 640 p.
15. Dzwonkowski M., Rykaczewski R. Secure quaternion Feistel cipher (S-QFC) for DICOM
images, IEEE Transactions on Image Processing, 2019, Vol. 28, No. 1, pp. 371-380.
16. Dzwonkowski M., Papaj M., Rykac R. A new quaternion-based encryption method for DICOM
Images, IEEE Transactions on Image Processing, 2015, Vol. 24, No. 11, pp. 4614-4522.
17. Gantmakher F.R. Teoriya matrits [The theory of matrices]. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury izdatel'stva "Nauka", 1966.
18. Blair Jeffrey S. The Biomedical Engineering handbook. CRC Press Taylor & Francis Group,
New York, 2006, pp. 42-4–42-5.
19. Deng Y., Guo M., Ramos A.F., et al. Optimal low-latency network topologies for cluster performance
enhancement, J. Supercomput. Published online 02 March 2020. Available at:
https://doi.org/10.1007/s11227-020-03216-y.
20. Hayes J.P., Mudge T. Hypercube supercomputers, Proceedings of the IEEE, 1989, Vol. 77
(12), pp. 1829-1841.
